Recursion and Iteration in Algorithm Design

Iteration

Iteration repeats a block of instructions using loops (for, while) until a terminating condition is reached.

Structure

ALGORITHM SumIterative(n)
    sum ← 0
    for i ← 1 to n do
        sum ← sum + i
    end for
    return sum

Characteristics

• Uses explicit loops
• Maintains and updates state in variables
• Generally more memory-efficient (no call stack overhead)
• Easier to trace manually (step-by-step)

Recursion

Recursion occurs when a function calls itself with a smaller or simpler version of the problem. Every recursive algorithm must have:

1. Base case(s): The simplest version(s) of the problem, solved directly without further recursion
2. Recursive case: Breaks the problem into a smaller sub-problem and calls itself

Structure

ALGORITHM SumRecursive(n)
    if n = 0 then
        return 0              // base case
    else
        return n + SumRecursive(n - 1)   // recursive case
    end if

Call Stack for SumRecursive(4)

SumRecursive(4)
  = 4 + SumRecursive(3)
      = 4 + 3 + SumRecursive(2)
          = 4 + 3 + 2 + SumRecursive(1)
              = 4 + 3 + 2 + 1 + SumRecursive(0)
                  = 4 + 3 + 2 + 1 + 0
                  = 10

KEY TAKEAWAY: Every recursive call is added to the call stack. The base case stops further calls, then results propagate back up the stack.

Recursive Fibonacci

ALGORITHM Fibonacci(n)
    if n <= 1 then
        return n
    else
        return Fibonacci(n-1) + Fibonacci(n-2)
    end if

Note: This naive implementation has exponential time complexity $O(2^n)$ — dynamic programming is vastly more efficient.

Recursion vs. Iteration Comparison

When to Use Each

Prefer iteration when:
- The problem has a straightforward loop structure
- Memory efficiency is critical
- Depth of recursion could be very large

Prefer recursion when:
- The problem is naturally self-similar (e.g. tree traversal, binary search, mergesort)
- Recursion leads to cleaner, more readable code
- The problem uses a divide-and-conquer approach

Converting Between the Two

Every recursive algorithm can be converted to an iterative one by using an explicit stack:

# Recursive DFS
def dfs_recursive(graph, start, visited=None):
    if visited is None: visited = set()
    visited.add(start)
    for neighbour in graph[start]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)
    return visited

# Iterative DFS (using explicit stack)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.add(v)
            for neighbour in graph[v]:
                stack.append(neighbour)
    return visited

EXAM TIP: DFS is naturally recursive; BFS is naturally iterative (using a queue). Both can be converted, but their natural form is easier to reason about and less error-prone.