What is recursion?

You can print the numbers from 3 down to 1 with a loop. Recursion does the same job in a different way: a function that hands a smaller copy of the job to itself.

Most learners get lost here because the work is hidden. Calls wait in memory and come back in an order that surprises you. This lesson makes that waiting visible.

The idea: hand a smaller job to yourself

Picture a long queue at a ticket counter. You want to know your place in it, but you can only talk to the person in front of you.

1. You ask the person in front: "What is your place?"
2. They do not know either, so they ask the person in front of them. The same question travels to the front.
3. The first person needs nobody: "I am number 1."
4. The answers travel back. Each person adds 1 and passes it on.

That is recursion. Every recursive function has two parts:

• The base case: the smallest input. The function answers it directly, with no call. Here, the first person in the queue.
• The recursive case: the function calls itself on a smaller input. Here, "ask the person in front".

JavaPythonTypeScript

void countdown(int n) {
    if (n <= 0) return; // base case: nothing left to print
    System.out.println(n);
    countdown(n - 1); // the same job, one smaller
}

// countdown(3) prints 3, 2, 1

• The first line is the base case. When n reaches 0, the function returns and stops calling.
• countdown(n - 1) is the recursive case. Each call has a smaller n, so the calls move toward the base case.

The call stack: calls that wait

When countdown(3) calls countdown(2), the first call is not finished. It pauses at that line and waits for the inner call to return.

Java, Python and JavaScript all keep each waiting call on the call stack. Each call gets its own box, called a stack frame, with its own copy of n.

┌───────────────────────────────────────────────┐
│                                               │
│                     ┌───┐                     │
│                     │ 0 │                     │
│               ┌───┐ ├───┤ ┌───┐               │
│               │ 1 │ │ 1 │ │ 1 │               │
│         ┌───┐ ├───┤ ├───┤ ├───┤ ┌───┐         │
│         │ 2 │ │ 2 │ │ 2 │ │ 2 │ │ 2 │         │
│   ┌───┐ ├───┤ ├───┤ ├───┤ ├───┤ ├───┤ ┌───┐   │
│   │ 3 │ │ 3 │ │ 3 │ │ 3 │ │ 3 │ │ 3 │ │ 3 │   │
│   └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘   │
│   push  push  push  push   pop   pop   pop    │
│     3     2     1     0     0     1     2     │
│                                               │
└───────────────────────────────────────────────┘

Read the picture from left to right:

• Winding down (moments 1 to 3). Each call pushes a new frame on top and runs. It prints its n, calls countdown(n - 1) and pauses there.
• The turn (moment 4). countdown(0) is on top. It hits the base case and returns without calling.
• Unwinding (moments 5 to 7). Frame 0 pops, so countdown(1) is on top again. It goes on from the line where it paused, has nothing left to do, and returns. The same happens to 2, then to 3.

Frames pop newest first. This is the stack you already know: last in, first out.

No base case: the stack overflows

Remove the base case and nothing stops the calls:

JavaPythonTypeScript

void forever(int n) {
    forever(n - 1); // no base case
}

// forever(5) crashes

Each call pushes a frame, and no frame ever pops. The stack has a fixed amount of room, so the program crashes.

This crash is a stack overflow. Each language names it in its own way. We ran forever(5) in all three:

Python stops early on purpose. It counts the frames and raises RecursionError when the count reaches its recursion limit, 1,000 by default. Firefox names the JavaScript crash InternalError: too much recursion.

A base case that the input never reaches is as bad. With n == 0 as the base case, the call countdown(-1) goes to −2, −3 and on, and crashes. That is why the code above uses n <= 0.

Where the line goes decides the order

Move one line, and the output flips. Compare these two:

JavaPythonTypeScript

void countdown(int n) {
    if (n <= 0) return;
    System.out.println(n); // before the call
    countdown(n - 1);
}

void countUp(int n) {
    if (n <= 0) return;
    countUp(n - 1);
    System.out.println(n); // after the call
}

countdown and countUp (count_up in Python) make the same calls and push the same frames as in the picture above. Walk through those seven moments and note when each one prints:

The calls are the same in both. Only the moment of printing changes:

• A line before the call runs while the stack winds down. The biggest n prints first.
• A line after the call runs while the stack unwinds. countUp(3) cannot print until countUp(2) has finished, so 1 prints first.

Striver's videos call the second style "backtracking", because the work happens on the way back. The full backtracking pattern comes later in the course.

The recursion tree, and what recursion costs

You do not need to draw every frame. A recursion tree shows each call as one node, with lines to the calls it makes. In the trees below, the number n stands for the call with n.

┌────────────────────────────────────────────┐
│                                            │
│                                            │
│                     3                      │
│                     │                      │
│                     2                      │
│                     │                      │
│                     1                      │
│                     │                      │
│                     0                      │
│                                            │
│                                            │
└────────────────────────────────────────────┘

┌────────────────────────────────────────────┐
│                                            │
│                                            │
│                                            │
│                      3                     │
│                   ┌──┴──┐                  │
│                   2     1                  │
│                 ┌─┴─┐                      │
│                 1   0                      │
│                                            │
│                                            │
│                                            │
└────────────────────────────────────────────┘

The tree answers both cost questions:

• Time is the number of nodes times the work in one call.
• Space is the height of the tree: the most frames on the stack at one moment.

For countUp(n) the tree is a straight line. There are n + 1 calls, and each one does O(1) work, so time is O(n). The stack reaches n + 1 frames, so space is O(n).

That second row surprises people. The recursion creates no array, yet it uses O(n) memory. The call stack is hidden memory, and it counts.

For a chain, nodes and height are the same. When a call makes two calls, the tree branches.

Then it has many more nodes than levels, and time grows much faster than space. Many calls at once: Fibonacci counts that tree.

How to write one: three questions

Do not trace every call in your head. Answer three questions instead:

1. What is the smallest input I can answer at once? That is the base case.
2. How do I make the input smaller? Subtract one, move an index, cut it in half.
3. If the smaller call already works, what is left for this call? Trust the smaller call, and write only this call's job.

For countdown: the base case is n ≤ 0. The smaller input is n − 1. This call's job is to print n before it hands over.

The third question is the hard one. Tracing calls helps you check a solution. Trusting the smaller call is how you write one.

How to spot recursion in a problem

take U forwardYouTube

Read more

• Recursion in the MDN glossary, with JavaScript examples
• Call stack in the MDN glossary, how the engine tracks calls
• sys.setrecursionlimit in the Python docs, the recursion limit and why raising it is risky
• Re 2. Problems on Recursion by Striver, printing 1 to N and N to 1 step by step

Next: two ways to carry an answer through recursion, by passing it down or by returning it up.