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.