Recursive Functions and Self-Referential Definitions | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 8.8 Free with a free account

Recursive Functions and Self-Referential Definitions

Discrete Mathematics · Chapter 8: Binomial Probability, Recurrence Relations, and Generating FunctionsSection 8.8 · lesson 53 of 879 min · free with a free account

← Applied Binomial Experiment ProblemsNext lesson: First-Order Linear Recurrence Relations →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Defining something in terms of smaller copies of itself - safely.

  • Identify base cases and recursive cases
  • Explain what makes a recursive definition well-founded
  • Trace factorial and Fibonacci recursively
  • Define structures, not just numbers, recursively

Transcript

Everything said in the video, section by section (1,247 words). Read along, or search it.

Binomial Probability, Recurrence Relations, and Generating Functions

Recursive Functions and Self-Referential Definitions

Chapter eight now turns from binomial probability to recurrence relations. It starts with the idea underneath them. Recursion. This section covers what makes a definition in terms of itself legitimate, traces two classic examples, factorial and Fibonacci, and shows that recursion describes structures, not just numbers.

The Opening Problem

Replies to Replies to Replies

When someone opens a busy post, the interface renders the post, and potentially thousands of nested replies. A comment can have replies, each reply can have its own replies, and so on, to whatever depth the conversation has reached. So a comment thread is a comment, together with a list of reply-threads. And each of those is exactly the same kind of object. No separate vocabulary is needed for a reply three levels deep. The definition of a comment thread refers to itself. A function that counts a thread's total replies naturally mirrors that. It computes the answer for each smaller reply-thread, then combines the results. That pattern is called recursion.

Definition 8.8.1

Base Cases and Recursive Cases

A recursive definition defines something partly in terms of itself. Left unrestricted, that's pure circularity. Like a dictionary where every word is defined using other words, and none is ever tied to anything outside. It defines nothing at all. A recursive definition avoids that with two ingredients. Base cases, whose values are stated directly, with no self-reference. And recursive cases, which express the value at an input in terms of the value at strictly smaller inputs. For the definition to work, every recursive case has to reach a base case after finitely many steps. Usually some quantity strictly decreases, and can't decrease forever. Such a definition is called well-founded. That's the same shape as induction, from chapter four. An anchor, plus a step toward it. A well-founded recursive definition is induction used to build a function, instead of proving a statement.

Definition 8.8.2 and Worked Example 8.8.1

Factorial, Down and Back Up

The factorial function is one of the simplest examples. Zero factorial is one, the base case. And n factorial is n times n minus one factorial, for n at least one. It's well-founded, since each application replaces n with n minus one. After exactly n steps, the base case is reached. Compute four factorial. Unwinding down, four factorial is four times three factorial. Three factorial is three times two factorial, and so on, down to zero factorial, which is one. Then unwind back up. One factorial is one. Two factorial is two. Three factorial is six. And four factorial is four times six, which is twenty-four. Four recursive calls going down, matched by four multiplications coming back up.

Recursion as Code

1 Branch of Code per Case

A recursive definition already specifies, for every input that isn't a base case, which smaller subproblem to solve and how to combine the result. So it translates directly into a recursive function in code, typically one branch per case. If n is zero, return one. That's the base case, with no further call. Otherwise, return n times the factorial of n minus one. That's the recursive case.

Definition 8.8.3

Fibonacci: 2 Base Cases, 2 Calls

The Fibonacci sequence is the standard next example, because it departs from factorial in an instructive way. It has two base cases. F of zero is zero, and F of one is one. And for n at least two, F of n is F of n minus one, plus F of n minus two. It's still well-founded. Both n minus one and n minus two are strictly smaller, and stay non-negative, so repeated application always reaches zero or one. What's new is that a single recursive case makes two recursive calls. The code mirrors that directly.

Figure 8.8.1

The Recursion Tree for F(5)

Because each non-base call branches into two, the calls form a recursion tree, not a single chain. Here's the full tree for F of five. Every box is one call. The gold boxes are base cases, returned immediately as zero or one. Reading upward, each box adds its two children. F of two is one plus zero, which is one. F of three is one plus one, which is two. F of four is two plus one, three. And F of five is three plus two, which is five.

Worked Example 8.8.2

15 Calls to Get F(5) = 5

Count the calls. There are fifteen, to compute a value of five. That's because several subproblems are solved more than once. F of three is computed twice. F of two, three times. F of one, five times, and F of zero, three times. Nine of the fifteen calls recompute a value already found somewhere else in the tree. And the redundancy gets worse for larger n, since each extra level roughly doubles the calls. But the recursive definition itself is unambiguous, and entirely correct. The redundancy belongs to this particular way of carrying it out.

8.8.3 Beyond Numbers

Recursive Structures

Nothing requires a recursive definition to produce numbers. Sets and data structures can be defined recursively too, with the same two ingredients. A binary tree is either empty, or a node together with two binary trees, its left and right subtrees. The definition refers to itself, just like the comment thread. Now make the thread precise. A comment thread is either a single comment with no replies, the base case. Or a comment with a nonempty list of comment threads, its replies. The total reply count is defined on that same structure. A thread with no replies has total zero. Otherwise, for each reply, count one for the reply, plus its own total, and add those up.

Worked Example 8.8.3

Counting Replies in a Small Thread

The code mirrors that definition. If a thread has no replies, return zero. Otherwise, sum one plus the total for each reply. Take a thread rooted at comment A. A has two replies, B and C. B has none. C has one reply, D, and D has none. Start with the base cases, the leaves. B and D each have total zero. C has one reply, D, so its total is one plus zero, which is one. And A has two replies. Its total is one plus zero for B, plus one plus one for C. That's three. Directly inspecting the thread confirms it. Besides A, there are exactly three comments, B, C, and D.

Table 8.8.1

The Same Anatomy, 3 Times

This table lays the three definitions side by side. Factorial has one base case, makes one recursive call per step, and decreases n toward zero. Fibonacci has two base cases, makes two calls per step, and also decreases n toward zero. And the reply count has a base case of a thread with no replies. It makes one call per direct reply, and the nesting depth decreases. Recursive sequences like Fibonacci are called recurrence relations. The next two sections develop systematic ways to find a closed formula for the nth term, without unwinding the recursion by hand.

Takeaways

Anchor, Then Shrink

To summarize. A recursive definition has base cases, stated with no self-reference, and recursive cases that reduce every other input to a strictly smaller one. It's well-founded only if a base case is always reached after finitely many steps. A recursive case can make one smaller call, like factorial, or several, like Fibonacci. And structures such as binary trees and comment threads can be defined recursively too. Here's something to think about. Computing F of five by direct recursion takes fifteen calls. Yet the Fibonacci definition is exactly as correct as factorial's. What does that say about the difference between a recursive definition, and a recursive procedure for computing it? Suppose you had to compute F of thirty. Would you follow the recursion by hand? Or would you fill in a table, F of zero, F of one, F of two, in order? Which is less work, and why doesn't the definition force either choice?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Recursive Functions and Self-Referential Definitions

What are base cases and recursive cases in a recursive definition?
A base case gives a value directly with no self-reference, while a recursive case defines the value at an input using the value at strictly smaller inputs. Together they keep a definition from being circular. For factorial, 0! = 1 is the base case and n! = n\cdot(n-1)! for n\ge 1 is the recursive case.
What makes a recursive definition well-founded?
A recursive definition is well-founded when every recursive case reaches a base case after finitely many steps. Usually some quantity, like n, strictly decreases and cannot decrease forever. Without that, the definition is circular and defines nothing. This mirrors induction: the base case is the anchor, and the recursive step moves toward it.
How do you trace the factorial and Fibonacci functions recursively?
Unwind downward until you hit base cases, then combine values on the way back up. For 4!: 4! = 4\cdot 3!, down to 0! = 1, then 1!=1, 2!=2, 3!=6, 4!=24. Fibonacci has F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2). Tracing F(5) gives F(2)=1, F(3)=2, F(4)=3, F(5)=5.
Can you define things other than numbers recursively?
Yes, sets and data structures can be defined recursively using the same base and recursive cases. A binary tree is either empty, or a node with a left binary tree and a right binary tree. A comment thread is either one comment with no replies, or a comment with a nonempty list of reply threads. Both definitions refer to themselves.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →