When I first heard about recursion, I found it a little confusing.

A function calling itself? How does that even work?

The easiest way to understand recursion is to remember this simple definition:

Recursion is a programming technique in which a function calls itself repeatedly until a specified condition is met.
That specified condition is called the base case.

Let's understand recursion step by step using some simple C++ examples.

What is Recursion?

In simple words, recursion happens when a function calls itself.

The function keeps calling itself until it reaches a condition that tells it to stop. This stopping condition is called the base case.

So, a recursive function generally has two important parts:

  1. Base Case: The condition that stops the recursion.

  2. Recursive Case: The part where the function calls itself again.

Let's understand this with an example.

Example: Using a "count" Variable

Consider this C++ program:

include

using namespace std;

int count = 0;

void f() {
if (count == 3) {
return;
}

cout << count << endl;
count++;

f();

Enter fullscreen mode Exit fullscreen mode

}

int main() {
f();
return 0;
}

The output will be:

0
1
2

Let's understand exactly what happens.

Step 1: The Initial Call
At the beginning, we have:

int count = 0;

Then we call:

f();

So the function starts executing.

The first thing it checks is:

if (count == 3) {
return;
}

Currently, "count" is "0".

So the condition "count == 3" is false, and the function continues.

It prints the current value of "count":

cout << count << endl;

So we get:

Then we increase "count":

count++;

Now "count" becomes "1".

After that, the function calls itself:

f();

This is the recursive call.

Step 2: The Function Calls Itself

Now the new call to "f()" starts executing.

The value of "count" is now "1".

Again, the function checks:

if (count == 3)

The condition is false because "count" is "1".

So it prints:

1

Then "count++" changes the value of "count" from "1" to "2".

After that, "f()" calls itself again.

Step 3: Another Recursive Call
Now "count" is "2".

The function checks:

if (count == 3)

Again, the condition is false.

So it prints:

2

Then:

count++;

changes "count" from "2" to "3".

After that, the function calls itself one more time.

*Step 4: The Base Case is Reached
*
Now we enter "f()" with:

count = 3

The function checks:

if (count == 3) {
return;
}

This time the condition is true.

So "return" is executed, and the function stops making further recursive calls.

This is called the base case.

Therefore, in our program:

if (count == 3) {
return;
}

is the base case.

The complete flow is simply:

count = 0 -> print 0 -> count becomes 1 -> call f()
count = 1 -> print 1 -> count becomes 2 -> call f()
count = 2 -> print 2 -> count becomes 3 -> call f()
count = 3 -> base case reached -> return

So the final output is:
0
1
2

What is the Call Stack?

Now comes one of the most important concepts in recursion: the call stack.

Whenever a function is called, information about that function call is stored in a special area of memory called the call stack.

Every time our recursive function calls itself, a new stack frame is created for that function call.

Let's follow our example.

First, "f()" is called with "count = 0".

A stack frame is created for that function call.

Then "f()" calls itself with the current value of "count" being "1". Another stack frame is added.

Then another call happens with "count = 2".

Finally, another call happens with "count = 3".

At this point, the call stack has multiple active function calls waiting for the function above them to finish.

You can imagine the calls like this:

f(count = 0)
f(count = 1)
f(count = 2)
f(count = 3)

The important thing to understand is that these earlier function calls have not completely finished yet. They are waiting because each one called another "f()".

When "count" becomes "3", the base case is reached and that function call returns.

Now the previous function calls can also return one by one.

This process is called stack unwinding.

LIFO: Last In, First Out

The call stack follows a principle called LIFO.

LIFO means:

«Last In, First Out»

Think about a stack of plates.

If you put one plate on top of another, the last plate you put on the stack will be the first plate you take out.

The call stack works in a similar way.

In our example, the function calls happen in this order:

f(count = 0)
f(count = 1)
f(count = 2)
f(count = 3)

The last function call added was:

f(count = 3)

So this function call returns first.

Then:

f(count = 2)

returns.

Then:

f(count = 1)

returns.

Finally:

f(count = 0)

returns.

So the return order is the reverse of the call order:

f(count = 3) → return
f(count = 2) → return
f(count = 1) → return
f(count = 0) → return

This is LIFO — Last In, First Out.

The Call Stack: Going Down and Coming Back Up

One way I find recursion easier to understand is by thinking about it in two phases.

Phase 1: Going Down

First, the function keeps calling itself.

In our example:

f(0)
f(1)
f(2)
f(3)

At this point, the base case is reached.

During this phase, new function calls are continuously added to the call stack.

Phase 2: Coming Back Up

Once the base case is reached, the recursive calls start returning.

The return happens in reverse order:

f(3) returns
f(2) returns
f(1) returns
f(0) returns

The call stack starts becoming smaller as each function call finishes.

This process is called stack unwinding.

So, the base case is basically the point where the recursion stops going deeper and the function calls start returning.

What Happens If There Is No Base Case?

Now let's look at another example.

include

using namespace std;

void print() {
cout << 1 << endl;
print();
}

int main() {
print();
return 0;
}

Here, the function "print()" prints "1" and then immediately calls itself again.

There is no condition that tells the function when to stop.

So the function keeps doing this:

print() → print() → print() → print() → ...

The output keeps printing:

1
1
1
1
1
1
...

This is called infinite recursion.

What Happens to the Call Stack During Infinite Recursion?

Remember that every function call creates a new stack frame.

The first call to "print()" creates one stack frame.

Then that function calls "print()" again, so another stack frame is created.

The new function calls "print()" again, creating another stack frame.

This continues again and again.

The call stack keeps growing because the previous function calls are still waiting for the newer calls to finish.

Since there is no base case, the recursion never stops.

Eventually, the available stack memory becomes full.

This is called a stack overflow.

The program may then crash. In C++, depending on the operating system and runtime environment, this can commonly result in a segmentation fault (SIGSEGV) or another runtime error.

The whole process can be understood like this:

Infinite Recursion
↓
Function keeps calling itself
↓
A new stack frame is created each time
↓
Call stack keeps growing
↓
Stack memory is exhausted
↓
Stack Overflow
↓
Possible Segmentation Fault / Program Crash

Why Is the Base Case So Important?

The base case prevents recursion from continuing forever.

Let's compare our two examples.

In the first example:

void f() {
if (count == 3) {
return;
}

cout << count << endl;
count++;

f();

Enter fullscreen mode Exit fullscreen mode

}

The value of "count" eventually reaches "3".

The condition becomes true:

count == 3

So:

return;

is executed.

The recursive calls stop, the call stack unwinds, and the program finishes normally.

In the second example:

void print() {
cout << 1 << endl;
print();
}

There is no base case.

The function keeps calling itself forever.

The call stack keeps growing until a stack overflow occurs, which may cause the program to crash or produce a segmentation fault depending on the environment.

Recursion in One Simple Flow

The basic process of recursion is:

Function starts
↓
Check the base case
↓
If base case is true → return
↓
Otherwise, execute the recursive case
↓
Function calls itself
↓
A new stack frame is created
↓
Check the base case again

If the base case is eventually reached, the recursive calls start returning and the call stack unwinds in LIFO order.

If the base case is never reached, the function keeps creating new stack frames until the call stack runs out of available memory, resulting in a stack overflow.

Final Takeaway

Recursion may look complicated at first, but the basic idea is actually simple:

«Recursion is when a function calls itself until a specified condition, called the base case, is met.»

To understand recursion, remember these four concepts:

  1. Recursive Call

The function calls itself.

f();

  1. Base Case

The condition that tells the recursion to stop.

if (count == 3) {
return;
}

  1. Call Stack

Every function call creates a stack frame. During recursion, each new recursive call adds another stack frame to the call stack.

  1. LIFO

The call stack follows Last In, First Out.

The last function call added to the stack is the first one to return.

And one final rule is very important:

«A recursive function should have a reachable base case and should make progress towards that base case.»

Otherwise, you may get infinite recursion. The call stack will continue to grow, eventually causing a stack overflow and potentially a segmentation fault or program crash.

Hope you understood base cases, recursive calls, the call stack, and LIFO concept :).