Skip to content

2.2   Iteration and recursion

Algorithms often repeat tasks, and repetition is closely tied to complexity analysis. Before introducing time and space complexity, let's examine two basic ways to repeat work in a program: iteration and recursion.

2.2.1   Iteration

Iteration is a control structure for repeating a task. A program repeatedly executes a block of code while a condition holds, stopping when it no longer does.

1.   For loops

A for loop is one of the most common forms of iteration, especially when the number of iterations is known in advance.

The following function uses a for loop to compute \(1 + 2 + \dots + n\), storing the result in res. In Python, range(a, b) includes the left endpoint but excludes the right, so it visits \(a, a + 1, \dots, b-1\):

iteration.py
def for_loop(n: int) -> int:
    """for loop"""
    res = 0
    # Sum 1, 2, ..., n-1, n in a loop
    for i in range(1, n + 1):
        res += i
    return res
iteration.cpp
/* for loop */
int forLoop(int n) {
    int res = 0;
    // Sum 1, 2, ..., n-1, n in a loop
    for (int i = 1; i <= n; ++i) {
        res += i;
    }
    return res;
}
iteration.java
/* for loop */
int forLoop(int n) {
    int res = 0;
    // Sum 1, 2, ..., n-1, n in a loop
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.cs
/* for loop */
int ForLoop(int n) {
    int res = 0;
    // Sum 1, 2, ..., n-1, n in a loop
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.go
/* for loop */
func forLoop(n int) int {
    res := 0
    // Sum 1, 2, ..., n-1, n in a loop
    for i := 1; i <= n; i++ {
        res += i
    }
    return res
}
iteration.swift
/* for loop */
func forLoop(n: Int) -> Int {
    var res = 0
    // Sum 1, 2, ..., n-1, n in a loop
    for i in 1 ... n {
        res += i
    }
    return res
}
iteration.js
/* for loop */
function forLoop(n) {
    let res = 0;
    // Sum 1, 2, ..., n-1, n in a loop
    for (let i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.ts
/* for loop */
function forLoop(n: number): number {
    let res = 0;
    // Sum 1, 2, ..., n-1, n in a loop
    for (let i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.dart
/* for loop */
int forLoop(int n) {
  int res = 0;
  // Sum 1, 2, ..., n-1, n in a loop
  for (int i = 1; i <= n; i++) {
    res += i;
  }
  return res;
}
iteration.rs
/* for loop */
fn for_loop(n: i32) -> i32 {
    let mut res = 0;
    // Sum 1, 2, ..., n-1, n in a loop
    for i in 1..=n {
        res += i;
    }
    res
}
iteration.c
/* for loop */
int forLoop(int n) {
    int res = 0;
    // Sum 1, 2, ..., n-1, n in a loop
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.kt
/* for loop */
fun forLoop(n: Int): Int {
    var res = 0
    // Sum 1, 2, ..., n-1, n in a loop
    for (i in 1..n) {
        res += i
    }
    return res
}
iteration.rb
### for loop ###
def for_loop(n)
  res = 0

  # Sum 1, 2, ..., n-1, n in a loop
  for i in 1..n
    res += i
  end

  res
end
Visualize execution

Figure 2-1 is a flowchart of this summation function.

Flowchart of the summation function

Figure 2-1   Flowchart of the summation function

Its operation count is proportional to the input size \(n\): the relationship is linear. Time complexity describes this relationship, as the next section will explain.

2.   While loops

Like for, a while loop implements iteration. Before each iteration, it checks a condition: if true, execution continues; otherwise, the loop ends.

Here is a while loop computing \(1 + 2 + \dots + n\):

iteration.py
def while_loop(n: int) -> int:
    """while loop"""
    res = 0
    i = 1  # Initialize the loop control variable
    # Sum 1, 2, ..., n-1, n in a loop
    while i <= n:
        res += i
        i += 1  # Update the loop control variable
    return res
iteration.cpp
/* while loop */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while (i <= n) {
        res += i;
        i++; // Update the loop control variable
    }
    return res;
}
iteration.java
/* while loop */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while (i <= n) {
        res += i;
        i++; // Update the loop control variable
    }
    return res;
}
iteration.cs
/* while loop */
int WhileLoop(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while (i <= n) {
        res += i;
        i += 1; // Update the loop control variable
    }
    return res;
}
iteration.go
/* while loop */
func whileLoop(n int) int {
    res := 0
    // Initialize the loop control variable
    i := 1
    // Sum 1, 2, ..., n-1, n in a loop
    for i <= n {
        res += i
        // Update the loop control variable
        i++
    }
    return res
}
iteration.swift
/* while loop */
func whileLoop(n: Int) -> Int {
    var res = 0
    var i = 1 // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while i <= n {
        res += i
        i += 1 // Update the loop control variable
    }
    return res
}
iteration.js
/* while loop */
function whileLoop(n) {
    let res = 0;
    let i = 1; // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while (i <= n) {
        res += i;
        i++; // Update the loop control variable
    }
    return res;
}
iteration.ts
/* while loop */
function whileLoop(n: number): number {
    let res = 0;
    let i = 1; // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while (i <= n) {
        res += i;
        i++; // Update the loop control variable
    }
    return res;
}
iteration.dart
/* while loop */
int whileLoop(int n) {
  int res = 0;
  int i = 1; // Initialize the loop control variable
  // Sum 1, 2, ..., n-1, n in a loop
  while (i <= n) {
    res += i;
    i++; // Update the loop control variable
  }
  return res;
}
iteration.rs
/* while loop */
fn while_loop(n: i32) -> i32 {
    let mut res = 0;
    let mut i = 1; // Initialize the loop control variable

    // Sum 1, 2, ..., n-1, n in a loop
    while i <= n {
        res += i;
        i += 1; // Update the loop control variable
    }
    res
}
iteration.c
/* while loop */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while (i <= n) {
        res += i;
        i++; // Update the loop control variable
    }
    return res;
}
iteration.kt
/* while loop */
fun whileLoop(n: Int): Int {
    var res = 0
    var i = 1 // Initialize the loop control variable
    // Sum 1, 2, ..., n-1, n in a loop
    while (i <= n) {
        res += i
        i++ // Update the loop control variable
    }
    return res
}
iteration.rb
### while loop ###
def while_loop(n)
  res = 0
  i = 1 # Initialize the loop control variable

  # Sum 1, 2, ..., n-1, n in a loop
  while i <= n
    res += i
    i += 1 # Update the loop control variable
  end

  res
end
Visualize execution

A while loop offers more flexibility than a for loop in how its condition variables are initialized and updated.

For example, the following code updates the condition variable \(i\) twice per iteration, which is less convenient to express with a for loop:

iteration.py
def while_loop_ii(n: int) -> int:
    """while loop (two updates)"""
    res = 0
    i = 1  # Initialize the loop control variable
    # Sum 1, 4, 10, ... in a loop
    while i <= n:
        res += i
        # Update the loop control variable
        i += 1
        i *= 2
    return res
iteration.cpp
/* while loop (two updates) */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while (i <= n) {
        res += i;
        // Update the loop control variable
        i++;
        i *= 2;
    }
    return res;
}
iteration.java
/* while loop (two updates) */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while (i <= n) {
        res += i;
        // Update the loop control variable
        i++;
        i *= 2;
    }
    return res;
}
iteration.cs
/* while loop (two updates) */
int WhileLoopII(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while (i <= n) {
        res += i;
        // Update the loop control variable
        i += 1; 
        i *= 2;
    }
    return res;
}
iteration.go
/* while loop (two updates) */
func whileLoopII(n int) int {
    res := 0
    // Initialize the loop control variable
    i := 1
    // Sum 1, 4, 10, ... in a loop
    for i <= n {
        res += i
        // Update the loop control variable
        i++
        i *= 2
    }
    return res
}
iteration.swift
/* while loop (two updates) */
func whileLoopII(n: Int) -> Int {
    var res = 0
    var i = 1 // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while i <= n {
        res += i
        // Update the loop control variable
        i += 1
        i *= 2
    }
    return res
}
iteration.js
/* while loop (two updates) */
function whileLoopII(n) {
    let res = 0;
    let i = 1; // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while (i <= n) {
        res += i;
        // Update the loop control variable
        i++;
        i *= 2;
    }
    return res;
}
iteration.ts
/* while loop (two updates) */
function whileLoopII(n: number): number {
    let res = 0;
    let i = 1; // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while (i <= n) {
        res += i;
        // Update the loop control variable
        i++;
        i *= 2;
    }
    return res;
}
iteration.dart
/* while loop (two updates) */
int whileLoopII(int n) {
  int res = 0;
  int i = 1; // Initialize the loop control variable
  // Sum 1, 4, 10, ... in a loop
  while (i <= n) {
    res += i;
    // Update the loop control variable
    i++;
    i *= 2;
  }
  return res;
}
iteration.rs
/* while loop (two updates) */
fn while_loop_ii(n: i32) -> i32 {
    let mut res = 0;
    let mut i = 1; // Initialize the loop control variable

    // Sum 1, 4, 10, ... in a loop
    while i <= n {
        res += i;
        // Update the loop control variable
        i += 1;
        i *= 2;
    }
    res
}
iteration.c
/* while loop (two updates) */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while (i <= n) {
        res += i;
        // Update the loop control variable
        i++;
        i *= 2;
    }
    return res;
}
iteration.kt
/* while loop (two updates) */
fun whileLoopII(n: Int): Int {
    var res = 0
    var i = 1 // Initialize the loop control variable
    // Sum 1, 4, 10, ... in a loop
    while (i <= n) {
        res += i
        // Update the loop control variable
        i++
        i *= 2
    }
    return res
}
iteration.rb
### while loop (two updates)###
def while_loop_ii(n)
  res = 0
  i = 1 # Initialize the loop control variable

  # Sum 1, 4, 10, ... in a loop
  while i <= n
    res += i
    # Update the loop control variable
    i += 1
    i *= 2
  end

  res
end
Visualize execution

In general, for loops are more compact, while while loops are more flexible. Both implement iteration; choose according to the problem's needs.

3.   Nested loops

We can place one loop inside another, as in the following for-loop example:

iteration.py
def nested_for_loop(n: int) -> str:
    """Nested for loops"""
    res = ""
    # Loop over i = 1, 2, ..., n-1, n
    for i in range(1, n + 1):
        # Loop over j = 1, 2, ..., n-1, n
        for j in range(1, n + 1):
            res += f"({i}, {j}), "
    return res
iteration.cpp
/* Nested for loops */
string nestedForLoop(int n) {
    ostringstream res;
    // Loop over i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        // Loop over j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; ++j) {
            res << "(" << i << ", " << j << "), ";
        }
    }
    return res.str();
}
iteration.java
/* Nested for loops */
String nestedForLoop(int n) {
    StringBuilder res = new StringBuilder();
    // Loop over i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        // Loop over j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; j++) {
            res.append("(" + i + ", " + j + "), ");
        }
    }
    return res.toString();
}
iteration.cs
/* Nested for loops */
string NestedForLoop(int n) {
    StringBuilder res = new();
    // Loop over i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        // Loop over j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; j++) {
            res.Append($"({i}, {j}), ");
        }
    }
    return res.ToString();
}
iteration.go
/* Nested for loops */
func nestedForLoop(n int) string {
    res := ""
    // Loop over i = 1, 2, ..., n-1, n
    for i := 1; i <= n; i++ {
        for j := 1; j <= n; j++ {
            // Loop over j = 1, 2, ..., n-1, n
            res += fmt.Sprintf("(%d, %d), ", i, j)
        }
    }
    return res
}
iteration.swift
/* Nested for loops */
func nestedForLoop(n: Int) -> String {
    var res = ""
    // Loop over i = 1, 2, ..., n-1, n
    for i in 1 ... n {
        // Loop over j = 1, 2, ..., n-1, n
        for j in 1 ... n {
            res.append("(\(i), \(j)), ")
        }
    }
    return res
}
iteration.js
/* Nested for loops */
function nestedForLoop(n) {
    let res = '';
    // Loop over i = 1, 2, ..., n-1, n
    for (let i = 1; i <= n; i++) {
        // Loop over j = 1, 2, ..., n-1, n
        for (let j = 1; j <= n; j++) {
            res += `(${i}, ${j}), `;
        }
    }
    return res;
}
iteration.ts
/* Nested for loops */
function nestedForLoop(n: number): string {
    let res = '';
    // Loop over i = 1, 2, ..., n-1, n
    for (let i = 1; i <= n; i++) {
        // Loop over j = 1, 2, ..., n-1, n
        for (let j = 1; j <= n; j++) {
            res += `(${i}, ${j}), `;
        }
    }
    return res;
}
iteration.dart
/* Nested for loops */
String nestedForLoop(int n) {
  String res = "";
  // Loop over i = 1, 2, ..., n-1, n
  for (int i = 1; i <= n; i++) {
    // Loop over j = 1, 2, ..., n-1, n
    for (int j = 1; j <= n; j++) {
      res += "($i, $j), ";
    }
  }
  return res;
}
iteration.rs
/* Nested for loops */
fn nested_for_loop(n: i32) -> String {
    let mut res = vec![];
    // Loop over i = 1, 2, ..., n-1, n
    for i in 1..=n {
        // Loop over j = 1, 2, ..., n-1, n
        for j in 1..=n {
            res.push(format!("({}, {}), ", i, j));
        }
    }
    res.join("")
}
iteration.c
/* Nested for loops */
char *nestedForLoop(int n) {
    // There are n * n points; each "(i, j), " takes at most 6+10*2 characters, plus space for the final null character \0
    int size = n * n * 26 + 1;
    char *res = malloc(size * sizeof(char));
    // Loop over i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        // Loop over j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; j++) {
            char tmp[26];
            snprintf(tmp, sizeof(tmp), "(%d, %d), ", i, j);
            strncat(res, tmp, size - strlen(res) - 1);
        }
    }
    return res;
}
iteration.kt
/* Nested for loops */
fun nestedForLoop(n: Int): String {
    val res = StringBuilder()
    // Loop over i = 1, 2, ..., n-1, n
    for (i in 1..n) {
        // Loop over j = 1, 2, ..., n-1, n
        for (j in 1..n) {
            res.append(" ($i, $j), ")
        }
    }
    return res.toString()
}
iteration.rb
### Nested for loops ###
def nested_for_loop(n)
  res = ""

  # Loop over i = 1, 2, ..., n-1, n
  for i in 1..n
    # Loop over j = 1, 2, ..., n-1, n
    for j in 1..n
      res += "(#{i}, #{j}), "
    end
  end

  res
end
Visualize execution

Figure 2-2 shows the nested loop's flowchart.

Flowchart of nested loops

Figure 2-2   Flowchart of nested loops

Here, the operation count is proportional to \(n^2\): runtime has a quadratic relationship with input size \(n\).

Adding further nesting increases the dimension each time, producing cubic, fourth-power, and higher-order time complexity.

2.2.2   Recursion

Recursion is an algorithmic strategy in which a function calls itself to solve a problem. It has two main phases.

  1. Descent: The function calls itself more deeply, usually with smaller or simpler arguments, until a base case is reached.
  2. Return: Once the base case is reached, calls return from the deepest level upward, combining results along the way.

In implementation, recursive code has three main elements.

  1. Base case: Determines when descent stops and returning begins.
  2. Recursive call: The function calls itself, usually with smaller or simpler arguments.
  3. Returned result: The current level returns its result to the previous level.

In the following code, calling recur(n) computes \(1 + 2 + \dots + n\):

recursion.py
def recur(n: int) -> int:
    """Recursion"""
    # Base case
    if n == 1:
        return 1
    # Recurse: make a recursive call
    res = recur(n - 1)
    # Unwind: return the result
    return n + res
recursion.cpp
/* Recursion */
int recur(int n) {
    // Base case
    if (n == 1)
        return 1;
    // Recurse: make a recursive call
    int res = recur(n - 1);
    // Unwind: return the result
    return n + res;
}
recursion.java
/* Recursion */
int recur(int n) {
    // Base case
    if (n == 1)
        return 1;
    // Recurse: make a recursive call
    int res = recur(n - 1);
    // Unwind: return the result
    return n + res;
}
recursion.cs
/* Recursion */
int Recur(int n) {
    // Base case
    if (n == 1)
        return 1;
    // Recurse: make a recursive call
    int res = Recur(n - 1);
    // Unwind: return the result
    return n + res;
}
recursion.go
/* Recursion */
func recur(n int) int {
    // Base case
    if n == 1 {
        return 1
    }
    // Recurse: make a recursive call
    res := recur(n - 1)
    // Unwind: return the result
    return n + res
}
recursion.swift
/* Recursion */
func recur(n: Int) -> Int {
    // Base case
    if n == 1 {
        return 1
    }
    // Recurse: make a recursive call
    let res = recur(n: n - 1)
    // Unwind: return the result
    return n + res
}
recursion.js
/* Recursion */
function recur(n) {
    // Base case
    if (n === 1) return 1;
    // Recurse: make a recursive call
    const res = recur(n - 1);
    // Unwind: return the result
    return n + res;
}
recursion.ts
/* Recursion */
function recur(n: number): number {
    // Base case
    if (n === 1) return 1;
    // Recurse: make a recursive call
    const res = recur(n - 1);
    // Unwind: return the result
    return n + res;
}
recursion.dart
/* Recursion */
int recur(int n) {
  // Base case
  if (n == 1) return 1;
  // Recurse: make a recursive call
  int res = recur(n - 1);
  // Unwind: return the result
  return n + res;
}
recursion.rs
/* Recursion */
fn recur(n: i32) -> i32 {
    // Base case
    if n == 1 {
        return 1;
    }
    // Recurse: make a recursive call
    let res = recur(n - 1);
    // Unwind: return the result
    n + res
}
recursion.c
/* Recursion */
int recur(int n) {
    // Base case
    if (n == 1)
        return 1;
    // Recurse: make a recursive call
    int res = recur(n - 1);
    // Unwind: return the result
    return n + res;
}
recursion.kt
/* Recursion */
fun recur(n: Int): Int {
    // Base case
    if (n == 1)
        return 1
    // Descending: recursive calls
    val res = recur(n - 1)
    // Unwinding: return the result
    return n + res
}
recursion.rb
### Recursion ###
def recur(n)
  # Base case
  return 1 if n == 1
  # Recurse: make a recursive call
  res = recur(n - 1)
  # Unwind: return the result
  n + res
end
Visualize execution

Figure 2-3 illustrates the recursive process.

Recursive process of the summation function

Figure 2-3   Recursive process of the summation function

Iteration and recursion can produce the same answer, but represent two different ways of thinking about and solving a problem.

  • Iteration works bottom up, starting with basic steps and repeatedly performing or accumulating them until the task is complete.
  • Recursion works top down, dividing the original problem into smaller subproblems of the same form, then repeating the division until reaching base cases with known solutions.

For the summation example, let \(f(n) = 1 + 2 + \dots + n\).

  • Iteration: Loop from \(1\) to \(n\), accumulating the sum at each step to obtain \(f(n)\).
  • Recursion: Decompose the problem as \(f(n) = n + f(n-1)\) and keep doing so recursively until the base case \(f(1) = 1\).

1.   The call stack

Each time a recursive function calls itself, the system allocates memory for the new call's local variables, return address, and other information. This has two consequences.

  • The call's context is stored in a stack frame until it returns. Recursion therefore usually uses more memory than iteration.
  • Each recursive call adds overhead. Recursion is therefore usually slower than a loop.

As shown in Figure 2-4, before the base case is reached, \(n\) recursive calls remain active at once: the recursion depth is \(n\).

Depth of recursive calls

Figure 2-4   Depth of recursive calls

Programming languages usually limit recursion depth, and excessively deep recursion may cause a stack overflow.

2.   Tail recursion

Interestingly, if the recursive call is the last operation before a function returns, a compiler or interpreter can optimize it to use as little space as iteration. This is called tail recursion.

  • Ordinary recursion: After a call returns, its caller must continue executing code, so the caller's context must be preserved.
  • Tail recursion: Nothing remains to be done after the recursive call returns, so the caller's context need not be retained.

For \(1 + 2 + \dots + n\), passing the accumulated result res as a parameter gives a tail-recursive solution:

recursion.py
def tail_recur(n, res):
    """Tail recursion"""
    # Base case
    if n == 0:
        return res
    # Tail-recursive call
    return tail_recur(n - 1, res + n)
recursion.cpp
/* Tail recursion */
int tailRecur(int n, int res) {
    // Base case
    if (n == 0)
        return res;
    // Tail-recursive call
    return tailRecur(n - 1, res + n);
}
recursion.java
/* Tail recursion */
int tailRecur(int n, int res) {
    // Base case
    if (n == 0)
        return res;
    // Tail-recursive call
    return tailRecur(n - 1, res + n);
}
recursion.cs
/* Tail recursion */
int TailRecur(int n, int res) {
    // Base case
    if (n == 0)
        return res;
    // Tail-recursive call
    return TailRecur(n - 1, res + n);
}
recursion.go
/* Tail recursion */
func tailRecur(n int, res int) int {
    // Base case
    if n == 0 {
        return res
    }
    // Tail-recursive call
    return tailRecur(n-1, res+n)
}
recursion.swift
/* Tail recursion */
func tailRecur(n: Int, res: Int) -> Int {
    // Base case
    if n == 0 {
        return res
    }
    // Tail-recursive call
    return tailRecur(n: n - 1, res: res + n)
}
recursion.js
/* Tail recursion */
function tailRecur(n, res) {
    // Base case
    if (n === 0) return res;
    // Tail-recursive call
    return tailRecur(n - 1, res + n);
}
recursion.ts
/* Tail recursion */
function tailRecur(n: number, res: number): number {
    // Base case
    if (n === 0) return res;
    // Tail-recursive call
    return tailRecur(n - 1, res + n);
}
recursion.dart
/* Tail recursion */
int tailRecur(int n, int res) {
  // Base case
  if (n == 0) return res;
  // Tail-recursive call
  return tailRecur(n - 1, res + n);
}
recursion.rs
/* Tail recursion */
fn tail_recur(n: i32, res: i32) -> i32 {
    // Base case
    if n == 0 {
        return res;
    }
    // Tail-recursive call
    tail_recur(n - 1, res + n)
}
recursion.c
/* Tail recursion */
int tailRecur(int n, int res) {
    // Base case
    if (n == 0)
        return res;
    // Tail-recursive call
    return tailRecur(n - 1, res + n);
}
recursion.kt
/* Tail recursion */
tailrec fun tailRecur(n: Int, res: Int): Int {
    // Add the tailrec modifier to enable tail-call optimization
    // Base case
    if (n == 0)
        return res
    // Tail-recursive call
    return tailRecur(n - 1, res + n)
}
recursion.rb
### Tail recursion ###
def tail_recur(n, res)
  # Base case
  return res if n == 0
  # Tail-recursive call
  tail_recur(n - 1, res + n)
end
Visualize execution

Figure 2-5 illustrates tail recursion. Ordinary and tail recursion perform their additions at different points.

  • Ordinary recursion: Addition occurs during the return phase, after each deeper call returns.
  • Tail recursion: Addition occurs during descent; the return phase simply returns through the levels.

Tail-recursive summation

Figure 2-5   Tail-recursive summation

Tip

Many compilers and interpreters do not support tail-recursion optimization. Python, for example, does not optimize it by default, so even a tail-recursive function can run into a stack overflow.

3.   Recursion trees

For divide-and-conquer problems, recursion often provides a more intuitive approach and more readable code than iteration. Consider the Fibonacci sequence.

Question

Given the Fibonacci sequence \(0, 1, 1, 2, 3, 5, 8, 13, \dots\), find its \(n\)-th number.

Let \(f(n)\) be its \(n\)-th number. Two facts follow.

  • The first two numbers are \(f(1) = 0\) and \(f(2) = 1\).
  • Every later number is the sum of the two preceding numbers: \(f(n) = f(n - 1) + f(n - 2)\).

Use the recurrence for recursive calls and the first two numbers as base cases. Calling fib(n) then returns the \(n\)-th Fibonacci number:

recursion.py
def fib(n: int) -> int:
    """Fibonacci sequence: recursion"""
    # Base cases: f(1) = 0, f(2) = 1
    if n == 1 or n == 2:
        return n - 1
    # Recursive calls: f(n) = f(n-1) + f(n-2)
    res = fib(n - 1) + fib(n - 2)
    # Return the result f(n)
    return res
recursion.cpp
/* Fibonacci sequence: recursion */
int fib(int n) {
    // Base cases: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // Return the result f(n)
    return res;
}
recursion.java
/* Fibonacci sequence: recursion */
int fib(int n) {
    // Base cases: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // Return the result f(n)
    return res;
}
recursion.cs
/* Fibonacci sequence: recursion */
int Fib(int n) {
    // Base cases: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    int res = Fib(n - 1) + Fib(n - 2);
    // Return the result f(n)
    return res;
}
recursion.go
/* Fibonacci sequence: recursion */
func fib(n int) int {
    // Base cases: f(1) = 0, f(2) = 1
    if n == 1 || n == 2 {
        return n - 1
    }
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    res := fib(n-1) + fib(n-2)
    // Return the result f(n)
    return res
}
recursion.swift
/* Fibonacci sequence: recursion */
func fib(n: Int) -> Int {
    // Base cases: f(1) = 0, f(2) = 1
    if n == 1 || n == 2 {
        return n - 1
    }
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    let res = fib(n: n - 1) + fib(n: n - 2)
    // Return the result f(n)
    return res
}
recursion.js
/* Fibonacci sequence: recursion */
function fib(n) {
    // Base cases: f(1) = 0, f(2) = 1
    if (n === 1 || n === 2) return n - 1;
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    const res = fib(n - 1) + fib(n - 2);
    // Return the result f(n)
    return res;
}
recursion.ts
/* Fibonacci sequence: recursion */
function fib(n: number): number {
    // Base cases: f(1) = 0, f(2) = 1
    if (n === 1 || n === 2) return n - 1;
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    const res = fib(n - 1) + fib(n - 2);
    // Return the result f(n)
    return res;
}
recursion.dart
/* Fibonacci sequence: recursion */
int fib(int n) {
  // Base cases: f(1) = 0, f(2) = 1
  if (n == 1 || n == 2) return n - 1;
  // Recursive calls: f(n) = f(n-1) + f(n-2)
  int res = fib(n - 1) + fib(n - 2);
  // Return the result f(n)
  return res;
}
recursion.rs
/* Fibonacci sequence: recursion */
fn fib(n: i32) -> i32 {
    // Base cases: f(1) = 0, f(2) = 1
    if n == 1 || n == 2 {
        return n - 1;
    }
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    let res = fib(n - 1) + fib(n - 2);
    // Return the result
    res
}
recursion.c
/* Fibonacci sequence: recursion */
int fib(int n) {
    // Base cases: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // Return the result f(n)
    return res;
}
recursion.kt
/* Fibonacci sequence: recursion */
fun fib(n: Int): Int {
    // Base cases: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1
    // Recursive calls: f(n) = f(n-1) + f(n-2)
    val res = fib(n - 1) + fib(n - 2)
    // Return the result f(n)
    return res
}
recursion.rb
### Fibonacci sequence: recursion ###
def fib(n)
  # Base cases: f(1) = 0, f(2) = 1
  return n - 1 if n == 1 || n == 2
  # Recursive calls: f(n) = f(n-1) + f(n-2)
  res = fib(n - 1) + fib(n - 2)
  # Return the result f(n)
  res
end
Visualize execution

The function makes two recursive calls, so each call creates two branches. Continuing this process produces a recursion tree with \(n\) levels, as shown in Figure 2-6.

Recursion tree for the Fibonacci sequence

Figure 2-6   Recursion tree for the Fibonacci sequence

Recursion embodies the idea of breaking a problem into smaller subproblems, a crucial divide-and-conquer strategy.

  • In algorithms, searching, sorting, backtracking, divide and conquer, dynamic programming, and many other techniques use this idea directly or indirectly.
  • In data structures, recursion naturally handles linked lists, trees, and graphs because divide-and-conquer reasoning suits them well.

2.2.3   Comparing iteration and recursion

Table 2-1 summarizes their differences in implementation, performance, and suitability.

Table 2-1   Comparing iteration and recursion

Iteration Recursion
Implementation Loops A function calls itself
Time efficiency Usually high, with no function-call overhead Each call adds overhead
Memory use Usually a fixed amount of memory Accumulated calls may require many stack frames
Suitable problems Simple repetitive tasks, with straightforward, readable code Subproblem decomposition, including trees, graphs, divide and conquer, and backtracking; concise, clear structure

Tip

If the following discussion feels difficult, return to it after reading the section on stacks.

How are iteration and recursion connected? In the summation example, additions occur during the return phase. The first function called is the last to finish its addition, matching a stack's last-in, first-out behavior.

The terms call stack and stack frame already suggest this close relationship.

  1. Descent: A function call adds a new stack frame to the call stack, holding local variables, parameters, the return address, and other data.
  2. Return: When the function finishes, its frame is removed, restoring the caller's execution context.

Thus, an explicit stack can simulate the call stack, converting recursion into iteration:

recursion.py
def for_loop_recur(n: int) -> int:
    """Simulate recursion using iteration"""
    # Use an explicit stack to simulate the system call stack
    stack = []
    res = 0
    # Simulate the recursive-call phase
    for i in range(n, 0, -1):
        # Simulate recursive calls by pushing onto the stack
        stack.append(i)
    # Simulate unwinding and accumulating the result
    while stack:
        # Simulate unwinding by popping from the stack
        res += stack.pop()
    # res = 1+2+3+...+n
    return res
recursion.cpp
/* Simulate recursion using iteration */
int forLoopRecur(int n) {
    // Use an explicit stack to simulate the system call stack
    stack<int> stack;
    int res = 0;
    // Recurse: make a recursive call
    for (int i = n; i > 0; i--) {
        // Simulate recursive calls by pushing onto the stack
        stack.push(i);
    }
    // Unwind: return the result
    while (!stack.empty()) {
        // Simulate unwinding by popping from the stack
        res += stack.top();
        stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.java
/* Simulate recursion using iteration */
int forLoopRecur(int n) {
    // Use an explicit stack to simulate the system call stack
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    // Recurse: make a recursive call
    for (int i = n; i > 0; i--) {
        // Simulate recursive calls by pushing onto the stack
        stack.push(i);
    }
    // Unwind: return the result
    while (!stack.isEmpty()) {
        // Simulate unwinding by popping from the stack
        res += stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.cs
/* Simulate recursion using iteration */
int ForLoopRecur(int n) {
    // Use an explicit stack to simulate the system call stack
    Stack<int> stack = new();
    int res = 0;
    // Recurse: make a recursive call
    for (int i = n; i > 0; i--) {
        // Simulate recursive calls by pushing onto the stack
        stack.Push(i);
    }
    // Unwind: return the result
    while (stack.Count > 0) {
        // Simulate unwinding by popping from the stack
        res += stack.Pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.go
/* Simulate recursion using iteration */
func forLoopRecur(n int) int {
    // Use an explicit stack to simulate the system call stack
    stack := list.New()
    res := 0
    // Descending: simulate recursive calls
    for i := n; i > 0; i-- {
        // Simulate recursive calls by pushing onto the stack
        stack.PushBack(i)
    }
    // Unwinding: simulate returning results
    for stack.Len() != 0 {
        // Simulate unwinding by popping from the stack
        res += stack.Back().Value.(int)
        stack.Remove(stack.Back())
    }
    // res = 1+2+3+...+n
    return res
}
recursion.swift
/* Simulate recursion using iteration */
func forLoopRecur(n: Int) -> Int {
    // Use an explicit stack to simulate the system call stack
    var stack: [Int] = []
    var res = 0
    // Descending: simulate recursive calls
    for i in (1 ... n).reversed() {
        // Simulate recursive calls by pushing onto the stack
        stack.append(i)
    }
    // Unwinding: simulate returning results
    while !stack.isEmpty {
        // Simulate unwinding by popping from the stack
        res += stack.removeLast()
    }
    // res = 1+2+3+...+n
    return res
}
recursion.js
/* Simulate recursion using iteration */
function forLoopRecur(n) {
    // Use an explicit stack to simulate the system call stack
    const stack = [];
    let res = 0;
    // Recurse: make a recursive call
    for (let i = n; i > 0; i--) {
        // Simulate recursive calls by pushing onto the stack
        stack.push(i);
    }
    // Unwind: return the result
    while (stack.length) {
        // Simulate unwinding by popping from the stack
        res += stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.ts
/* Simulate recursion using iteration */
function forLoopRecur(n: number): number {
    // Use an explicit stack to simulate the system call stack 
    const stack: number[] = [];
    let res: number = 0;
    // Recurse: make a recursive call
    for (let i = n; i > 0; i--) {
        // Simulate recursive calls by pushing onto the stack
        stack.push(i);
    }
    // Unwind: return the result
    while (stack.length) {
        // Simulate unwinding by popping from the stack
        res += stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.dart
/* Simulate recursion using iteration */
int forLoopRecur(int n) {
  // Use an explicit stack to simulate the system call stack
  List<int> stack = [];
  int res = 0;
  // Recurse: make a recursive call
  for (int i = n; i > 0; i--) {
    // Simulate recursive calls by pushing onto the stack
    stack.add(i);
  }
  // Unwind: return the result
  while (!stack.isEmpty) {
    // Simulate unwinding by popping from the stack
    res += stack.removeLast();
  }
  // res = 1+2+3+...+n
  return res;
}
recursion.rs
/* Simulate recursion using iteration */
fn for_loop_recur(n: i32) -> i32 {
    // Use an explicit stack to simulate the system call stack
    let mut stack = Vec::new();
    let mut res = 0;
    // Recurse: make a recursive call
    for i in (1..=n).rev() {
        // Simulate recursive calls by pushing onto the stack
        stack.push(i);
    }
    // Unwind: return the result
    while !stack.is_empty() {
        // Simulate unwinding by popping from the stack
        res += stack.pop().unwrap();
    }
    // res = 1+2+3+...+n
    res
}
recursion.c
/* Simulate recursion using iteration */
int forLoopRecur(int n) {
    int stack[1000]; // Use a large array to simulate a stack
    int top = -1;    // Top-of-stack index
    int res = 0;
    // Recurse: make a recursive call
    for (int i = n; i > 0; i--) {
        // Simulate recursive calls by pushing onto the stack
        stack[1 + top++] = i;
    }
    // Unwind: return the result
    while (top >= 0) {
        // Simulate unwinding by popping from the stack
        res += stack[top--];
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.kt
/* Simulate recursion using iteration */
fun forLoopRecur(n: Int): Int {
    // Use an explicit stack to simulate the system call stack
    val stack = Stack<Int>()
    var res = 0
    // Descending: recursive calls
    for (i in n downTo 0) {
        // Simulate recursive calls by pushing onto the stack
        stack.push(i)
    }
    // Unwinding: return the result
    while (stack.isNotEmpty()) {
        // Simulate unwinding by popping from the stack
        res += stack.pop()
    }
    // res = 1+2+3+...+n
    return res
}
recursion.rb
### Simulate recursion using iteration ###
def for_loop_recur(n)
  # Use an explicit stack to simulate the system call stack
  stack = []
  res = 0

  # Recurse: make a recursive call
  for i in n.downto(0)
    # Simulate recursive calls by pushing onto the stack
    stack << i
  end
  # Unwind: return the result
  while !stack.empty?
    res += stack.pop
  end

  # res = 1+2+3+...+n
  res
end
Visualize execution

The resulting iterative code is more complicated. Although iteration and recursion can often be converted into each other, doing so is not always worthwhile.

  • The converted code may be harder to understand and less readable.
  • Simulating the call stack can be very difficult for complex problems.

The choice between iteration and recursion depends on the problem. In practice, weigh their strengths and weaknesses and choose the approach that fits the situation.

Share your insights, questions, or suggestions in the comments