Recursion

Base cases and smaller subproblems

Recursion is like "Russian nesting dolls": you open one doll, and inside there is a smaller one, until the smallest one cannot be opened (the termination condition).

Writing recursion must answer two questions:
① When does it stop? (termination condition, also called the boundary condition)
② How does it get smaller each time? (the recursive relation; the problem size must decrease)

Call chain: f(5) → f(4) → f(3) → f(2) → f(1), until f(1) returns directly, and then the answer is "collected" back layer by layer.

Recursion vs iteration: factorial calls and returns

factorial(3) calls factorial(2), then factorial(1), and returns 1→2→6. Recursion needs a base case and smaller subproblems; iteration can keep the running product directly.

long long factorialIterative(int n) {
    long long result = 1;
    for (int i = 2; i <= n; ++i) result *= i;
    return result;
}

Assume 0≤n≤20 so the result fits in long long. Both factorial implementations take O(n) time. The recursive version needs O(n) call-stack space; the loop uses O(1) auxiliary space. Do not assume compiler elimination of recursion. Tree-shaped problems may suit recursion, while naive Fibonacci repeats subproblems and is not linear time.

Recursive factorial and Fibonacci code

Example 1: Find the factorial of n

#include <iostream>
using namespace std;


long long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

int main() {
    cout << factorial(5) << endl;
    return 0;
}

factorial(5)=5×factorial(4)=5×4×factorial(3)=…=5×4×3×2×1=120. Each time n decreases by 1, finally stopping at 1, and then the results are multiplied back layer by layer.

Example 2: Fibonacci sequence (the nth term)

#include <iostream>
using namespace std;

// F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)
int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    for (int i = 1; i <= 8; i++) {
        cout << fib(i) << " ";
    }
    cout << endl;
    return 0;
}

fib(5)=fib(4)+fib(3), fib(4)=fib(3)+fib(2)…… keep breaking it down until fib(1) or fib(2), which directly return 1. Note that this way of writing it recalculates repeatedly, and it will be very slow when n is large.

Tips

• Recursion must have a termination condition (base case); without it, it will "blow the stack" and cause the program to crash.
• Each recursive call must make the problem size smaller (such as n-1), otherwise it will never reach the termination condition.
• The safe recursion depth depends on the runtime environment and stack frame size; when the depth is too large, consider loops or an explicit stack, and memoization does not necessarily reduce the call depth.
• The key to understanding recursion: first think clearly about "how to solve the smallest subproblem", then write "how the big problem depends on the small problem".

Prerequisites

• Functions and parameters

Technical references

• C++ working draft: function calls

Scope note

This lesson is written by InfoCode and is not an official syllabus; the reference level is a site mapping and does not represent official levels, certification or eligibility. Practice records do not establish mastery or eligibility.

Reference level: GESP Level 5 (site mapping)

See contest pathways