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:

- look at the middle element
- if it is equal to the one we are looking for, we are done
- if it is greater, then our number should be in the lower half of the list
- if it is lesser, then our number should be in the upper half of the list
- 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.