Recursion concepts

📖 Theory

The function that phones itself

Every function you have written so far calls other functions. Today's twist sounds illegal the first time you hear it:

fact(4) computes its answer by calling... fact(3). Which calls fact(2). Which calls fact(1).

A function calling itself. Students either love recursion or fear it, and the difference is always one thing: whether they have traced it once, slowly, by hand. That is exactly what we will do.

📖 Theory

Asking down the queue

You are 8th in the canteen line and want your position, but cannot see the front. So you ask the person ahead: "what is your position?" They do not know either, so they ask ahead... until the question reaches the first person, who simply knows: "I am 1st."

Now answers flow back: 1st, so 2nd, so 3rd... up to you: 8th. One question passed down, answers built up on the way back. That is recursion, complete with its stopping person.

📖 Theory

The two mandatory parts

Every correct recursive function has exactly two parts:

• Base case: an input so small the function answers directly, without calling itself. The person who knows they are 1st.
• Recursive case: reduce the problem one step and call yourself on the smaller piece.

For factorial (n! = n × (n-1) × ... × 1):

• Base: fact(1) = 1
• Recursive: fact(n) = n × fact(n-1)

No base case, or a step that never shrinks toward it, and the calls never stop.

⌨️ Practical

Factorial, four lines of self-reference

#include <iostream>
using namespace std;

long fact(int n) {
    if (n <= 1)            // BASE CASE: answer directly
        return 1;
    return n * fact(n - 1); // RECURSIVE CASE: smaller problem
}

int main() {
    cout << fact(4) << endl;   // 24
    return 0;
}

📖 Theory

The trace, on the call stack

Calls pile UP until the base case, then results return DOWN:

fact(4)

fact(3)

fact(2)

fact(1) → 1 (base case reached)

2 × 1 → 2

3 × 2 → 6

4 × 6 → 24

Each pending call waits in memory on the call stack: fact(4) cannot finish before fact(3) returns. Push on the way down, pop on the way back: the stack lesson's LIFO, running your programs from the inside.

💭 Think first

Trace one yourself

Using the same function, trace fact(5) on paper: write the chain of calls down to the base case, then the multiplications on the way back. What is the final value, and which call finishes FIRST?

🧩 Quiz

A student writes: long fact(int n) { return n * fact(n - 1); } with no if. What happens when fact(4) runs?

1. Calls never stop, the call stack fills up, and the program crashes (stack overflow)
2. It returns 24 anyway; the base case is optional
3. Compile error: recursion requires an if statement
4. It returns 0 because fact(0) is eventually reached

⚠️ Watch out

Exam precision: recursion vs iteration

The classic 5-marker asks for differences. Score with these:

• Recursion: shorter code, natural for self-similar problems (trees, Tower of Hanoi), but each call costs stack memory and call overhead.
• Iteration (loops): more code sometimes, but no stack growth.
• Every recursion can be rewritten as iteration; the reverse is also true.

And never forget to NAME the two parts (base case, recursive case) when defining recursion.

📖 Theory

Where recursion is the natural language

Folders inside folders, the tree structures two lessons away, the quicksort and mergesort you will meet in later semesters, JSON parsing: all self-similar, all naturally recursive. When the problem contains a smaller copy of itself, recursion is not a trick, it is the honest description.

✅ Summary

Key takeaways

• Recursion: a function calls itself on a smaller input until a base case answers directly.
• Two mandatory parts: base case (the brakes) and recursive case (the smaller step).
• fact(4): calls stack up 4,3,2,1 and results return in reverse: 1,2,6,24.
• Each pending call lives as a frame on the call stack: push going down, pop coming back (LIFO).
• Missing base case = stack overflow crash, not a compile error.
• Recursion trades stack memory for shorter, self-similar code; loops trade the reverse.
• Memory hook: asking down the queue until someone knows.