πŸ‡―πŸ‡΅ ζ—₯本θͺž | πŸ‡ΊπŸ‡Έ English

Recursion

Understand functions that call themselves by visualizing the call stack.

What is recursion?

Recursion is a programming technique where a function calls itself.
Anything you can express with a loop can also be written recursively, but recursion really shines when a problem has a naturally self-similar structure.
Every recursive function needs a base case (a stopping condition). Without one, the calls continue forever and you'll hit a stack overflow.

Factorial

n! = n Γ— (n-1) Γ— ... Γ— 1 can be written recursively like this:
int factorial(int n) {
    if (n <= 1) return 1;   // base case
    return n * factorial(n - 1); // recursive call
}
Execution flow for n=4:
factorial(4) β†’ 4 Γ— factorial(3) β†’ 4 Γ— 3 Γ— factorial(2) β†’ 4 Γ— 3 Γ— 2 Γ— factorial(1) β†’ 4 Γ— 3 Γ— 2 Γ— 1 = 24

Call stack visualizer

Watch how recursive calls get pushed onto the stack and then unwound as each one returns.

Fibonacci sequence

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ...) is a classic example of a function that makes two recursive calls.
int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}
Heads up: this naive implementation gets exponentially slower as n grows β€” even fib(40) can take several seconds. In practice, use a loop or memoization.
n =

Things to watch out for

Stack overflow
Without a base case, recursion never stops. The stack gets exhausted and your program crashes.
Performance
Recursion that repeats the same work over and over is inefficient. Consider memoization (caching results) or rewriting it as a loop.
Where recursion shines
Tree traversal, divide-and-conquer algorithms (like merge sort), and any problem that fits the pattern of mathematical induction.

Review Quiz

int mystery(int n) {
    if (n == 0) return 0;
    return n + mystery(n - 1);
}
printf("%d\n", mystery(5));

What is the output?

5
15
120
0
Explanation: mystery(5) = 5 + mystery(4) = 5 + 4 + 3 + 2 + 1 + 0 = 15.
This function computes the sum from 1 to n β€” don't mix it up with factorial (n!).
Share this article
Share on X Share on Facebook