Iteration vs. recursion

From CS 61A Wiki
Jump to: navigation, search
Iteration and recursion are both ways to achieve repetition in programs. One can be converted to the other:
  • All iterative functions can be converted to recursion because iteration is just a special case of recursion (tail recursion). In functional languages like Scheme, iteration is defined as tail recursion.
  • All recursive functions can be converted to iteration by simulating the stack to store state.

However, recursion is usually slower and uses more memory because of the overhead of creating and maintaining stack frames. This doesn't mean never use recursion though. Recursion is the better choice when:

  • the code is clearer, more concise, and more intuitive
  • exploring/manipulating recursive data structures like linked lists and trees or parsing expressions (e.g., Scheme interpreter)

For example, a recursive function on a tree can be converted into an iterative one, but the iterative one is harder to understand. Compare the following recursive and iterative implementations of finding the number of nodes in a binary tree:

def size_recur(t):
    """Returns the number of nodes in binary tree T.
    >>> t = Tree(10, Tree(4, Tree(1), Tree(7)), Tree(16, Tree(13), Tree(19)))
    >>> size_recur(t)
    7
    """
    if t is None:
        return 0
    return 1 + size_recur(t.left) + size_recur(t.right)
 
def size_iter(t):
    """Returns the number of nodes in binary tree T.
    >>> t = Tree(10, Tree(4, Tree(1), Tree(7)), Tree(16, Tree(13), Tree(19)))
    >>> size_iter(t)
    7
    """
    count = 0
    nodes = [] # unprocessed nodes
    if t is not None:
        nodes.append(t)
    while nodes: # while nodes is not empty
        u = nodes.pop() # get an unprocessed node
        count += 1 # increment counter
        if u.left:
            nodes.append(u.left) # add left child
        if u.right:
            nodes.append(u.right) # add right child
    return count
In this case, the recursive version is more intuitive and concise.

Iteration → recursion

An iterative function can be converted to a tail recursive function by using the loop condition as the base case and the body of the loop as the recursive step. The local variables in the iterative version turn into parameters in the recursive version.

Example 1:

def max_iter(lst):
    """Returns the maximum element of LST.
    >>> max_iter([3, 7, 2, 5])
    7
    """
    x = lst[0]
    i = 1
    while i < len(lst):
        if lst[i] > x:
            x = lst[i]
        i += 1
    return x
 
def max_recur(lst):
    """Returns the maximum element of LST.
    >>> max_recur([3, 7, 2, 5])
    7
    """
    def helper(i, x):
        if i == len(lst):
            return x
        if lst[i] > x:
            x = lst[i]
        return helper(i + 1, x)
    return helper(1, lst[0])

Example 2:

def fib_iter(n):
    prev, curr = 0, 1
    for k in range(2, n):
        prev, curr = curr, prev + curr
    return curr
 
def fib_tail_recur(n):
    def helper(k, prev, curr):
        if k == n:
            return curr
        return helper(k + 1, curr, prev + curr)
    return helper(2, 0, 1)

Recursion → iteration

A tail recursive function can be converted to an iterative function using the same idea as above. A more complicated recursive function will require a stack to convert to an iterative function. This is outside the scope of 61A.

Sources