# 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