Recursion

Learn how to write functions that call themselves to solve problems through recursive thinking.

A Simple Example

#include <iostream>

// Count down from n to 1
void countdown(int n) {
    // Base case: stop when we reach 0
    if (n <= 0) {
        std::cout << "Liftoff!" << "\n";
        return;
    }

    // Recursive case: print and call with smaller value
    std::cout << n << "..." << "\n";
    countdown(n - 1);  // Function calls itself!
}

int main() {
    countdown(5);
    return 0;
}

Breaking It Down

Base Case - The Stopping Condition

• What it does: Defines when the recursion should stop
• Essential: Without it, you get infinite recursion and stack overflow
• Example: if (n <= 0) return; stops when counting reaches zero
• Remember: Always write the base case first when creating recursive functions

Recursive Case - The Self-Call

• What it does: Calls the same function with a simpler problem
• Must progress: Each call should move closer to the base case
• Example: countdown(n - 1) reduces n by 1 each time
• Remember: Think "solve a smaller version of the same problem"

The Call Stack

• What happens: Each function call is pushed onto a stack in memory
• Unwinding: When base case is reached, calls return in reverse order
• Limit: Stack has limited size, too many calls cause stack overflow
• Remember: Recursion uses more memory than loops due to stack frames

Recursive Return Values

• What to do: If function returns a value, return the recursive call
• Common pattern: return someValue + recursiveCall(n-1);
• Example: Factorial needs return n * factorial(n-1);
• Remember: Forgetting to return the recursive result loses computed values

Why This Matters

• Some problems are naturally recursive: calculating factorials, traversing tree structures, searching directories, processing nested data.
• Recursion can make these problems elegant and simple, where iterative solutions would be complex and hard to understand.
• Master recursion and you'll unlock a new way of thinking about problem-solving.

Critical Insight

The order of the recursive call matters! Calling recursively before or after your operation changes behavior completely:

#include <iostream>

void beforeRecursion(int n) {
    if (n <= 0) return;
    std::cout << n << " ";  // Print FIRST
    beforeRecursion(n - 1);  // Then recurse
}
// Output for beforeRecursion(5): 5 4 3 2 1

void afterRecursion(int n) {
    if (n <= 0) return;
    afterRecursion(n - 1);  // Recurse FIRST
    std::cout << n << " ";  // Then print
}
// Output for afterRecursion(5): 1 2 3 4 5

Operations after the recursive call happen in "unwinding" order, from innermost to outermost!

Best Practices

Always define the base case first: Write and test your stopping condition before the recursive case to prevent infinite recursion.

Make progress toward base case: Each recursive call must move closer to the base case. Ensure parameters change in a way that eventually reaches the stopping condition.

Consider iteration for simple cases: If recursion depth could be large or the problem is naturally iterative, use loops instead to avoid stack overflow.

Return recursive calls: If your function returns a value, don't forget return recursiveFunction(...) to pass the result up the call chain.

Common Mistakes

Missing Base Case: Causes infinite recursion and stack overflow. Always include a clear stopping condition.

Base Case Never Reached: Progress doesn't lead to base case. Example: decrementing by 2 but checking for n == 0 misses odd numbers.

Forgetting to Return Recursive Call: Writing factorial(n-1); instead of return n * factorial(n-1); loses the computed value.

Too Deep Recursion: Very large inputs cause stack overflow. Consider iteration or tail recursion optimization.

Inefficient Recursion: Multiple redundant calculations like naive Fibonacci. Use memoization or dynamic programming.

Debug Challenge

This recursive function tries to count down but has a bug that causes infinite recursion. Click the highlighted line to fix it:

1 #include <iostream>

2

3 void countdown(int n) {

4 if (n <= 0) {

5 std::cout << "Liftoff!" << "\n";

6 return;

7 }

8 std::cout << n << "\n";

9 countdown(n);

10 }

countdown(0); countdown(n * 2); countdown(n - 1); countdown(n + 1);

Quick Quiz

1. What are the two essential parts of a recursive function?

Try and catch blocks

Parameters and return value

Base case and recursive case

Loop and condition

Every recursive function needs a base case (stopping condition) and a recursive case (the part that calls itself with a simpler problem). Loops are for iteration, not recursion.

2. What happens if you forget the base case in a recursive function?

The function automatically stops after 100 calls

The function returns 0

Infinite recursion and stack overflow

Compilation error

Without a base case to stop the recursion, the function calls itself forever until the stack runs out of memory, causing a stack overflow crash. C++ does not have automatic recursion limits.

3. Given: int factorial(int n) { if (n <= 1) return 1; return n * factorial(n-1); } What is factorial(4)?

16

10

24

4

factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1) = 4 * 3 * 2 * 1 = 24. If you got 16, you may have confused factorial with power (4^2 = 16).

Check Answers Try Again

Step Through the Code

Walk through the code step by step. Watch how variables change and see the program output at each line.

Step Through Reset Edit Code

Loading execution trace...

Step 0 of 0

Default Memory Addresses Byte-Level View

Variables

Click "Step Through" to begin

Output

Stack / Heap

Output:

Error:

Lesson Progress

• Fix This Code
• Quick Quiz
• Practice Playground - run once

Complete Lesson