Difference between revisions of "Iteration vs. recursion"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][pending revision]
m (fix link)
(Recursion → iteration)
 
Line 88: Line 88:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
== Recursion → iteration ==
+
int rec(int n)
A tail recursive function can be converted to an iterative function using the same idea as [[#Iteration → recursion|above]]. A more complicated recursive function will require a stack to convert to an iterative function. This is outside the scope of 61A.
+
{
 +
if ( f(n) == FALSE ) {
 +
/* any group of statements that do not change the value of n */
 +
return (rec(g(n)));
 +
}//end if
 +
return (0);
 +
}//end rec
  
 
== Sources ==
 
== Sources ==

Latest revision as of 14:21, 19 September 2016

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)

int rec(int n) { if ( f(n) == FALSE ) { /* any group of statements that do not change the value of n */ return (rec(g(n))); }//end if return (0); }//end rec

Sources