Iteration vs. recursion
- 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
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.
def max_iter(lst): """Returns the maximum element of LST. >>> max_iter([3, 7, 2, 5]) 7 """ x = lst 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)
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.