UPI Study › Courses › C++ Programming › Free lessons › Lesson 8.7 Free with a free account
Recursive Calls
C++ Programming · Chapter 8: FunctionsSection 8.7 · lesson 57 of 84video coming soon
← Function Overloading in ActionNext lesson: Breaking Tasks Into Functions →
In this lesson
Functions that repeat themselves.
- Identify the base case, the recursive case, and what shrinks
- Trace a recursion down and back up
- Spot the waste in branching recursion
- Prevent non-termination; choose recursion or a loop
Transcript
Everything said in the video, section by section (1,572 words). Read along, or search it.
Opening Idea
A Function That Calls Itself
A function is allowed to call itself. That sounds circular, and isn't, provided two things hold. Each call works on a smaller version of the problem. And there's a smallest version that's answered outright, rather than passed on. Get those right, and some problems become startlingly short. Get them wrong, and the program runs until it's stopped.
Core Concept
Base Case and Recursive Case
Every correct recursive function has exactly two kinds of branch. The base case answers the smallest version of the problem directly, without calling anything. The recursive case answers a larger version by asking for the answer to a slightly smaller one, then doing a little work with what comes back. So every recursion has two phases. Calls go down to the base case: factorial of 4 asks for factorial of 3, which asks for 2, which asks for 1. Then the answers come back up. Factorial of 1 returns 1. 2 times 1 is 2. 3 times 2 is 6. And 4 times 6 is 24. Nothing is multiplied on the way down. All the arithmetic happens on the way back up.
Worked Example
Factorial With Three Requirements
Here's factorial, with both parts labeled. If n is at most 1, return 1: the base case. Otherwise, return n times the factorial of one less than n: the recursive case. Three requirements must hold, and missing any one gives a function that never finishes. A base case must exist. Without it, every call makes another call, forever. Something must shrink. Here, n minus 1 is strictly smaller each time. Without that, the same question is asked repeatedly. And the base case must be reachable. That's the one people overlook. N at most 1, rather than n equals 1, is a deliberate defense. With equality, factorial of minus 3 counts downward past the base forever. Writing the base case as a range, instead of a point, costs nothing, and closes that hole.
Call Tracing
Four Activations Alive at Once
Each call is an independent activation, with its own parameters and its own local variables. The outer call is paused, not replaced, and resumes when the inner one returns. Trace factorial of 4 through the calls. Depth 1: n is 4, waiting to compute 4 times something. Depth 2: n is 3. Depth 3: n is 2. Depth 4: n is 1, and that's the base case. At the deepest point, four activations exist at once, each holding its own n. The multiplication in the first call can't happen until three further calls have finished. So depth isn't free. It's the quantity that eventually runs out.
More Examples
GCD, Power, and Reversing Text
The same shape appears again and again, with different shrinking steps. GCD: if b is zero, the answer is a. Otherwise, it's the GCD of b, and a mod b. The remainder shrinks fast. Power: if the exponent is zero, the answer is 1. Otherwise, it's the base times the power with the exponent reduced by 1. And reversing text: if the left position has reached the right, there's nothing left to do. Otherwise, swap the two ends, and move both inward. Run all three: GCD of 48 and 18 is 6, 2 to the 10th is 1024, and stressed reverses to desserts. Identifying the base case, the recursive case, and what shrinks is how you write a new one.
Key Insight
Shrink Speed Decides Depth
Notice how differently these shrink. Factorial and power step down by one, so the depth reached equals the input. The remainder in GCD collapses so quickly that even huge inputs finish fast: a few dozen calls at most. So depth is decided by how fast the problem shrinks, not by how large it started.
New Pattern
Fibonacci Branches Into Two Calls
Everything so far makes one call per activation, so the calls form a single chain. Fibonacci makes two. If n is at most 1, return n. Otherwise, add fib of one less than n to fib of two less than n. That's the definition written out exactly, and now the calls branch.
Call Tree
Fib of 5 Repeats Its Work
Fib of 5 calls fib of 4 and fib of 3. Fib of 4 calls fib of 3 again, and so on down. Fib of 3 is computed twice, and fib of 2 three times. 15 calls, to answer a question the loop version answers in 5 steps.
Cost Analysis
Duplicated Calls Compound Explosively
And it gets much worse. For n of 5, the tree makes 15 calls, against 5 loop steps: three times the work. For 10, 177 calls. For 20, 21,891 calls. For 30, nearly 2.7 million calls, against 30 loop steps. These are real counts from the program. The fault isn't recursion. The definition is correct. The fault is that each branch recomputes answers the other branch already worked out, and the duplication compounds at every level. Two repairs exist. Keep the answers already computed, so each is worked out once. Or use the loop version, which carries two values forward. Recognizing the pattern matters more than the fix. Whenever a call tree contains the same question twice, the same waste is present.
Recursion Wins
Towers of Hanoi in Three Lines
Here's where recursion genuinely wins: the Towers of Hanoi. Three pegs, a stack of discs of different sizes on the first, and two rules. Move one disc at a time, and never place a larger disc on a smaller one. Move the whole stack to the third peg. Written as a loop, it's a serious puzzle. Written recursively, it's three lines, because the recursive statement is the insight. To move n discs from A to C: first, move all but the largest disc from A to B, using C. That's a smaller version of the same problem. Then move the largest disc from A to C, the only real move. Then move the smaller discs from B to C, using A. The base case is zero discs: nothing to do. And the code is that sentence.
Worked Example
Seven Moves for Three Discs
For three discs, the output is seven moves. Run it. Disc 1 to C, disc 2 to B, disc 1 onto it. Then disc 3, the largest, from A to C. Then disc 1 back to A, disc 2 to C, and disc 1 on top. The move count is 2 to the n, minus 1. 7 for 3 discs, 1,023 for 10, and over a million for 20. That growth is a property of the puzzle, not of recursion. No method can do better, because every one of those moves is genuinely required.
Common Mistake
When Recursion Never Stops
Each activation needs its own room, and only so many can exist at once. A recursion that never reaches its base case keeps adding activations until that limit is passed. Then the program stops abruptly, usually with a message mentioning overflow, or simply a crash. Here is the unreachable-base fault: n equals 1, called with minus 3. Factorial of 5 prints 120, then the run dies. Three faults cause it, and all three build and run. No base case: nothing ever returns a value outright. A base case that's unreachable: the value shrinks past it, to zero, minus 1, minus 2, and onward. And nothing shrinking: the same question asked again at every level. Two habits prevent all three. Write the base case first, before the recursive line, so it can't be forgotten. And write it as a range rather than a point. At most 1 catches everything at or below the base.
Design Choice
Choosing Recursion or a Loop
So, recursion or a loop? Each recursive step costs a call, with its own activation to set up and put away. A loop step costs almost nothing. Recursion has a depth limit. A loop can run any number of times. Recursion reads best when the problem is defined in terms of itself: puzzles, nested structures, divide and conquer. It reads worst for simple counting and accumulating, where the call adds ceremony and nothing else. A workable rule: if you can state the method as, and then do the same thing to what's left, recursion will read well. If the sentence is, for each of these, do that, write a loop. Factorial passes the first test only barely. That's why it's in every explanation of recursion, and almost never in real code.
Checklist
Before You Write Recursion
Before you write a recursive function, run through a short checklist. State the base case in words first: what's the smallest input, and what's its answer? Write it as a range, not a single value. Name what shrinks, and check it shrinks on every path, not just the expected one. Check that the shrinking reaches the base, rather than stepping past it. Trace two calls by hand: one that reaches the base immediately, and one that recurses at least twice. And if the call tree branches, ask whether the same question appears twice. If it does, expect the waste you saw with Fibonacci.
Quick Check
Counting Down by Twos
Quick check. Count down subtracts 2 each time, and stops when n equals zero. Which call finishes: count down of 6, or count down of 5? Pause and predict. Count down of 6 finishes: 6, 4, 2, 0, and zero is the base case. Count down of 5 steps right past it: 5, 3, 1, minus 1, and on. It never returns, and the run crashes when the stack runs out. Write the base case as a range, n at most zero, and both calls finish.
Key Takeaways
Recursion in Five Sentences
To summarize. A recursive function needs a base case, a recursive case, and something that shrinks until it reaches the base. Calls go down, and the work happens coming back up. Branching recursion can repeat work exponentially. For problems like Hanoi, the recursive statement is the insight itself. For simple counting and accumulating, prefer a loop.
About C++ Programming at UPI Study
C++ Programming (Computer Science 242) is a self-paced online course of 84 video lessons in 11 chapters, from your first program to decisions, loops, arrays, functions, classes, files, pointers and inheritance. 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 Every course with PRO →
Why take it here
Why students take C++ Programming with UPI Study
Where the credit goes
Universities that work with NCCRS
C++ Programming 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 Recursive Calls
What are the base case and the recursive case in a recursive function?
How do you trace a recursive call like factorial(4)?
Why is recursive Fibonacci so slow compared to a loop?
Why does my recursive function crash with a stack overflow, and how do I prevent it?
About the C++ Programming course
How many college credits is C++ Programming?
How much does C++ Programming cost and what is included?
Which universities accept UPI Study credits?
How long does C++ Programming take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in C++ Programming.
84 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →