Recursion — Understanding with Stack Pictures & Examples

Правка en2, от Nourhan_Abo-Heba, 2025-10-05 17:47:11

Hi everyone! In this post I’ll try to make recursion clear using stack intuition and ASCII trees after each example.


What is Recursion?

A function can call another function. A function can also call itself — that’s recursion.

Example:

void Print2() {
    cout << "NOUR";
}

void Print() {
    Print2();
    cout << "NOUR";
}

int main() {
    Print();
}

Stack:

Push: main() → Print() → Print2()
Pop:  Print2() → Print() → main()
  • exit(0) → terminates all stack frames immediately.
  • return → terminates only the current function.

What if the function calls itself with no stop?

void Print() {
    Print();
    cout << "NOUR";
}

int main() {
    Print();
}

Stack:

Push: main() → Print() → Print() → Print() → … infinite
Pop:  never happens → program crashes (stack overflow)

We need a base case to stop recursion.


Adding a base case

int n = 5;

void Print(int i) {
    if (i == n) return; // base case
    Print(i + 1);       // recursive call with modified input
    cout << "NOUR";
}

int main() {
    Print(0);
}

Stack trace (push):

main() → Print(0) → Print(1) → Print(2) → Print(3) → Print(4) → return

Stack trace (pop):

Print(4) → Print(3) → Print(2) → Print(1) → Print(0) → main()

Everything after the recursive call waits until the recursive call finishes.


Example 1: Printing Digits of a Number

We want: 1234007 → 1 2 3 4 0 0 7

void digit(int x) {
    if (x == 0) return;
    digit(x / 10);
    cout << x % 10 << ' ';
}

int main() {
    digit(1234007);
}

Call tree:

digit(1234007)
 └─ digit(123400)
     └─ digit(12340)
         └─ digit(1234)
             └─ digit(123)
                 └─ digit(12)
                     └─ digit(1)
                         └─ digit(0)

Unwinding prints: 1 2 3 4 0 0 7


Example 2: Factorial

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

Call tree for fact(4):

fact(4)
 └─ 4 * fact(3)
      └─ 3 * fact(2)
           └─ 2 * fact(1)
                └─ 1 * fact(0)

During unwind:

fact(0)=1
fact(1)=1*1=1
fact(2)=2*1=2
fact(3)=3*2=6
fact(4)=4*6=24

Example 3: Fibonacci

int fibo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

int main() {
    cout << fibo(5);
}

Call tree for fibo(5):

fibo(5)
 ├─ fibo(4)
 │   ├─ fibo(3)
 │   │   ├─ fibo(2)
 │   │   │   ├─ fibo(1)
 │   │   │   └─ fibo(0)
 │   │   └─ fibo(1)
 │   └─ fibo(2)
 │       ├─ fibo(1)
 │       └─ fibo(0)
 └─ fibo(3)
     ├─ fibo(2)
     │   ├─ fibo(1)
     │   └─ fibo(0)
     └─ fibo(1)

Example 4: LIS (Longest Increasing Subsequence)

int n;
int s[20];

int LIS(int i, int last) {
    if (i == n) return 0;

    int ch1 = LIS(i + 1, last);
    int ch2 = 0;
    if (s[i] > last) {
        ch2 = 1 + LIS(i + 1, s[i]);
    }
    return max(ch1, ch2);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    cout << LIS(0, -1);
}

For array [3,1,2] recursion tree (take or not take):

LIS(0,-∞)
 ├─ skip 3 → LIS(1,-∞)
 │   ├─ skip 1 → LIS(2,-∞)
 │   │   ├─ skip 2 → LIS(3,-∞)
 │   │   └─ take 2 → LIS(3,2)
 │   └─ take 1 → LIS(2,1)
 │       ├─ skip 2 → LIS(3,1)
 │       └─ take 2 → LIS(3,2)
 └─ take 3 → LIS(1,3)
     ├─ skip 1 → LIS(2,3)
     └─ take 1 (impossible because 1<3)

Example 5: Grid Path Sum

int n, m, s[10][10];

long long solve(int i, int j) {
    if (i == n || j == m) return -1e15;          // invalid
    if (i == n - 1 && j == m - 1) return s[i][j]; // base case

    long long ch1 = solve(i, j + 1);
    long long ch2 = solve(i + 1, j);

    return max(ch1, ch2) + s[i][j];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> s[i][j];

    cout << solve(0, 0);
}

Call tree for a small grid will branch right/down at each step.


Recap

  • Recursion = function calling itself.
  • Always have a base case to stop.
  • Modify input each call to move closer to base case.
  • Everything after the recursive call runs only when deeper calls finish.

Once you understand the push/pop stack model, recursion becomes natural and you can apply it to many CP problems.


История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Nourhan_Abo-Heba 2025-10-05 17:47:11 350
en1 Английский Nourhan_Abo-Heba 2025-10-05 17:34:52 4918 Initial revision (published)