UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 8.2 Free with a free account
Thinking Recursively
Data Structures and Algorithms · Chapter 8: RecursionSection 8.2 · lesson 32 of 8712 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Calculating the True Cost of Methods That Call Themselves →← When to Call Itself vs. When a Loop Does BetterNext lesson: Calculating the True Cost of Methods That Call Themselves →
In this lesson
Base cases, progress, the call stack, and induction proofs for recursion.
- Identify the base case, recursive case, and progress in a recursive method
- Trace how frames pile up on the call stack and then unwind
- Predict output when work happens before or after the recursive call
- Prove a recursive method correct with mathematical induction
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,886 words). Read along, or search it.
Opening Question
Finding Your Place in Line
You're standing in a long line, and you want to know your place in it. But you can't see the front. So you ask the person ahead of you: what's your position? They ask the person ahead of them, and so on, up the line. The person at the very front just answers: one. Then each person adds one to the answer they got, and passes it back. Two, three, four, five. Nobody solved the whole problem. Each person solved a tiny piece, and trusted the person ahead for the rest. That's recursion.
First Example
Countdown to Liftoff
In Java, a method can call itself. That's called recursion. The simplest example counts down. Countdown prints its number, then calls countdown again, on one less. When the number reaches zero, it prints Liftoff instead, and returns without calling itself. Start it at three, and it prints three, two, one, Liftoff. Each call handles one number, and hands a smaller problem to a fresh call. That stopping rule is essential. A method that always calls itself, and never stops, can never finish.
Key Idea
Base Case, Recursive Case, Progress
Every correct recursive method has three parts. The base case is the smallest version of the problem, whose answer you know directly. It ends the chain of calls. The recursive case handles anything larger. The method calls itself on a smaller version, and uses that answer to build its own. And progress: each call must move the input closer to the base case. Without progress, the base case is never reached.
Worked Example
Factorial as a Smaller Factorial
Factorial is the standard first example. The factorial of n, written n with an exclamation mark, is the product of the whole numbers from one to n. And zero factorial is defined to be one. The key observation: n factorial equals n times the factorial of one less than n. A bigger factorial is just a smaller one, with one more multiplication. So the method has a base case, n equal to zero, which returns one. And a recursive case, which returns n times the factorial of one less than n.
Strategy
Three Questions for Any Recursion
When you write a recursive method, ask three questions. What's the smallest version, and what's its answer? For factorial: zero, and one. How is a bigger version built from a smaller one? Multiply the smaller answer by n. And does each call get closer to the smallest version? Yes: one less than n is one step nearer to zero.
Call Stack
Each Call Gets Its Own Frame
How does Java keep track of all those waiting calls? With frames. When a method is called, Java creates a frame for that call. It holds the call's parameters, its local variables, and the place to return to. Frames live on the call stack. A new frame goes on top when a method is called, and the top frame comes off when its method returns. With recursion, the same method can have many frames on the stack at once, and each frame has its own copy of n. Call factorial of three. It can't finish yet: it waits for factorial of two, which waits for factorial of one, which waits for factorial of zero. Zero is the base case, so that frame returns one straight away.
Call Stack
Multiplying on the Way Back Up
Now the stack unwinds. Factorial of one gets its answer back, multiplies one times one, and returns one. Factorial of two returns two times one, which is two. And factorial of three returns three times two: six. Notice when the multiplying happens. The calls go down without multiplying anything. All of it happens on the way back up.
Trace
Indented Trace of Factorial Calls
You can watch it happen. Add a print when each call starts, and another when it returns, indented by how deep the call is. Factorial of three is called, then two, then one, then zero, each one level deeper. Then the stack unwinds, and the returns come back out: zero returns one, one returns one, two returns two, and three returns six. The indentation is the stack depth. At its deepest point, a call to factorial of n needs n plus one frames. Stack memory is limited. A chain of calls that's far too deep runs out of room, and Java stops the program with a StackOverflowError.
Worked Examples
Powers and Digit Sums
Two more examples follow the same recipe. To raise a base to a power, notice that base to the power exp is base times base to one less than exp. Anything to the power zero is one: that's the base case. The shrinking quantity is the exponent, while the base is passed along unchanged. So two to the tenth is ten twenty-four, and three to the fourth is eighty-one. To add up the digits of a whole number, split off the last digit with n mod ten, and shrink the number with n divided by ten. A single digit is the base case: it's its own digit sum. For forty-eight thirty-seven, the calls peel off one digit at a time: seven, three, eight, four. The additions on the way back give twenty-two.
Two Calls
Fibonacci Calls Form a Tree
The Fibonacci numbers start zero, one, and every later number is the sum of the two before it: one, two, three, five, eight. That definition is already recursive. But it differs from the others in two ways: it needs two base cases, and its recursive case makes two calls. If n is at most one, return n. Otherwise, return the fib of one less than n, plus the fib of two less than n. Because each call can start two more, the calls form a tree, not a chain. Fib of four makes nine calls in all. Look at fib of two. It's worked out twice, from scratch, both times. Count the calls as n grows from one to six: one, three, five, nine, fifteen, twenty-five. The count climbs fast, and the repeated work is the reason.
Common Mistake
Int Overflow at Thirteen Factorial
One warning that isn't about recursion at all. Factorial of twelve is about four hundred seventy-nine million, and it's right. But factorial of thirteen prints about one point nine billion. The true value is over six billion. An int simply can't hold it. That's a limit of the number type, not a fault in the recursion. A long, or a BigInteger, postpones the limit.
Key Idea
Print Before or After the Call
Where the recursive call sits matters. Compare two methods that differ in one thing only: whether the print comes before the call, or after it. Print before, called with three, prints three, two, one. Its work happens on the way down the stack, in the original order. Print after prints one, two, three. Its work waits until each call returns, so it happens on the way back up, in reverse order. It's the same pattern as factorial, where the multiplication waited for the return.
Quick Check
Tracing Echo of Two
Quick check. This method prints both before and after its recursive call. If n is zero, it returns. Otherwise it prints n, calls echo on one less, and then prints n again. What does echo of two print? Is it two one one two, two one two one, or one two two one? Pause, and predict. It prints two, one, one, two. The first print runs on the way down: two, then one. Then echo of zero just returns, and the second print runs on the way back up: one, then two. The tempting answer, two one two one, reads it like a loop. But the second print of two has to wait until the whole call on one has finished.
Common Mistakes
Bugs That Break the Three Parts
Most recursion bugs break one of the three parts. No base case: the calls never stop. No progress: the argument never changes. Both keep adding frames until the stack is full, and end in a StackOverflowError. A base case that some inputs miss: a factorial that stops at n equal to one works for five, but called on zero, it never reaches one, and never stops. An input outside the expected range: factorial of minus one counts down, away from zero. Reject bad input before recursing. And an ignored result: a version that calls itself, but then returns plain n, gives four for an input of four, instead of twenty-four.
Debugging
A Checklist for Recursion Bugs
A short checklist catches most of these. Print the argument at the top of the method, and watch whether it moves toward the base case. Test the smallest input first, then one slightly larger, then one outside the expected range. And check every path: it either returns directly, or calls itself on something smaller, and it uses the value that comes back.
Induction
Dominoes and Recursive Methods
Tracing shows that a method works for one input. To know it works for every input, use mathematical induction. Think of a long row of dominoes. If the first one falls, and each falling domino knocks over the next, then they all fall. An induction proof has matching parts. The base step shows the claim holds for the smallest input. In the method, that's the base case. The hypothesis assumes the claim holds for smaller inputs. That's the recursive call, working on something smaller. And the induction step shows the claim then holds for the current input. That's the recursive case, combining the smaller answer correctly.
Worked Example
Proving Factorial by Induction
Here's the proof for factorial. The claim: for every whole number n, zero or more, factorial of n returns n factorial. Base step. For n equal to zero, the method returns one, and zero factorial is one. The claim holds. Hypothesis. Suppose n is at least one, and the factorial of one less than n is right. Step. Since n isn't zero, the method returns n times that value, and by the hypothesis, that's n factorial. So the claim holds for every n. For digit sum, the number shrinks by more than one each time, so the hypothesis assumes the claim for every smaller number, not just one less. Fibonacci needs that too. And notice what progress gives the proof. If the input doesn't shrink, the hypothesis says nothing useful, and the proof breaks, just as the program never ends. One limit: induction proves a method gives the right answer. It says nothing about how long the method takes.
Quick Check
A Base Case Odd Inputs Miss
One more check. Half sum returns zero when n is zero. Otherwise it returns n, plus the half sum of two less than n. It's called three times: with four, with five, and with six. One of those calls never finishes. Which one? Pause, and decide. Half sum of five never finishes. Five, three, one, then minus one: the input steps right over zero, and keeps going until the stack overflows. Four and six are even, so they land exactly on zero, and return six and twelve. It's a base case that some inputs miss. The fix is a base case every input reaches, such as n less than or equal to zero.
Key Takeaways
Thinking Recursively Essentials
To sum up. A recursive method solves a problem by calling itself on a smaller version of that problem. It needs a base case, a recursive case, and progress toward the base case. Each active call has its own frame. Frames pile up on the way down, and unwind on the way back. Work before the call happens going down, and work after it happens coming back up. And induction shows why the method is correct.
Think About It
Predicting Calls for Fib of Thirty
Here's something to think about. Fib of four makes nine calls, and fib of six makes twenty-five. Without computing anything, what do you expect for fib of thirty? And what might be done about it?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 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 All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms 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 UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks 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 Thinking Recursively
What are the three parts of a recursive method?
How do you write factorial recursively in Java?
Why does the order of a print and a recursive call matter?
How do you prove a recursive method correct with induction?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →