Back to series
· 7 min read

Recursion vs. Iteration


I. Basic Concepts of Recursion and Iteration

1. Recursion

Recursion means that a function directly or indirectly calls itself during execution, gradually solving the original problem by breaking it into smaller subproblems and combining the results.

Recursion usually contains two essential components:

  • Recursion termination condition (Base Case): Defines when a problem can be solved directly, preventing infinite calls.
  • Recursive relation (Recursive Case): Converts the current problem into a smaller problem of the same kind.

For example, calculating a factorial:

n! = n \times (n-1)!

where:

0! = 1

Python implementation:

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

    return n * factorial(n - 1)

print(factorial(5))  # 120

The function calls itself to decompose the factorial problem step by step until it reaches the termination condition.

2. Iteration

Iteration means repeatedly executing a section of code through a loop structure and updating state on each iteration until an exit condition is met.

Common iteration structures:

  • for: Iterates over a specified range or iterable.
  • while: Continues executing while a condition is met.
  • do-while: Executes once first, then checks whether to continue; supported by some languages.

Calculating a factorial:

def factorial(n):
    result = 1

    for i in range(1, n + 1):
        result *= i

    return result

print(factorial(5))  # 120

Iteration stores intermediate results in variables and does not require repeatedly calling a function.

3. Key Differences

Comparison Dimension Recursion Iteration
Implementation approach The function repeatedly calls itself A loop structure repeatedly executes
State storage Usually relies on the call stack Usually uses variables or data structures
Termination method Recursive termination condition Loop exit condition
Space overhead Usually related to recursion depth Usually can maintain constant extra space
Code structure Suitable for expressing divide-and-conquer and hierarchical relationships Suitable for expressing repeated state updates
Performance characteristics May incur function call overhead Usually easier to control overhead
Typical scenarios Tree traversal, divide-and-conquer, backtracking Array traversal, counting, state updates

Note that recursion and iteration are ways of expressing algorithms, not two completely different computational capabilities. Many recursive algorithms can be converted into iterative algorithms, and vice versa.

II. Execution Principles of Recursion

The most important underlying mechanism of recursion is the function call stack.

For each function call, the runtime needs to maintain the execution state of the current call, such as:

  • Parameter values.
  • Local variables.
  • Return address.
  • Temporary computation results.
  • Saved register information and other call state.

This information is usually managed by a call stack frame or other runtime mechanisms.

2.1 The Recursive Call Process

Take the factorial function as an example:

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

    return n * factorial(n - 1)

Call:

factorial(4)

Recursive call relationships:

flowchart TD
    A["factorial(4)"] --> B["4 × factorial(3)"]
    B --> C["3 × factorial(2)"]
    C --> D["2 × factorial(1)"]
    D --> E["1 × factorial(0)"]
    E --> F["Termination condition met"]
    F --> G["Return 1"]
    G --> H["Return 1 × 1 = 1"]
    H --> I["Return 2 × 1 = 2"]
    I --> J["Return 3 × 2 = 6"]
    J --> K["Return 4 × 6 = 24"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style H fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style I fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style J fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style K fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

Recursive execution is divided into two phases:

  1. Recursive descent phase: keep calling itself until the termination condition is met.
  2. Recursive unwinding phase: begin returning from the deepest call, completing the pending operations layer by layer.

These two phases correspond to pushing onto and popping from the call stack, respectively.

2.2 Call Stack and Stack Frames

Take factorial(4) as an example. As the recursion descends, a logical call stack gradually forms:

Call level Current argument Pending operation
Level 1 4 Calculate 4 × factorial(3)
Level 2 3 Calculate 3 × factorial(2)
Level 3 2 Calculate 2 × factorial(1)
Level 4 1 Calculate 1 × factorial(0)
Level 5 0 Return 1

Each call level needs to preserve its own execution state.

After the deepest layer returns, the call stack pops layer by layer, and the previous layer resumes execution and continues calculating.

Therefore, ordinary recursion usually incurs additional space overhead proportional to the recursion depth.

2.3 Recursion Termination Condition

Recursion must have a reachable termination condition.

Correct example:

def countdown(n):
    if n <= 0:
        return

    print(n)
    countdown(n - 1)

Incorrect example:

def countdown(n):
    print(n)
    countdown(n - 1)

The second implementation has no termination condition. It will keep creating new function calls and may eventually trigger the runtime's recursion depth limit or exhaust stack space.

The termination condition must be designed to meet the following:

  • Cover the edge cases of valid input.
  • The recursive parameters must advance toward the termination condition.
  • Every recursive path that can be executed must be able to terminate.
  • The termination condition must not miss special inputs.

2.4 Recursion Depth and Stack Overflow

Assume that each recursion reduces the problem size by 1:

T(n) = T(n-1) + O(1)

The recursion depth is usually:

D(n) = O(n)

If each call level requires a constant amount of stack space, the extra space complexity is:

S(n) = O(n)

When the recursion depth is too large, the following may occur:

  • Python's RecursionError.
  • Stack space exhaustion in C/C++ programs.
  • Java's StackOverflowError.

Different languages, runtimes, and execution environments have different limits; the recursion depth limit of one language cannot be generalized to other languages.

III. Execution Principles of Iteration

Iteration repeatedly performs operations through loops and stores the current state in variables or data structures.

Unlike recursion, which relies on the function call stack, ordinary iteration usually updates state within the same function call.

3.1 Iteration Execution Process

Factorial implementation:

def factorial(n):
    result = 1

    for i in range(1, n + 1):
        result *= i

    return result

Execution process:

flowchart TD
    A["Initialize result = 1"] --> B["Set i = 1"]
    B --> C{"i <= n ?"}
    C -->|"Yes"| D["result = result × i"]
    D --> E["i = i + 1"]
    E --> C
    C -->|"No"| F["Return result"]
    F --> G["End"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

3.2 Iteration State

The core of iteration is maintaining state.

Taking the above factorial algorithm as an example:

Iteration count i result
Initialization 1 1
1st iteration 1 1
2nd iteration 2 2
3rd iteration 3 6
4th iteration 4 24

Each loop iteration computes the next state based on the current state.

This can be abstracted as:

S_{k+1} = F(S_k)

Where:

  • S_k: the state of the k-th iteration.
  • F: the state update function.
  • S_{k+1}: the updated state.

Iterative algorithms usually need to specify three elements:

  1. Initial state.
  2. State transition rule.
  3. Exit condition.

3.3 Loop Invariant

A loop invariant is an important tool for understanding and proving the correctness of iterative algorithms.

It refers to a condition that always holds at a specific point during loop execution.

For example, factorial iteration:

def factorial(n):
    result = 1

    for i in range(1, n + 1):
        result *= i

    return result

We can define the loop invariant:

At the beginning of each loop iteration:

result = (i-1)!

Before the loop starts, result = 1, corresponding to 0! = 1.

After one iteration:

result = result \times i

This gives:

result = i!

At the beginning of the next iteration, the loop variable is incremented, and the new loop invariant still holds.

When the loop ends, the result is:

result = n!

The loop invariant is usually proved in three steps:

  • Initialization: holds before the first iteration begins.
  • Maintenance: still holds after each loop iteration.
  • Termination: when the loop ends, the invariant implies the algorithm's result is correct.

IV. The Mathematical Relationship Between Recursion and Iteration

Many algorithms can be described by recurrence relations and can also be converted into iterative form.

4.1 Recurrence Relations

Recursive algorithms often describe their running time using a recurrence:

T(n) = aT(n/b) + f(n)

Where:

  • a: the number of subproblems produced each time.
  • n/b: the size of the subproblems.
  • f(n): the work of splitting, merging, and other extra work.

For example, merge sort:

T(n) = 2T(n/2) + O(n)

By the master theorem we obtain:

T(n) = O(n\log n)

The recurrence relation here describes the algorithm's time complexity; it does not mean that all recursive algorithms have the same space overhead.

4.2 Iterative Relations

An iterative algorithm can be expressed as a state transition:

S_{k+1} = F(S_k)

By repeatedly applying the state transition function until the target state or exit condition is reached.

For example, the Fibonacci sequence:

F(n) = \begin{cases} 0 & n=0 \\ 1 & n=1 \\ F(n-1)+F(n-2) & n\geq 2 \end{cases}

It can be computed either recursively or iteratively by maintaining the previous two values.

V. A Comparison of Typical Algorithms: Recursion vs. Iteration

5.1 Fibonacci Sequence

Definition of the Fibonacci sequence:

F(0)=0,\quad F(1)=1
F(n)=F(n-1)+F(n-2)

Recursive Implementation

def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

This implementation expresses the mathematical definition intuitively, but involves a great deal of redundant computation.

For example, when computing fib(5), subproblems such as fib(3) and fib(2) are computed multiple times.

Recursion call tree:

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    C --> F["fib(2)"]
    C --> G["fib(1)"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

The time complexity of naive recursion is:

T(n)=T(n-1)+T(n-2)+O(1)

Its time complexity is exponential:

O(\varphi^n)

Where \varphi is the golden ratio. A common loose upper bound can also be written as O(2^n).

Iterative Implementation

def fib(n):
    if n <= 1:
        return n

    a, b = 0, 1

    for _ in range(2, n + 1):
        a, b = b, a + b

    return b

Time complexity:

O(n)

Extra space complexity:

O(1)

Iteration only needs to keep the previous two states; there is no need to build a recursion call tree.

5.2 Binary Tree Traversal

Tree structures naturally have a recursive character.

For example, preorder traversal of a binary tree:

def preorder(node):
    if node is None:
        return

    print(node.value)
    preorder(node.left)
    preorder(node.right)

The recursive formulation is very natural:

  • Visit the current node.
  • Traverse the left subtree.
  • Traverse the right subtree.

But it can also be implemented iteratively using an explicit stack:

def preorder(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop()
        print(node.value)

        if node.right:
            stack.append(node.right)

        if node.left:
            stack.append(node.left)

Here, the traversal state originally managed by the runtime call stack is moved into a stack that the program maintains explicitly.

Comparison Recursive traversal Iterative traversal
State storage System call stack Explicit stack
Code structure Concise Usually more complex
Space complexity O(h) O(h)
Depth control Limited by the call stack Can be managed manually
Use cases Clear hierarchical structure Need to control execution state

Here h denotes the height of the tree. For a tree that has degenerated into a linked list, h may reach O(n).

VI. Complexity Analysis of Recursion and Iteration

When comparing recursion and iteration, you cannot look only at the number of lines of code; you also need to analyze time complexity and space complexity.

6.1 Time Complexity

Time complexity depends mainly on the algorithm itself, not on whether it uses recursion.

For example: