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)
#include <bits/stdc++.h>
using namespace std;
int n;
int s[20];
// last = last chosen element
// cur = just for tracing (current element)
int LIS(int i, int last, int cur) {
if (i == n) return 0;
// option 1: skip s[i]
int ch1 = LIS(i + 1, last, s[i]);
// option 2: take s[i] if it’s increasing
int ch2 = 0;
if (s[i] > last) {
ch2 = 1 + LIS(i + 1, s[i], s[i]);
}
return max(ch1, ch2);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i];
cout << "LIS length = " << LIS(0, -1, 0);
}
Call tree for array [3,1,2]:
LIS(0,-∞,0)
├─ skip 3 → LIS(1,-∞,3)
│ ├─ skip 1 → LIS(2,-∞,1)
│ │ ├─ skip 2 → LIS(3,-∞,2)
│ │ └─ take 2 → LIS(3,2,2)
│ └─ take 1 → LIS(2,1,1)
│ ├─ skip 2 → LIS(3,1,2)
│ └─ take 2 → LIS(3,2,2)
└─ take 3 → LIS(1,3,3)
├─ skip 1 → LIS(2,3,1)
└─ 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.




