Understanding Recursion

A recursive subroutine, also called a recursive method, is one that calls itself, either directly or indirectly.

Programming

Interactive lab

Try it: The Call Stack

How the call stack keeps track of function calls: each call pushes a frame with its own arguments and local variables, and each return pops it.

How it works

Calling a function pushes a new frame on top of the stack; the caller pauses.
The frame holds that call's parameters and local variables.
When the function returns, its frame is popped and the return value goes back to the paused caller.
A recursive function pushes one frame per call until the base case, then the frames unwind in reverse order.

Default run (17 steps): Program starts: main is about to call factorial(4). … The stack is empty again. Result: 24. Deepest point: 4 frames, 4 calls in total.

Educational simulation

Loading the simulation…

Why Recursion Is a Different Way to Organize Work

Most of the subroutines you have written so far probably do their work and then return control to whoever called them. Recursion is a different way of organizing a subroutine. It is a programming technique in which a subroutine makes use of itself, and this article starts by defining exactly what that means.

Keep one idea in mind as you read: a recursive subroutine can define a complex task in just a few lines of code. Before we see how that works, we need a precise definition of the term. As you go, try to predict what a subroutine that keeps calling itself is doing at each moment, and check your guess against the trace later in this article.

What a Recursive Subroutine Is

Definition

A recursive subroutine, also called a recursive method, is one that calls itself, either directly or indirectly.

The definition has two parts. The first is that the subroutine makes a call to itself. The second is that this self-call can take one of two forms, which the source describes as direct and indirect. Both forms make the subroutine recursive, so the distinction between them matters when you read or write recursive code.

Key point

A subroutine is recursive when some path of calls starts at that subroutine and eventually returns to that same subroutine. The path may be one step long or may pass through other subroutines first.

Tracing a Self-Call with a Countdown

The source does not give a specific program at this point, so the following is a generated, purely descriptive illustration of the pattern. Imagine a subroutine that is given a number. It performs a small task with that number, then calls itself with a smaller number. The new call performs the same kind of task and calls itself again with an even smaller number. Each call is a complete use of the same subroutine, but with different input.

Trace it with the starting number 3. The first use of the subroutine receives 3, does its small task, and makes a self-call with 2. That use is not finished yet: it is now waiting for the call it made. The second use receives 2, does its task, and calls itself with 1, so it now waits too. The third use receives 1 and, in this illustration, makes no further self-call, so it can finish. Control then returns to the use that was waiting for it, and so on back up the chain.

When the subroutine calls itself, where does each pending call wait, and in what order do the calls finish and return?

Worked example

Following the countdown from 3

A recursive countdown subroutine is started with the number 3. Each use does a small task, then calls itself with a number one smaller, until the innermost use makes no further call. In what order do the uses finish?

1
Start the first use
The first use receives 3, does its task, and makes a self-call with 2. It cannot finish yet because it is waiting for that call.
2
Start the second use
The second use receives 2, does its task, and calls itself with 1. It also waits.
3
Start the innermost use
The third use receives 1 and makes no further self-call, so it does its task and finishes.
4
Unwind the waiting uses
The second use resumes after its call returns, finishes, and returns to the first use. The first use then finishes last.

Result

The innermost use finishes first and the first use finishes last. Several uses of the same subroutine were active at the same time, each holding its own input.

Direct and Indirect Recursion

Both forms of recursion satisfy the same definition, and the difference lies in how the calls are arranged. Reading the arrangement tells you which form you are looking at.

Comparing the Two Forms

Feature	Direct recursion	Indirect recursion
Where the self-call appears	Inside the body of the subroutine being defined	Inside a second subroutine, which calls back to the first
Number of subroutines in the cycle	One	Two or more
How to spot it	Read the subroutine's own definition for a call to itself	Follow the calls from one subroutine until the path returns to the start
Source definition used	Calls the subroutine being defined	Calls a second subroutine which in turn calls the first

Direct and indirect recursion both make a subroutine recursive; they differ in how the calls are arranged.

Why a Few Lines Can Cover Many Steps

A recursive subroutine can define a complex task in just a few lines of code. The reason is that the definition is written once, while the subroutine can be active in several nested uses at the same time. In the countdown trace, the same short body ran three times, once for each input. The number of uses depended on the input, not on the number of lines you wrote.

Key point

This is what makes a short recursive definition able to cover a task whose number of steps depends on the input. You do not write a separate copy of the work for each step; the one definition is reused for each smaller piece.

Deciding When a Call Continues or Stops

A self-call on its own does not say when the chain of uses should end. The countdown example only finishes because, at some point, a use receives an input for which it makes no further self-call. Each use has a choice: stop and return, or do its small task and call itself again. The flowchart below shows that decision for the countdown illustration.

On each call, what decides whether the subroutine stops or makes another self-call, and which path leads to termination?

Mistakes Beginners Make with Recursive Definitions

Common mistake
Thinking a recursive subroutine calls a different subroutine each time
What it looks like
Reading the countdown and assuming each use is a new, separate subroutine.
Why it fails
The definition is written once. Each use is a complete use of the same subroutine, but with different input.
Do this instead
Treat each nested use as another active copy of one definition, distinguished by its input.
Common mistake
Assuming only direct recursion counts as recursion
What it looks like
Looking for a subroutine whose body names itself and concluding that a chain of two subroutines is not recursive.
Why it fails
The definition includes indirect recursion, where the subroutine calls a second subroutine which in turn calls the first.
Do this instead
Follow the path of calls. If it starts at a subroutine and returns to it, the subroutine is recursive.
Common mistake
Reading the self-call and skipping the stopping condition
Why it fails
A self-call alone does not say when the chain ends, so the reader cannot tell how the subroutine finishes.
Do this instead
For every recursive definition, identify the input for which the subroutine stops making self-calls.
Common mistake
Believing the number of lines in the code equals the number of steps performed
Common mistake
Trying to trace a whole chain at once instead of one call at a time
What it looks like
Attempting to hold all nested uses in mind without writing down the input for each.
Why it fails
Each use is waiting for the next, so the order of finishing is easy to lose.
Do this instead
Write each use on its own line with its input, then mark which uses are waiting and which finish first.

Practice Tracing a Chain of Uses

EASY

Using the countdown illustration from this article, start a recursive countdown with the number 4. List every use of the subroutine in the order it is started, the input each one receives, and the order in which the uses finish.

Hints

Start with the first use receiving 4 and write down the self-call it makes.
Keep a list of uses that are still waiting; the innermost use finishes first.
Check that your list has four uses, one for each input from 4 down to 1.

Your attempt (not saved)

MEDIUM

Sketch a two-subroutine indirect cycle in which subroutine X calls subroutine Y and subroutine Y calls subroutine X. Label which call is the one that closes the cycle, and explain in one sentence why this counts as recursion under the source definition.