Recursion Step by Step With the Call Stack

Recursion is the idea that breaks the most beginners. A function that calls itself sounds like a trap. Will it run forever? Where does the answer even come from?

Here is the secret. Recursion is not magic. It is just a stack of paused work. Once you can see that stack grow and shrink, the whole thing clicks.

What is recursion?

Recursion is when a function solves a problem by calling itself on a smaller piece of that same problem. Each call handles one small step. Then it hands the rest down to another copy of itself.

Think of it like a set of nesting boxes. To open the biggest box you open the one inside it. To open that one you open the next. You keep going until you reach the smallest box, which is empty. That smallest box is the part that stops the chain.

Every recursion needs that stopping point. Without it the function would call itself forever. So recursion is really two things working together. A step that shrinks the problem and a point where the shrinking stops.

How does recursion work step by step?

Reading the definition is not enough. You have to watch the calls stack up. So let’s trace one real example using the computer’s call stack.

We will compute the factorial of 4, written as factorial(4). A factorial multiplies every whole number from 1 up to that number. So factorial(4) is 4 times 3 times 2 times 1, which equals 24.

The call stack is a pile of paused functions. When a function calls another, the first one pauses and the new one goes on top. The computer always works on whatever sits at the top of the pile.

Watch the calls go down. factorial(4) cannot finish yet, because it needs factorial(3) first. So factorial(3) goes on the stack. But factorial(3) needs factorial(2). And factorial(2) needs factorial(1). Now four calls are stacked, each one paused and waiting on the one below it.

factorial(1) is the bottom. It does not call anything. It just returns 1, because the factorial of 1 is 1. This is the moment the chain stops going down.

Now watch the answers climb back up. With factorial(1) done as 1, factorial(2) can finish. It returns 2 times 1, which is 2. That lets factorial(3) finish as 3 times 2, which is 6. Finally factorial(4) finishes as 4 times 6, which is 24.

The base case and the recursive case

Every recursive function has two parts. Get both right and it works. Miss one and it breaks.

The base case is the stopping point. It is the simplest version of the problem, the one you can answer with no more calls. For factorial, the base case is factorial(1), which is just 1. The base case is what lets the stack stop growing and start unwinding.

The recursive case is the part that calls itself on a smaller input. For factorial it is n times factorial(n minus 1). Each call must move closer to the base case. If it does not, the function never stops. That bug is called infinite recursion, and it crashes the program.

Recursion code in Python and C++

Here is the factorial in Python. Notice how short it is. The two parts map straight onto the two lines.

def factorial(n):
    if n == 1:            # base case
        return 1
    return n * factorial(n - 1)   # recursive case

The first line is the base case. The second line is the recursive case. There is no loop anywhere, yet it still walks through every number from n down to 1.

Here is the same function in C++, which is the language most Indian placement tests use.

int factorial(int n) {
    if (n == 1)           // base case
        return 1;
    return n * factorial(n - 1);   // recursive case
}

The shape is identical. A check for the base case, then a return that calls the function again on a smaller value. That pattern is the heart of every recursive solution you will ever write.

What is the time and space cost of recursion?

Recursion is clean to read, but it is not free. factorial(n) makes n calls, so it runs in O(n) time. That part matches a normal loop.

The real cost is memory. Each waiting call takes a slot on the call stack, so factorial(n) holds n frames at its deepest point. That makes the space O(n). A loop doing the same job would use a single fixed amount of memory, which is O(1).

This memory cost has a hard limit. The stack is not endless. When recursion goes too deep, the program runs out of stack space and crashes. That crash is the famous stack overflow. Python, for example, stops at about 1,000 nested calls by default and raises an error. So a recursion that should run a million levels deep will not survive as plain recursion.

You can check the formal definition on Wikipedia’s recursion page.

Recursion vs iteration

Recursion and iteration can solve the same problems. A loop repeats work using a counter and a fixed bit of memory. Recursion repeats work by stacking calls. For something like factorial, a loop is faster and lighter. But for problems that branch, like walking a tree or a divide and conquer sort, recursion reads far cleaner and matches the shape of the data. For the full comparison, read our recursion vs iteration guide.

FAQ

What is a base case in recursion?

It is the condition that stops the calls. The base case is the simplest input you can answer with no further recursion, like factorial(1) returning 1. Without it the function calls itself forever.

Why does recursion cause a stack overflow?

Each pending call takes a slot on the call stack. If the recursion goes too deep, the stack runs out of room and the program crashes. A missing or wrong base case is the usual reason.

Is recursion faster than a loop?

Usually no. Recursion adds the overhead of pushing and popping stack frames, and it uses more memory. A loop doing the same work is often faster. Recursion wins on clarity for problems that branch, not on raw speed.

Can every recursion be rewritten as a loop?

Yes. Any recursive function can be turned into an iterative one, sometimes with the help of your own stack. The two approaches are equally powerful. The choice is about which one reads more clearly for the problem.

What is infinite recursion?

It is recursion that never reaches its base case, so it calls itself without stopping. It runs until the stack overflows and the program crashes. Always make sure each call moves closer to the base case.

When should I use recursion?

Reach for it when the problem is naturally nested, like trees, graphs, or divide and conquer algorithms. For simple counting or summing, a loop is the better fit.

So what should you remember?

Recursion is a function that trusts a smaller copy of itself to do part of the job. The calls stack up on the way down. The answers build back up on the way out.

Once you can picture that stack growing and shrinking, recursion stops being scary and starts being a tool. The base case is your safety net. Never write a recursion without one.

Now try tracing factorial(5) on paper. How many frames sit on the stack before the first answer comes back?