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

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 do with a loop can also be expressed with recursion, but recursion shines when the problem has a naturally self-similar structure.
Every recursion needs a base case (stop condition). Without it, calls continue forever and you get a stack overflow.

Factorial

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

Call stack visualizer

See how recursive calls are pushed onto the stack and then returned.

Fibonacci sequence

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ...) is a classic example of a function with two recursive calls.
int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}
Warning: 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 ends. The stack is exhausted and the program crashes.
Performance
Recursion that repeats the same computation is inefficient. Consider memoization (caching results) or rewriting as a loop.
Where recursion shines
Tree traversal, divide-and-conquer (like merge sort), and problems that match mathematical induction.

Quick 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 confuse it with factorial (n!).
Share this article
Share on X Share on Facebook