Recursion Explained

how recursion works

A function that calls itself sounds like a loop with no exit, but how recursion works is simple: every call gets its own frame on the call stack, and a base case stops the chain so the answers can come back.

This explainer traces one small function by hand, then breaks it on purpose. It sits with the other programming essays on this site, which look at how code behaves underneath the syntax.

A function that calls itself, and nothing more mysterious

In its simplest form, a recursive function is one that calls itself, as freeCodeCamp’s flowchart walkthrough puts it. The misleading picture is a loop spinning forever. The accurate picture is a problem handed to a smaller copy of itself, plus a stopping rule that says when the smallest copy can answer directly.

Most confusion comes from imagining all those copies running at once. They do not. One call runs, pauses while it waits for the call it made, and resumes only when that call hands back a value. Seeing where the paused calls wait is the whole trick, and that place is the call stack.

The call stack: how a recursive function actually runs

Each time code makes a function call, Python puts information about that call on the call stack, according to Rensselaer Polytechnic Institute’s recursion lecture notes. The entry holds all values of the parameters and local variables, plus the location of the call. Here, a frame means one such entry.

Sheets pinned in rows with boxes, arrows and handwritten notes: the same habit works for a stack trace, with one box per frame and an arrow for each return.

When a function ends, Python looks at the top of the stack and restores the caller’s values. The top entry is removed and the return value is inserted into the caller’s code. That is the entire mechanism behind recursion: frames pile up on the way down and are removed one at a time on the way back.

Because every call has its own frame, every call also has its own variables. Notice how each call to the factorial function has its own copy of x, as the freeCodeCamp walkthrough observes. That is why a recursive function can call itself with a different input without overwriting the value its caller is still waiting to use.

Colour-highlighted if/else blocks on a dark screen. A base case takes this shape, a condition that decides between answering now and calling again, though the code shown is not itself recursive.
Common belief What actually happens Planning use
A base case is an optional safeguard. Every recursive function definition needs at least one base case, the part that does not recurse. Write the base case before the recursive step.
Recursion is faster than a loop. There is no performance benefit to recursion, and each call carries hidden overhead, so an iterative version is often more efficient. Choose recursion for clarity, not speed.
All calls share one variable. Each call has its own copy of its variables in its own frame. Track each call’s values separately when tracing.

The first and third rows come from the RPI lecture notes and the performance row from both those notes and freeCodeCamp. With the stack in mind, a hand trace becomes mechanical.

Tracing factorial(4) by hand

The RPI notes list hand-simulating the call stack, with factorial and n=4 as the case, as a way to check your understanding. The factorial is a good subject because its definition already refers to itself: n! = n·(n−1)!, with 0! = 1. The factorial is now defined in terms of itself, but on a smaller number.

Here is the function as it would be written in Python.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n – 1)

To trace factorial(4), draw the stack on paper and work through these steps in order.

A hand-drawn flowchart with boxes and arrows on a whiteboard; the handwriting is too small to read.
  1. Record the first frame. Write factorial(4) at the bottom with n=4 and a note of where its answer must go.
  2. Push the next call. Because n is not 0, the frame cannot multiply yet. It needs factorial(3), so draw a new frame above it with its own n.
  3. Keep stacking. Repeat for factorial(2), factorial(1) and factorial(0), each frame sitting on top of the one waiting below it.
  4. Stop at the base case. In factorial(0), n equals 0, so the function returns 1. This is the only frame that answers without calling anything.
  5. Unwind. Remove the top frame and insert its return value into the frame beneath. That frame multiplies by its own n and returns in turn, until the bottom frame delivers the final answer.

The same shape appears in a plain sum. GeeksforGeeks’ introduction to recursion shows sum(3) calling sum(2) and sum(2) calling sum(1), with the calls stacked before any adding happens. The results are then added back in reverse: sum(1) = 1, sum(2) = 3, sum(3) = 6.

When your trace disagrees with what the program prints, the mistake is nearly always in a frame’s own value of n or in a return that was inserted into the wrong caller. Redraw that frame rather than the whole stack.

Rerunning it with the base case removed

Now delete the stopping rule and keep only the recursive line.

def factorial(n):
    return n * factorial(n – 1)

Trace it the same way. factorial(4) calls factorial on a smaller value again and again. Nothing special happens at the base case any more, so the calls keep going into negative values. No frame ever returns a value, so no frame is ever removed, and the unwinding step never begins.

As W3Schools’ Python recursion tutorial explains, without a base case the function would call itself forever, causing a stack overflow error. GeeksforGeeks adds that the problem may arise whether the base case is not defined or simply never reached. A base case that exists but is skipped by the input fails in exactly the same way.

Python does not let the stack grow without limit. It has a built-in recursion limit, which W3Schools says is usually around 1000 recursive calls. You can read the current setting with sys.getrecursionlimit(). When the limit is exceeded, Python raises an error reporting that the maximum recursion depth was exceeded, shown in Python 101’s recursion chapter as a RuntimeError.

Treat that error as a symptom. The RPI notes name the cure: infinite recursion is avoided by ensuring that progress is made toward the base case in every recursive call. Fix the stopping rule or the shrinking step rather than hunting for ways around the limit.

Writing recursive function examples of your own

The RPI guidelines for writing a recursive function come down to two instructions: define the base case or cases, and make sure the code is proceeding toward the base case in every step. Everything else follows from the trace you just did.

  • Name the base case first. Decide the smallest input that can be answered directly. For factorial that is n equal to 0, which returns 1.
  • Make the input shrink. The recursive call must pass a smaller value, such as n − 1. A call that passes the same value, or a larger one, never gets closer to the stop.
  • Let each frame do one job. A frame handles its own piece and combines it with what the smaller call returns, as the factorial frames multiply by their own n.
  • Trace one small input before trusting it. Run the stack on paper with a tiny value and confirm that one frame reaches the base case.
A laptop with an editor open and a row of application icons along the bottom of the screen. The code shown is stylesheet-style, so the factorial above is the working example here.

These rules apply beyond factorial. Many problems fit the same pattern, with a base case and a smaller copy of the problem, and the stack frames behave identically.

When a loop is the better choice

Choose a loop when the task is a plain repeat and speed or stack depth matters. The RPI notes say a recursive function can often, and should, be replaced by a non-recursive, iterative function that is significantly more efficient. The freeCodeCamp walkthrough agrees that recursion carries no inherent performance benefit.

  • Choose a loop for simple counting or accumulating. A loop creates no stack of waiting frames, so it cannot run into Python’s recursion limit.
  • Choose recursion when the definition is recursive. If the problem is naturally stated in terms of a smaller version of itself, as the factorial is, the code can mirror the definition directly.
  • Choose recursion for readability once the pattern is familiar. The main purpose of the recursive approach, per freeCodeCamp, is that it can be clearer once you understand it.
  • Prefer the loop when readers are unlikely to follow a trace. If the recursive version needs a stack diagram to be understood, that clarity benefit is gone.

In short, recursion is a style choice with real costs, not an upgrade. Use it where the shape of the problem rewards it.

Where to go next

If tracing a stack appealed to you, how does git merge work opens another everyday tool to look inside. For a language built around functions, see what is lisp programming language.

Frequently asked questions

Question Answer
Can a recursive function have more than one base case? Yes. A definition needs at least one base case, and the RPI guidelines speak of defining the base case or cases, with progress made toward them in every call.
Can recursion process a list? Yes. According to W3Schools, recursion can process lists by handling one element at a time, with each call dealing with one element and recursing on the rest.
Is the Fibonacci sequence a recursive example? It is a common one. Each new value is obtained by adding the two previous values, giving 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, so each term is defined from earlier terms.
What does a recursive function return when the base case is reached? It returns a value without calling itself, such as 1 when n equals 0 in the factorial. That value is then inserted into the waiting caller as the stack unwinds.