Recursive Algorithms

The Central Idea

A recursive algorithm refers to itself on a smaller problem.

A successful recursive design usually has two essential parts:

1. a base case that can be solved directly;
2. a recursive step that reduces the problem to a smaller instance.

The reduction must eventually reach the base case.

A Simple Recursive Definition

Consider factorial:

It can be defined recursively by

and, for \(n\ge1\),

The value \(n!\) is reduced to a smaller factorial problem.

Base Cases

A base case is a smallest or simplest problem instance that the algorithm solves without making another recursive call.

For factorial, the base case is

Without a base case, recursion has no defined stopping point.

Recursive Cases

The recursive case explains how to solve a larger problem using a smaller instance.

For factorial,

The recursive call uses the smaller input

Each step therefore moves closer to \(0\).

Tracing a Recursive Factorial

To compute

recursion expands as

The base case gives

Returning from the Base Case

Once the base case is reached, the recursive calls return in reverse order.

Recursive computation therefore has both a downward phase and a return phase.

Recursive Reduction

The recursive call must represent genuine progress.

A useful way to think about recursion is:

Replace the current problem with a smaller problem of the same type.

Typical reductions include:

• replace \(n\) by \(n-1\);
• remove one item from a list;
• move to a smaller subtree;
• reduce an interval;
• reduce a number by division.

A Recursive Sum

Let

A recursive definition is

and

Each recursive step removes the final term from the sum.

Tracing the Recursive Sum

For

we obtain

Since \(S(0)=0\),

Recursive Algorithms and Mathematical Recurrence

Recursive algorithms often mirror recurrence relations.

A recurrence such as

describes a term using an earlier term.

A recursive algorithm similarly computes an answer using one or more smaller answers.

Recursive List Processing

Suppose we want to compute the sum of a list

One recursive idea is:

and

The smaller problem is the list with its first entry removed.

Recursive Search in a List

Linear search can also be described recursively.

To search for target \(t\):

1. If the list is empty, report failure.
2. If the first entry equals \(t\), report success.
3. Otherwise search recursively in the remaining list.

This is the same basic logic as iterative linear search expressed through recursive reduction.

Recursive Binary Search

Binary search has a natural recursive form.

For a sorted interval:

1. If the interval is empty, report failure.
2. Inspect the middle entry.
3. If it matches the target, report success.
4. If the target is smaller, recursively search the left half.
5. If the target is larger, recursively search the right half.

Each call operates on a smaller interval.

Recursion on Trees

Trees are naturally recursive structures.

A rooted tree consists of:

• a root;
• zero or more subtrees rooted at its children.

Therefore, an algorithm can process a tree by processing the root and then recursively processing each subtree.

Recursive Depth-First Traversal

A simple recursive depth-first traversal can be described as follows:

1. Visit the current vertex.
2. Mark it visited.
3. For each unvisited neighbor, recursively traverse from that neighbor.

The recursive call automatically follows a branch deeper before returning.

The Call Stack

Each active recursive call must remember information such as:

• its parameter values;
• local variables;
• where execution should resume after the recursive call returns.

These suspended calls are commonly organized in a call stack.

Stack Behavior of Recursive Calls

A stack follows

last in, first out.

If a call to \(F(4)\) invokes \(F(3)\), which invokes \(F(2)\), then the \(F(2)\) call must finish before \(F(3)\) can finish.

This nested structure explains why recursive returns occur in reverse order.

Recursion Trees

When one recursive call produces several smaller calls, the computation can be represented as a recursion tree.

For example, a function satisfying

creates two recursive branches from many calls.

Recursion trees help visualize repeated work and the structure of the computation.

Fibonacci Recursion

The Fibonacci numbers satisfy

and

A direct recursive algorithm can follow this definition exactly.

However, matching a recurrence directly does not automatically produce an efficient algorithm.

Repeated Work in Naive Fibonacci Recursion

To compute \(F_5\), a direct recursive method computes both

and

But the computation of \(F_4\) itself also computes \(F_3\).

Thus the same subproblem may be solved repeatedly.

Later lessons on dynamic programming will show how to avoid this repeated work.

Recursive Correctness

To justify a recursive algorithm, we often use reasoning similar to mathematical induction.

The pattern is:

1. show that the base case is correct;
2. assume recursive calls correctly solve smaller valid instances;
3. show that the current step uses those smaller answers to produce the correct larger answer.

This aligns recursive computation with inductive proof.

Termination Requires Progress

A base case alone is not enough.

The recursive call must move toward that base case.

For example, if

recursively calls

for positive integers \(n\), then the input decreases until it reaches \(0\).

A Progress Measure

A useful termination argument identifies a quantity that:

1. cannot decrease forever;
2. strictly decreases on every recursive call.

Such a quantity is sometimes called a variant or a progress measure.

Examples include:

• the integer \(n\);
• the length of a list;
• the size of an interval;
• the number of unprocessed nodes.

Infinite Recursion

Suppose a procedure for positive integers is defined by

If the intended base case is \(F(0)\), then the recursive step moves in the wrong direction.

Starting at \(n>0\), the input grows instead of approaching \(0\).

The existence of a base case does not help if it is never reached.

Multiple Base Cases

Some recursive procedures require more than one base case.

Fibonacci recursion uses

and

Because the recurrence looks back two positions, two initial values are needed to determine the sequence.

Recursion and Iteration

Many problems can be solved either recursively or iteratively.

Iteration uses explicit repetition such as loops.

Recursion uses function calls on smaller instances.

These are different control structures, but they can often express the same underlying computation.

Iterative Factorial

Factorial can be computed iteratively by maintaining a running product:

Recursive factorial instead uses

Both methods compute the same mathematical function.

When Recursion Is Natural

Recursion is especially natural when the problem contains nested or self-similar structure.

Examples include:

• trees;
• nested expressions;
• recursive sequences;
• divide-and-conquer problems;
• backtracking search;
• hierarchical data.

When Iteration May Be Simpler

If a problem is naturally a straightforward sequence of repeated steps, iteration may be simpler.

For example, summing the integers from \(1\) through \(n\) can be handled directly with a loop.

Recursive elegance does not automatically imply implementation efficiency or simplicity.

Recursive Depth

The recursive depth is the maximum number of active recursive calls at one time.

For factorial computed by decreasing \(n\) by \(1\), the depth grows proportionally to \(n\).

For a procedure that repeatedly halves its input, the depth may grow proportionally to

Stack Space

Each active recursive call generally requires some memory.

Therefore, recursive depth can affect space usage.

A deeply recursive computation may require substantial call-stack space even when each individual call is simple.

Later complexity analysis will distinguish time cost from space cost.

Tail Recursion

A recursive call is in tail position when it is the final operation performed by the current call.

For example, a procedure may pass an accumulated answer into the next recursive call so that no additional computation is needed afterward.

Some programming environments can optimize certain tail-recursive procedures, but such optimization should not be assumed universally.

Recursive Construction

Recursion is not limited to numerical computation.

It can construct objects.

For example, to generate a sequence of \(n\) symbols, a recursive algorithm might:

1. construct a sequence of \(n-1\) symbols;
2. append one additional symbol.

The result is built from a smaller result.

Recursive Decomposition of Strings

A string

can be decomposed into:

• its first symbol \(s_1\);
• the remaining substring \(s_2\cdots s_n\).

This creates a natural recursive structure for tasks such as reversal, searching, and symbol counting.

Recursive String Reversal

Let \(R(s)\) denote the reverse of a string \(s\).

For the empty string,

If

where \(c\) is the first character and \(w\) is the remaining substring, then

Tracing String Reversal

For

we have

Recursive Algorithms Can Have Several Calls

Not every recursive algorithm makes only one recursive call.

Tree algorithms may recursively process several children.

Divide-and-conquer algorithms may split one problem into several subproblems.

Backtracking algorithms may recursively explore several choices.

The number and sizes of recursive calls strongly affect performance.

Structural Recursion

Structural recursion follows the recursive structure of the data itself.

For a tree:

1. process the current node;
2. recursively process each child subtree.

The algorithm terminates because each recursive call moves to a strictly smaller subtree.

Recursion and Structural Induction

Structural recursion and structural induction are closely related.

Structural recursion defines or computes something by following how an object is built.

Structural induction proves a property by showing it holds for basic objects and remains true when larger objects are built from smaller ones.

Both rely on the same recursive organization of structure.

Common Error: Missing a Base Case

A recursive procedure without a base case has no explicit stopping rule.

For example,

is incomplete unless some smallest input is assigned a direct value.

Common Error: Failing to Move Toward the Base Case

Suppose the base case is \(n=0\), but the recursive step sends

Starting from a positive \(n\), the recursion moves away from the base case.

A correct recursive design needs both a stopping condition and guaranteed progress toward it.

Common Error: Changing the Problem Type

The recursive subproblem should normally be the same kind of problem on a smaller input.

If the current problem is "sum this list," the recursive subproblem might be "sum the remaining shorter list."

An unrelated subproblem does not create a useful recursive decomposition.

Common Error: Recomputing the Same Subproblem

A recursive definition may cause repeated calls on identical inputs.

Naive Fibonacci recursion is a standard example.

Repetition may make an otherwise elegant recursive procedure inefficient.

Later dynamic-programming methods will address this issue directly.

Common Error: Ignoring Stack Depth

Recursive algorithms use memory for active calls.

A procedure that makes thousands or millions of nested calls may exhaust available stack space even if its mathematical definition is correct.

Correctness and practical implementation constraints must both be considered.

Common Error: Confusing Recursive Definition with Efficient Algorithm

A recurrence can define a quantity beautifully without providing the most efficient computational method.

The recursive Fibonacci formula

is mathematically natural, but its direct recursive implementation repeats many subproblems.

A Reliable Procedure for Designing Recursion

1. Identify the smallest instances that can be solved directly.
2. Write explicit base cases for those instances.
3. Determine how a larger instance can be reduced to smaller instances of the same problem.
4. Make sure every recursive call moves toward a base case.
5. Specify how smaller answers are combined into the larger answer.
6. Trace a few small inputs by hand.
7. Check termination.
8. Check for repeated work or excessive recursive depth.

Example: Recursive Power

For a number \(a\) and nonnegative integer \(n\), define

and

Thus,

Example: Recursive Greatest Common Divisor

The Euclidean algorithm has a recursive form.

For \(a\ge b>0\),

The base case is

Each recursive call reduces the second argument.

Tracing Recursive GCD

Compute

Since

we obtain

Then

and

Practice 1: Identify the Base Case

For the recursive definition

identify the base case.

Practice 2: Trace Factorial

Use

and

to compute \(5!\).

Practice 3: Recursive Sum

Given

compute \(S(5)\).

Practice 4: Termination

A recursive procedure has base case \(F(0)\) and recursive rule

for even positive integers \(n\).

Explain why the procedure terminates on every even nonnegative input.

Practice 5: Find the Error

A procedure is intended to reach the base case \(G(0)\), but for \(n>0\) it calls

What is wrong?

Practice 6: Recursive List Sum

Suppose

and

Compute

Practice 7: Recursive String Reversal

Using

reverse

Practice 8: Recursive Depth

A procedure starts with positive integer \(n\) and recursively calls itself with \(n-1\) until \(0\).

How does the maximum recursive depth grow as \(n\) increases?

Practice 9: Recursion on a Tree

Explain why recursively processing each child subtree is guaranteed to move toward termination in a finite rooted tree.

Practice 10: Repeated Work

Why can the direct recursive computation of Fibonacci numbers be inefficient?

Practice Answers

Practice 1

The base case is

Practice 2

Practice 3

Practice 4

Each recursive call reduces an even positive input by \(2\):

Because a nonnegative even integer cannot decrease by \(2\) forever, the sequence eventually reaches

the base case.

Practice 5

The recursive call moves away from \(0\) rather than toward it. Starting from a positive input, the base case will never be reached.

Practice 6

Practice 7

Practice 8

The recursive depth grows linearly with \(n\), because each call decreases the input by only \(1\).

Thus the depth is proportional to

Practice 9

Each child subtree contains fewer nodes than the entire tree. Repeatedly moving to child subtrees eventually reaches leaves, which have no child subtrees to process.

Practice 10

Direct Fibonacci recursion repeatedly computes the same subproblems. For example, \(F_{n-2}\) may be computed independently in several branches of the recursion tree.

What to Remember

• A recursive algorithm solves a problem using smaller instances of the same problem.
• Every recursive design needs one or more base cases.
• Recursive calls must make measurable progress toward a base case.
• Active recursive calls are commonly managed by a call stack.
• Recursive correctness often mirrors mathematical induction.
• Recursive structure is especially natural for trees, lists, strings, and recurrence-defined problems.
• Recursion and iteration can often express the same computation.
• A mathematically natural recursive definition is not automatically an efficient algorithm.

The most important habit is to ask two questions: What is the base case, and why must every recursive call eventually reach it?

Where We Go Next

Recursion gives us a general mechanism for reducing problems to smaller instances. Another important design strategy makes a sequence of locally attractive choices in the hope of constructing a globally useful solution.

The next lesson, Greedy Methods, develops locally optimal choices, greedy construction, exchange reasoning, and the conditions under which greedy decisions succeed or fail.