# Difference between revisions of "Iteration vs. recursion"

[checked revision] | [pending revision] |

m (fix link) |
(→Recursion → iteration) |
||

Line 88: | Line 88: | ||

</syntaxhighlight> | </syntaxhighlight> | ||

− | == | + | 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 == | == 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

## 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