Recursion vs iteration

A recent tutorial for the students was about the differece between recursion and iteration.
The most effective way to explain it was the following:

  • iteration requires a set of values, and you perform the same operations on each of them until you are done
  • recursion implies an operation on an input, that has a result depending on the same operation on smaller inputs up to a very simple one (like zero or one) with an easy answer

The classic example for recursion is the computation of a factorial. The factorial of a number n, denoted by n!,  is the product of all the numbers up to n. So 3! = 1 x 2 x 3, 5! = 1 x 2 x 3 x 4 x 5.

It is easy to implement recursively in Python as:

def fact(n):
    if n==1:
       return 1
    else:
       return n*fact(n-1)

As you can see, we have the simple input when n equals to 1, otherwise the value depends on a smaller input (n-1).

If you can write a recursive function for a task, you can also write an iterative version of the same task.

def fact(n):
    result = 1
    for i in range(1,n+1):
        result = result * i
    return result

The iterative version requires a variable to store intermediate results.

A more complex example is the binary search. The input for binary search is a sorted list of elements, for example numbers. It is faster to find the presence of a value in the list using the following approach:

  1. look at the middle element
  2. if it is equal to the one we are looking for, we are done
  3. if it is greater, then our number should be in the lower half of the list
  4. if it is lesser, then our number should be in the upper half of the list
  5. repeat from step 1 for the appropriate half

In this case, the recursive version is straghtforward too:

def binary_search(l,n):
    #l is the list, n is the element to be found
    if len(l)>0:
       mid = len(l)/2
       if l[mid]==n:
          return True
       elif l[mid]>n:
          return binary_search(l[:mid],n)
       elif l[mid]<n:
          return binary_search(l[mid+1:],n)
    else: #empty list
       return False

However, if we also want the position of the element, we need few more parameters:

def binary_search(l,n,low,high):
    if high<low:
       return None
    else:
       mid = (high-low)/2+low
       if l[mid]==n:
          return mid
       elif l[mid]>n:
          return binary_search(l,n,low,mid-1)
       elif l[mid]<n:
          return binary_search(l,n,mid+1,high)

To create an iterative version of this, a while loop is required:

def binary_search(l,n,low,high):
    while low<=high:
        mid = (high-low)/2+low
        if l[mid]==n:
          return mid
        elif l[mid]>n:
          high = mid-1
        elif l[mid]<n:
          low = mid+1
    return None

In this last case, there is not a clear list of inputs, like in the factorial example, but we have an exit condition similar to the one used by recursion.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s