Some problems are naturally made of smaller copies of themselves. To find the factorial of 5, you only need the factorial of 4 and one multiplication. To list every file in a folder, you list the files and then do the same thing for each sub-folder. When a function solves a problem by calling itself on a smaller version of that problem, we call it recursion.
In the Functions chapter we saw how one function calls another. Recursion is simply the case where the function being called is the same one. In this chapter we will see how it works inside the computer (the call stack), how to write recursive functions correctly, how to analyse their cost, and the tracing questions that appear in university exams, GATE and placement tests.
What is Recursion?
Recursion is a technique in which a function calls itself, directly or indirectly, to solve a problem by reducing it to smaller instances of the same problem.
Here is the smallest useful example:
#include <iostream>
void countDown(int n) {
if (n == 0) { // base case: stop here
std::cout << "Go!\n";
return;
}
std::cout << n << '\n';
countDown(n - 1); // recursive case: a smaller problem
}
int main() {
countDown(3);
}
Output:
3
2
1
Go!
countDown(3) prints 3 and calls countDown(2), which prints 2 and calls countDown(1), which prints 1 and calls countDown(0). That last call does not recurse again; it prints Go! and returns.
The Two Parts of Every Recursive Function
Every correct recursive function has two parts:
Part | What it does | In |
|---|---|---|
Base case | A simple input whose answer is known directly, without recursion. It stops the chain of calls. |
|
Recursive case | Breaks the problem into a smaller one and calls the function on it. |
|
There is a third, hidden requirement: every recursive call must move closer to a base case. countDown(n - 1) makes n smaller each time, so it is guaranteed to reach 0 (for non-negative inputs). If you called countDown(-1), n would go -1, -2, -3 ... and never hit 0. A base case that is never reached is as bad as no base case at all.
A good habit before writing any recursive function is to answer three questions:
What is the smallest input, and what is its answer? (base case)
If someone already solved the smaller problem for me, how do I build my answer from it? (recursive case)
Does every call make the input smaller, so the base case is always reached? (termination)
The second question is the key mental trick. Do not try to follow every call in your head. Just trust that the call on the smaller input returns the right answer, and use it. This is the same reasoning as mathematical induction.
Example: Factorial
Mathematically, factorial is already defined recursively:
0! = 1
n! = n × (n − 1)! for n ≥ 1
The C++ code is almost a word-for-word translation:
#include <iostream>
long long factorial(int n) {
if (n <= 1) { // base case: 0! = 1! = 1
return 1;
}
return n * factorial(n - 1); // n! = n × (n-1)!
}
int main() {
for (int i = 0; i <= 5; ++i) {
std::cout << i << "! = " << factorial(i) << '\n';
}
std::cout << "20! = " << factorial(20) << '\n';
}
Output:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
20! = 2432902008176640000
We return long long because factorials grow very fast. A 32-bit int can hold at most 12! (479001600), and even a 64-bit long long overflows after 20!. Signed integer overflow is undefined behaviour in C++, so factorial(21) with this code would not just give a "wrong" answer; the program would have no defined meaning at all.
Notice the base case is n <= 1, not n == 1. That makes factorial(0) work, and it also stops the recursion if someone passes a negative number by mistake.
How Recursion Works: The Call Stack
How can one function be "running" several times at once? The answer is the call stack.
Every time a function is called, the program creates a new stack frame (also called an activation record) that holds that call's parameters, local variables and the place to return to. Each recursive call gets its own frame, so each call has its own separate copy of n. Frames are pushed when a call starts and popped when it returns, in last-in, first-out order.
Let's add some printing to watch this happen. The depth parameter is only used for indentation:
#include <iostream>
void indent(int depth) {
for (int i = 0; i < depth; ++i) {
std::cout << " ";
}
}
int factorial(int n, int depth) {
indent(depth);
std::cout << "call factorial(" << n << ")\n";
int result;
if (n <= 1) {
result = 1; // base case
} else {
result = n * factorial(n - 1, depth + 1); // wait for the smaller answer
}
indent(depth);
std::cout << "return " << result << " from factorial(" << n << ")\n";
return result;
}
int main() {
int answer = factorial(4, 0);
std::cout << "Answer: " << answer << '\n';
}
Output:
call factorial(4)
call factorial(3)
call factorial(2)
call factorial(1)
return 1 from factorial(1)
return 2 from factorial(2)
return 6 from factorial(3)
return 24 from factorial(4)
Answer: 24
Read it from top to bottom. The calls go down (the winding phase) until the base case, then the answers come back up (the unwinding phase). At the deepest point, four frames exist at the same time:
┌──────────────────────┐
top → │ factorial(1) n = 1 │ returns 1
├──────────────────────┤
│ factorial(2) n = 2 │ waiting: 2 × ?
├──────────────────────┤
│ factorial(3) n = 3 │ waiting: 3 × ?
├──────────────────────┤
│ factorial(4) n = 4 │ waiting: 4 × ?
├──────────────────────┤
│ main │
└──────────────────────┘
Unwinding: 1 → 2 × 1 = 2 → 3 × 2 = 6 → 4 × 6 = 24
This picture explains the main cost of recursion: a call with recursion depth d needs d stack frames at the same time, so recursive factorial uses O(n) extra memory, while a loop would use O(1).
Stack Overflow
The stack is small: typically about 8 MB for the main thread on Linux and 1 MB on Windows (it depends on the system and settings). If recursion goes too deep, or never stops, the stack runs out. This is a stack overflow, and the program usually crashes with a segmentation fault (Linux) or a stack overflow exception (Windows). Unlike Java, C++ does not throw a catchable exception for this.
#include <iostream>
void hello(int n) {
std::cout << "Hello " << n << '\n';
hello(n + 1); // no base case!
}
int main() {
hello(1);
}
GCC (version 12 and later) can spot this simple case at compile time when you use -Wall:
p10_warn_infinite.cpp: In function ‘void hello(int)’:
p10_warn_infinite.cpp:3:6: warning: infinite recursion detected [-Winfinite-recursion]
3 | void hello(int n) {
| ^~~~~
p10_warn_infinite.cpp:5:10: note: recursive call
5 | hello(n + 1); // no base case!
| ~~~~~^~~~~~~
The compiler only catches obvious cases. A base case that exists but is never reached, like countDown(-1) above, will not be detected. So deep recursion (say, a million levels) is risky even when it is logically correct; use a loop for such inputs.
Work Before vs After the Recursive Call
Where you place the work relative to the recursive call changes the order of the result. This is the single most tested idea in recursion output questions.
#include <iostream>
void printBefore(int n) { // work BEFORE the call
if (n == 0) return;
std::cout << n << ' ';
printBefore(n - 1);
}
void printAfter(int n) { // work AFTER the call
if (n == 0) return;
printAfter(n - 1);
std::cout << n << ' ';
}
int main() {
printBefore(5);
std::cout << '\n';
printAfter(5);
std::cout << '\n';
}
Output:
5 4 3 2 1
1 2 3 4 5
printBefore prints while the calls are going down, so it prints 5 first. printAfter makes the call first and prints while the calls are coming back up, so the deepest call (n = 1) prints first. The same trick lets us print digits or binary numbers in the correct order, as you will see below.
When the recursive call is the first statement and the work comes after it, people sometimes call it head recursion. When the recursive call is the very last action, it is tail recursion (covered later in this chapter).
Types of Recursion
Type | Meaning | Example |
|---|---|---|
Direct | The function calls itself. |
|
Indirect (mutual) | A calls B, and B calls A. |
|
Linear | At most one recursive call per invocation. |
|
Tree (multiple) | Two or more recursive calls per invocation. |
|
Tail | The recursive call is the last thing the function does. |
|
Non-tail | Work remains after the recursive call returns. |
|
Indirect Recursion
#include <iostream>
bool isOdd(int n); // declaration needed: isEven uses isOdd
bool isEven(int n) {
if (n == 0) return true;
return isOdd(n - 1);
}
bool isOdd(int n) {
if (n == 0) return false;
return isEven(n - 1);
}
int main() {
std::cout << std::boolalpha;
std::cout << "isEven(10): " << isEven(10) << '\n';
std::cout << "isOdd(7): " << isOdd(7) << '\n';
}
Output:
isEven(10): true
isOdd(7): true
Because isEven uses isOdd before isOdd is defined, we must declare isOdd first (a function prototype, as discussed in the Functions topic). This example is only for learning; n % 2 == 0 is obviously the sensible way to test evenness.
Tree Recursion: Fibonacci and Its Hidden Cost
The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, ... where each number is the sum of the previous two. The recursive definition is short and elegant, and the code below also counts how many times fib is called:
#include <iostream>
long long calls = 0;
long long fib(int n) {
++calls;
if (n <= 1) {
return n; // fib(0) = 0, fib(1) = 1
}
return fib(n - 1) + fib(n - 2); // two recursive calls
}
int main() {
for (int n : {5, 10, 20, 30}) {
calls = 0;
long long value = fib(n);
std::cout << "fib(" << n << ") = " << value
<< " calls = " << calls << '\n';
}
}
Output:
fib(5) = 5 calls = 15
fib(10) = 55 calls = 177
fib(20) = 6765 calls = 21891
fib(30) = 832040 calls = 2692537
Over 2.6 million calls to compute fib(30)! The reason is visible in the call tree. Each call branches into two, and the same values are computed again and again:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) f(1) f(0) f(1) f(0)
/ \
f(1) f(0)
fib(3) is computed 2 times, fib(2) 3 times, fib(1) 5 times ...
For this version, the number of calls for fib(n) is exactly 2·F(n+1) − 1, where F is the Fibonacci sequence (check: n = 5 gives 2 × 8 − 1 = 15). Since Fibonacci numbers grow like φn with φ ≈ 1.618, the running time is exponential, often written loosely as O(2n) (the tight bound is Θ(φn)). The recursion depth, and therefore the stack space, is only O(n).
The fix is to remember answers that were already computed, called memoization. With a table of results (which we can build in the next topic, Arrays), each fib(k) is computed once, and the time drops to O(n). This idea is the starting point of dynamic programming. A simple loop that keeps the last two values also works in O(n) time and O(1) space.
More Classic Recursive Functions
#include <iostream>
// Sum of digits: 4096 -> 4 + 0 + 9 + 6
int digitSum(int n) {
if (n < 10) return n;
return n % 10 + digitSum(n / 10);
}
// Print the binary form of a non-negative number
void printBinary(int n) {
if (n > 1) {
printBinary(n / 2); // print the higher bits first
}
std::cout << n % 2;
}
// Fast power: x^n using O(log n) multiplications
long long power(long long x, int n) {
if (n == 0) return 1;
long long half = power(x, n / 2); // ONE recursive call, reused
if (n % 2 == 0) return half * half;
return half * half * x;
}
// Euclid's algorithm: gcd(a, b) = gcd(b, a % b)
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// Count the digits of a positive number
int countDigits(int n) {
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
int main() {
std::cout << "digitSum(4096) = " << digitSum(4096) << '\n';
std::cout << "binary of 13 = ";
printBinary(13);
std::cout << '\n';
std::cout << "power(2, 40) = " << power(2, 40) << '\n';
std::cout << "gcd(84, 36) = " << gcd(84, 36) << '\n';
std::cout << "countDigits(907150) = " << countDigits(907150) << '\n';
}
Output:
digitSum(4096) = 19
binary of 13 = 1101
power(2, 40) = 1099511627776
gcd(84, 36) = 12
countDigits(907150) = 6
A few things worth noticing:
printBinaryrecurses onn / 2before printingn % 2. The remainders come out in reverse order, so printing them while unwinding puts them in the correct order (13 = 1101 in binary).powermakes one recursive call and reuses the result. Each call halvesn, so it needs only about log2n levels: computing 240 takes 7 calls instead of 40 multiplications. If you wrotepower(x, n / 2) * power(x, n / 2)instead, you would make two calls per level and lose the entire benefit (the work goes back to O(n)).gcduses Euclid's rule gcd(a, b) = gcd(b, a mod b). It runs in O(log min(a, b)) steps: 84, 36 → 36, 12 → 12, 0 → answer 12.
Tower of Hanoi
Three rods A, B, C. Rod A holds n discs, largest at the bottom. Move them all to C, one disc at a time, never placing a larger disc on a smaller one.
Thinking iteratively, this is hard. Thinking recursively, it is three lines. To move n discs from A to C:
Move the top n − 1 discs from A to B (using C as the helper).
Move the largest disc from A to C.
Move the n − 1 discs from B to C (using A as the helper).
#include <iostream>
int moves = 0;
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to); // 1. move n-1 discs out of the way
std::cout << "Move disc " << n << " from " << from << " to " << to << '\n';
++moves; // 2. move the largest disc
hanoi(n - 1, via, to, from); // 3. put the n-1 discs back on top
}
int main() {
hanoi(3, 'A', 'C', 'B');
std::cout << "Total moves: " << moves << '\n';
}
Output:
Move disc 1 from A to C
Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C
Total moves: 7
The number of moves satisfies the recurrence T(n) = 2T(n − 1) + 1 with T(0) = 0, whose solution is T(n) = 2n − 1. For 3 discs that is 7; for 64 discs it is more than 1.8 × 1019 moves. This recurrence is a GATE favourite.
Tail Recursion
A call is a tail call if it is the very last action of the function: its result is returned directly, with nothing left to do afterwards. return n * fact(n - 1); is not a tail call, because the multiplication happens after the call returns. We can make factorial tail recursive by passing the partial answer along in an extra parameter (an accumulator):
#include <iostream>
// Not tail recursive: the multiplication happens AFTER the call returns.
long long fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}
// Tail recursive: the recursive call is the very last thing done.
// 'acc' carries the answer built so far.
long long factTail(int n, long long acc = 1) {
if (n <= 1) return acc;
return factTail(n - 1, acc * n);
}
// The same logic written as a loop
long long factLoop(int n) {
long long acc = 1;
while (n > 1) {
acc *= n;
--n;
}
return acc;
}
int main() {
std::cout << fact(10) << ' ' << factTail(10) << ' ' << factLoop(10) << '\n';
}
Output:
3628800 3628800 3628800
Why care? When nothing is left to do after the call, the current stack frame is no longer needed, so a compiler can reuse it and turn the recursion into a jump, effectively a loop. This is tail call optimisation (TCO). GCC and Clang usually do it when optimisation is enabled (for example -O2), but the C++ standard does not guarantee it. At -O0, or when a local object with a destructor is still alive at the point of the call, the frames remain. So in C++, do not rely on tail recursion to avoid stack overflow; if the depth can be large, write the loop yourself. Converting a tail-recursive function to a loop is mechanical, as factLoop shows.
Recursion vs Iteration
Point | Recursion | Iteration (loops) |
|---|---|---|
Termination | Base case | Loop condition becomes false |
Extra memory | One stack frame per active call (O(depth)) | Usually O(1) |
Speed | Function-call overhead on each step | Usually a little faster |
Failure if it does not stop | Stack overflow (crash) | Infinite loop (hangs) |
Code clarity | Very natural for trees, divide and conquer, backtracking | Natural for simple counting and scanning |
Anything written with recursion can be written with loops (if necessary by managing your own stack), and vice versa. Choose recursion when the problem has a recursive shape: tree and graph traversal (DFS), merge sort and quick sort, binary search, generating permutations and subsets, and backtracking problems such as N-Queens and Sudoku. Choose a loop for straight-line repetition like summing 1 to n.
Common Mistakes
Missing or unreachable base case. The result is a stack overflow. Check that every path makes the input smaller.
Forgetting
returnon the recursive call. Writingfactorial(n - 1);instead ofreturn n * factorial(n - 1);in a function that returns a value. Flowing off the end of a non-void function (other thanmain) is undefined behaviour;-Wallwarns about it, so read your warnings.Making the same call twice. As in
power(x, n / 2) * power(x, n / 2), this can turn a fast algorithm into a slow one. Store the result in a variable.Overflow in the result. Factorial and power grow fast; pick a big enough type or check limits.
Using recursion where depth can be huge. Recursing once per element of a list with a million elements risks stack overflow.
Exponential tree recursion without memoization. Naive Fibonacci beyond n ≈ 45 takes seconds or minutes.
Interview and GATE Questions
Here is a typical "predict the output" program. Try to work it out before opening the answers.
#include <iostream>
void fun(int n) {
if (n > 0) {
fun(n - 1);
std::cout << n << ' ';
fun(n - 1);
}
}
int f(int n) {
if (n <= 0) return 0;
return n + f(n - 2);
}
int main() {
fun(3);
std::cout << '\n' << f(7) << ' ' << f(8) << '\n';
}
What does fun(3) print?
1 2 1 3 1 2 1. fun(n) prints the output of fun(n-1), then n, then fun(n-1) again. fun(1) prints "1", fun(2) prints "1 2 1", and fun(3) prints "1 2 1" + "3" + "1 2 1". The number of values printed is 2n − 1 (same recurrence as Tower of Hanoi).
What are f(7) and f(8)?
f(7) = 7 + 5 + 3 + 1 + f(−1) = 16, and f(8) = 8 + 6 + 4 + 2 + f(0) = 20. The program prints 16 20. Note that the base case is n <= 0; with n == 0, f(7) would skip past 0 to −1, −3, ... and overflow the stack.
What is the time and space complexity of recursive factorial?
Time O(n): there are n calls, each doing constant work. Space O(n): up to n stack frames exist at once. The iterative version uses O(1) space.
How many calls does the naive fib(n) make, and how do you improve it?
2·F(n+1) − 1 calls (exponential, about 1.618n). Memoization or a bottom-up loop reduces the time to O(n); matrix exponentiation or fast doubling reduces it to O(log n).
Solve T(n) = 2T(n − 1) + 1, T(0) = 0.
Unrolling: T(n) = 2kT(n − k) + (2k − 1). With k = n, T(n) = 2n − 1. This is the move count for Tower of Hanoi.
Does C++ guarantee tail call optimisation?
No. Compilers may perform it at higher optimisation levels, but the standard does not require it, and things like destructors running after the call can prevent it. Some languages (such as Scheme) guarantee it; C++, Java and Python do not.
What is the difference between direct and indirect recursion?
In direct recursion a function calls itself. In indirect recursion a function calls another function that eventually calls the first one (A → B → A).
Can main() call itself in C++?
No. Unlike C, C++ forbids calling main from within the program, so a recursive main is ill-formed. GCC accepts it as an extension, but -pedantic reports it. Put the recursion in another function instead.
In Simple Words
A recursive function calls itself on a smaller problem. It needs a base case that stops the calls, and every call must move closer to that base case.
Each call gets its own stack frame; recursion depth = extra memory used.
Work done before the call happens on the way down; work after the call happens on the way back up.
Tree recursion (like naive Fibonacci) can repeat work exponentially; memoization fixes it.
Tail recursion can be optimised into a loop, but C++ does not guarantee it.
Use recursion when the problem has a recursive shape; use loops for simple repetition or very deep inputs.