Recursion, Iteration, and Backtracking

Introduction

Many algorithms solve a problem by reducing it to smaller versions of the same problem. This strategy is recursion. Other algorithms repeat steps explicitly with loops; this is iteration. A third class explores alternative choices, undoing unsuccessful choices when necessary; this is backtracking. These techniques are closely related: recursion provides a natural control structure for hierarchical and search problems, iteration often provides lower-overhead execution, and backtracking uses systematic recursion to explore a state space.

In Java and Python, understanding these methods requires more than memorising syntax. A programmer must be able to identify a terminating condition, trace activation records on the call stack, estimate time and space costs, translate recursive logic into an iterative form, and control combinatorial explosion through pruning.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish recursion, iteration, and backtracking;
• formulate valid base cases and recursive cases;
• trace recursive calls and returns;
• analyse time complexity and call-stack space;
• convert suitable recursive algorithms to iterative algorithms;
• design backtracking algorithms using state, choices, constraints, and undo operations;
• apply pruning and state-space search to practical problems;
• implement these ideas safely in Java and Python.

1. Recursion as a Problem-Solving Method

A recursive function calls itself, directly or indirectly, with a smaller or simpler input. A correct recursive design has four properties:

1. A clearly defined problem state. The function’s parameters must describe what remains to be solved.
2. A base case. This is a condition whose answer is known without another recursive call.
3. A recursive case. The function reduces the problem and calls itself on the reduced state.
4. Progress toward termination. Every call must move closer to a base case.

For example, factorial is defined for a non-negative integer n by:

Here n is an integer and the function is applicable only for n ≥ 0. The recursive case reduces n by one. In Python:

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

In Java:

static long factorial(int n) {
    if (n < 0) throw new IllegalArgumentException("n must be non-negative");
    if (n == 0) return 1L;
    return n * factorial(n - 1);
}

The result for 4 is calculated as 4 × 3 × 2 × 1 × 1 = 24. The return phase is important: calls are made first, and multiplication occurs as calls return.

Base Cases and Invariants

A base case must be reachable and must correctly represent the smallest valid input. A missing base case causes infinite recursion until the runtime reports a stack overflow. A base case that is too broad can produce an incorrect result. A useful design question is: “What is the smallest instance for which the answer is immediately known?”

An invariant is a property that remains true during execution. For recursive algorithms, an invariant can describe the meaning of each call. In factorial, factorial(k) always means “the product of all positive integers from 1 through k.” In a recursive array sum, sum(a, i) may mean “the sum of elements from index i to the end.”

2. Tracing the Call Stack

The call stack stores an activation record for every active function call. An activation record normally contains parameters, local variables, the return address, and temporary values. The most recent call is at the top of the stack and returns first.

Consider:

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

For sum_to(3), the calls are:

sum_to(3)
  └─ 3 + sum_to(2)
       └─ 2 + sum_to(1)
            └─ 1 + sum_to(0)
                 └─ 0

The returns occur in reverse order:

sum_to(0) = 0
sum_to(1) = 1 + 0 = 1
sum_to(2) = 2 + 1 = 3
sum_to(3) = 3 + 3 = 6

The maximum stack depth is proportional to n. If each activation record requires constant space, auxiliary stack space is O(n). The mathematical result is not the same as memory usage: although the result is one integer, several calls are simultaneously active.

A recursive algorithm’s stack cost is determined by the maximum number of unresolved calls, not simply by the number of calls made in total. An algorithm may make millions of calls sequentially but use little stack if calls return before the next calls begin; conversely, a long chain of nested calls can exhaust the stack.

3. Recurrence Relations and Complexity

Recursive running time is often expressed by a recurrence. For factorial, one recursive call performs constant additional work:

where c is a constant and n is the input value. Therefore, T(n) = Θ(n). The stack space is also Θ(n).

A binary search recurrence is:

because each step examines one element and discards approximately half the remaining sorted array. Thus its running time is Θ(log n), and a recursive implementation uses Θ(log n) stack space.

A divide-and-conquer merge sort satisfies:

The two recursive subproblems account for 2T(n/2), while merging costs Θ(n). The resulting time complexity is Θ(n log n). Its auxiliary space depends on implementation: a typical array-based implementation uses Θ(n) additional storage for merging, while recursion itself contributes Θ(log n) stack space.

Multiple Recursive Calls

Naive recursive Fibonacci illustrates overlapping subproblems:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

The function repeatedly solves the same subproblems. Its time is exponential in n under the usual unit-cost model, often bounded as Θ(φⁿ), where φ ≈ 1.618 is the golden ratio, while its stack depth is Θ(n). Memoisation stores previously computed values and reduces the time to Θ(n), with Θ(n) additional memory. An iterative version achieves Θ(n) time and Θ(1) additional space.

4. Recursion in Java and Python

The languages differ in runtime behaviour. Python has a deliberately limited recursion depth and does not generally optimise tail calls. Java also has a finite thread stack; excessive recursion can cause StackOverflowError. Consequently, recursion should not be used merely because it is shorter.

A recursive function is appropriate when:

• the data is naturally hierarchical, such as a tree or directory structure;
• the algorithm is naturally divide-and-conquer;
• recursive depth is known to be safe;
• clarity is improved and performance is acceptable.

It is less appropriate when input depth can be very large, when stack memory is constrained, or when a simple loop expresses the algorithm equally clearly.

A particularly useful pattern is recursive traversal of a tree:

def preorder(node):
    if node is None:
        return
    print(node.value)
    preorder(node.left)
    preorder(node.right)

The base case handles an empty subtree. The recursive cases process the left and right subtrees. For a tree with n nodes, traversal takes Θ(n) time because each node is visited once. Stack space is Θ(h), where h is the tree height. For a balanced tree h is Θ(log n); for a degenerate chain h is Θ(n).

5. Iteration and Conversion from Recursion

Iteration uses explicit control structures such as for and while. A recursive algorithm can often be converted by identifying the information that recursion stores implicitly and representing it explicitly in variables or a stack.

Example: Factorial

The iterative factorial uses constant auxiliary space:

def factorial_iterative(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Its time is Θ(n), and auxiliary space is Θ(1), ignoring the space required to store the returned integer. In Java, the corresponding loop is:

static long factorialIterative(int n) {
    if (n < 0) throw new IllegalArgumentException("n must be non-negative");
    long result = 1L;
    for (int k = 2; k <= n; k++) result *= k;
    return result;
}

The long type imposes a range limitation; for larger exact results, Java’s BigInteger or Python’s arbitrary-precision integers are appropriate.

Example: Iterative Binary Search

Recursive binary search carries the current interval through parameters. Iterative binary search stores the same state in local variables:

def binary_search(a, target):
    low, high = 0, len(a) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

The array must be sorted in ascending order according to the comparison used. The expression low + (high - low) // 2 avoids a possible integer-overflow issue in languages with fixed-width integers. The algorithm takes Θ(log n) time and Θ(1) auxiliary space.

Explicit Stacks

For tree traversal, replacing recursion with iteration usually requires an explicit stack:

def preorder_iterative(root):
    if root is None:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return result

The right child is pushed first so that the left child is processed first, because a stack is last-in, first-out. This algorithm has Θ(n) time and Θ(h) auxiliary space in the worst case, where h is represented by the maximum number of pending nodes; for a broad tree this can approach Θ(n).

6. Backtracking and State-Space Search

Backtracking systematically constructs a candidate solution one decision at a time. When a partial candidate cannot lead to a valid complete solution, the algorithm abandons it and reverses the most recent decision.

A backtracking problem can be described using:

• State: the partial solution currently constructed;
• Choices: legal next decisions;
• Constraint: a test determining whether the state remains feasible;
• Goal test: a test determining whether a complete solution has been formed;
• Undo operation: removal of the most recent choice.

The general pattern is:

def search(state):
    if is_complete(state):
        record(state)
        return
    for choice in choices(state):
        if feasible(state, choice):
            apply(state, choice)
            search(state)
            undo(state, choice)

The undo step is essential. If a mutable list is reused, failing to remove a choice causes later branches to contain data belonging to earlier branches.

Backtracking is a depth-first traversal of a state-space tree. If there are b choices at each of d levels, an unpruned upper bound is often O(b^d), although the actual number depends on constraints and varying branching factors. Backtracking does not magically make exponential problems polynomial; pruning reduces the explored portion of the tree.

Permutations

To generate all permutations of n distinct elements, choose an unused element for the next position. There are n! complete permutations, so output alone requires Ω(n!) time if every permutation must be produced. A typical implementation is:

def permutations(items):
    result = []
    used = [False] * len(items)
    current = []

    def search():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, value in enumerate(items):
            if used[i]:
                continue
            used[i] = True
            current.append(value)
            search()
            current.pop()
            used[i] = False

    search()
    return result

For distinct items, the number of leaves is n!. The copying and branch-management overhead means total time is commonly described as O(n × n!) when storing every length-n result. The recursion depth is n, and the working state uses O(n) space, excluding the output.

Pruning

Pruning rejects a state as soon as it violates a constraint. Effective pruning should be:

• correct: never discard a state that could lead to a required solution;
• inexpensive: the test should cost substantially less than exploring the rejected subtree;
• informative: it should significantly reduce branching.

Examples include rejecting a chess placement that attacks an existing queen, stopping subset construction when a partial sum already exceeds a positive target, and using a lower-bound estimate in optimisation search.

7. Worked Application: The N-Queens Problem

Background

The N-Queens problem asks whether n queens can be placed on an n × n chessboard so that no two queens attack one another. A queen attacks along a row, column, or diagonal. The problem is an illustrative case study rather than a claim about a particular production system.

Problem Representation

Place exactly one queen in each row. A partial state can be represented by an array positions, where positions[row] is the column occupied by the queen in that row. Since rows are processed in order, row conflicts are automatically avoided. We need test:

• whether a column is already occupied;
• whether the main diagonal is occupied;
• whether the secondary diagonal is occupied.

For a queen at row r and column c, the main-diagonal identifier can be r − c, and the secondary-diagonal identifier can be r + c. Two cells share a diagonal exactly when their corresponding identifier is equal.

def solve_n_queens(n):
    solutions = []
    positions = [-1] * n
    columns = set()
    diagonals1 = set()       # row - column
    diagonals2 = set()       # row + column

    def search(row):
        if row == n:
            solutions.append(positions.copy())
            return
        for col in range(n):
            d1, d2 = row - col, row + col
            if col in columns or d1 in diagonals1 or d2 in diagonals2:
                continue
            positions[row] = col
            columns.add(col)
            diagonals1.add(d1)
            diagonals2.add(d2)
            search(row + 1)
            columns.remove(col)
            diagonals1.remove(d1)
            diagonals2.remove(d2)
            positions[row] = -1

    search(0)
    return solutions

Analysis

The search depth is n. At the first row there are at most n choices, then at most n − 1, and so on, giving a crude bound of O(n!). The constant-time set checks make pruning efficient. The output requires additional space proportional to the number of solutions; excluding output, the active state and recursion depth are O(n).

For n = 4, one solution is represented as [1, 3, 0, 2]. The queens occupy (row, column) positions (0,1), (1,3), (2,0), and (3,2). No two share a column, and the values of r − c and r + c are all distinct within their respective sets.

Outcome and Learning Points

The case demonstrates that a good state representation can eliminate unnecessary checks. Processing one row at a time removes row conflicts automatically. Sets make constraint checks fast, while the undo phase restores the state for the next branch. The same architecture applies to scheduling, route construction, puzzle solving, configuration generation, and resource allocation.

8. Practical Design and Debugging Guidance

When designing a recursive or backtracking algorithm:

1. Write the meaning of the function in one precise sentence.
2. Identify the smallest valid input and write the base case first.
3. Prove that each recursive call moves toward termination.
4. Trace a small input by hand, including both calls and returns.
5. State the invariant for mutable state.
6. Estimate maximum depth before implementation.
7. Test empty input, one-element input, boundary values, and invalid input.
8. In backtracking, verify that every mutation has a matching undo operation.
9. Separate output storage from working memory when reporting complexity.
10. Convert to iteration if depth may exceed safe stack limits.

Common errors include using n == 1 as the only base case when zero is valid, changing a parameter in the wrong direction, sharing mutable results without copying, forgetting to restore a set or list, and confusing total calls with maximum stack depth.

9. Professional and Contemporary Considerations

Recursive and backtracking code may be used in compilers, interpreters, test-case generators, constraint solvers, graph analysis, and artificial-intelligence search. In AI systems, depth-first search with pruning, heuristic ordering, memoisation, and branch-and-bound are standard ways to manage large state spaces. However, the algorithm must remain explainable: a heuristic should not silently invalidate required solutions, and approximation should be distinguished from exact search.

For production software, resource limits are part of correctness. An algorithm that eventually returns the right answer but exhausts memory is not operationally correct. Developers should document input assumptions, maximum expected depth, time limits, and whether all solutions or only one solution is required. If a search processes user-controlled data, limits may also be needed to reduce denial-of-service risks caused by deliberately difficult inputs.

Chapter Summary

Recursion solves a problem through smaller instances of itself and requires a valid base case, recursive case, and guaranteed progress. Its call stack stores unresolved calls, so maximum recursion depth determines stack usage. Recurrence relations help analyse recursive running time, while tree height and branching structure determine space costs. Iteration often provides the same result with less stack overhead; recursive state can be represented by loop variables or an explicit stack. Backtracking explores a state-space tree by making choices, checking constraints, recursively continuing, and undoing choices. Pruning reduces unnecessary exploration but does not generally remove exponential worst-case behaviour. Effective implementations use precise state representations, safe mutation, correct restoration, and clearly documented complexity and input limits.

Key Terms

Recursion: A method in which a function solves a problem by calling itself on a smaller or simpler state.

Base case: A terminating case whose result is known directly.

Recursive case: The part of a recursive definition that reduces the problem and makes another call.

Call stack: Runtime storage for active function calls.

Activation record: Information associated with one active call, including parameters and local data.

Stack depth: The maximum number of simultaneously active calls.

Iteration: Repetition controlled explicitly by loops or equivalent state transitions.

Invariant: A property that remains true throughout an algorithm or phase of execution.

Recurrence: An equation describing the cost or value of a problem in terms of smaller instances.

Divide and conquer: Solving subproblems independently and combining their results.

Backtracking: Depth-first exploration that reverses a choice when a partial state fails.

State space: The set of possible states reachable through choices.

Constraint: A condition that a valid state must satisfy.

Pruning: Rejecting a state without exploring descendants that cannot produce a valid result.

Memoisation: Storing results of solved subproblems for reuse.

Branching factor: The number of choices available from a state.

Depth-first search: Exploring one branch as far as possible before returning to alternatives.

Branch and bound: Pruning optimisation states using bounds on their best possible outcome.

Auxiliary space: Extra memory used by an algorithm, excluding the required input and output where specified.

Review Questions

Short Answer Questions

1. What are the four essential properties of a correct recursive algorithm?
2. Why can a recursive algorithm use Θ(n) stack space even when it returns a single integer?
3. State one situation in which iteration is preferable to recursion.
4. What is the purpose of the undo operation in backtracking?
5. Distinguish memoisation from pruning.

Long Answer Questions

1. Trace sum_to(4) from the first call through the final return, and explain its time and stack-space complexity.
2. Explain how recursive binary search can be converted into an iterative algorithm. State the required input condition and complexity.
3. Describe the state, choices, constraints, and goal test in the N-Queens problem.
4. Compare recursive tree traversal with traversal using an explicit stack.
5. Explain why naive recursive Fibonacci is inefficient and how memoisation or iteration improves it.

Analytical / Application Questions

1. Design a backtracking algorithm for generating all subsets of a set. Specify its state, choices, base case, and complexity excluding and including output storage.
2. A program recursively processes a linked list containing one million nodes. Analyse the likely stack risk and propose an iterative alternative.
3. For a scheduling problem in which tasks have time conflicts, propose two safe pruning rules and explain why each rule cannot discard a feasible schedule.

Multiple Choice Questions with Answers

Question 1

Which condition is essential for every terminating recursive algorithm?

A. A global variable

B. A reachable base case

C. A sorted input

D. Two recursive calls

Correct Answer: B. A reachable base case

Question 2

What is the time complexity of recursive factorial for n ≥ 0?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: C. Θ(n)

Question 3

What determines the auxiliary stack space of a recursive algorithm most directly?

A. The number of output values

B. The maximum number of simultaneously active calls

C. The size of the source code

D. The number of base cases

Correct Answer: B. The maximum number of simultaneously active calls

Question 4

Binary search is applicable in the chapter’s implementation when the array is:

A. Unsorted

B. Sorted according to the comparison used

C. Circular

D. Strictly decreasing only

Correct Answer: B. Sorted according to the comparison used

Question 5

In iterative preorder traversal, why is the right child pushed before the left child?

A. The right child is always smaller

B. The stack processes the last pushed item first

C. The left child cannot be stored

D. It reduces the tree height

Correct Answer: B. The stack processes the last pushed item first

Question 6

What is the main purpose of pruning in backtracking?

A. To increase the number of explored states

B. To reject states that cannot lead to a valid solution

C. To remove the base case

D. To sort all candidate solutions

Correct Answer: B. To reject states that cannot lead to a valid solution

Question 7

Which operation restores a backtracking algorithm after a choice has been explored?

A. Compilation

B. Memoisation

C. Undo

D. Hashing

Correct Answer: C. Undo

Question 8

For a queen at row r and column c, which pair identifies its two diagonal classes?

A. r + c and r − c

B. r × c and r ÷ c

C. r² and c²

D. r and c only

Correct Answer: A. r + c and r − c

Question 9

What is the time complexity of iterative binary search on a sorted array of n elements?

A. Θ(n²)

B. Θ(n)

C. Θ(log n)

D. Θ(2ⁿ)

Correct Answer: C. Θ(log n)

Question 10

What problem causes naive recursive Fibonacci to be inefficient?

A. It has no parameters

B. It repeatedly solves overlapping subproblems

C. It always uses an explicit queue

D. It cannot have a base case

Correct Answer: B. It repeatedly solves overlapping subproblems