# Basics of recursion in Python

Posted on

### Question :

Basics of recursion in Python

“Write a recursive function, “listSum” that takes a list of integers and returns the sum of all integers in the list”.

Example:

``````>>>> listSum([1,3,4,5,6])
19
``````

I know how to do this another way but not in the recursive way.

``````def listSum(ls):
i = 0
s = 0
while i < len(ls):
s = s + ls[i]
i = i + 1
print s
``````

I need the basic way to do this since special built-in functions is not allowed.

Whenever you face a problem like this, try to express the result of the function with the same function.

In your case, you can get the result by adding the first number with the result of calling the same function with rest of the elements in the list.

For example,

``````listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6])
= 1 + (3 + listSum([4, 5, 6]))
= 1 + (3 + (4 + listSum([5, 6])))
= 1 + (3 + (4 + (5 + listSum([6]))))
= 1 + (3 + (4 + (5 + (6 + listSum([])))))
``````

Now, what should be the result of `listSum([])`? It should be 0. That is called base condition of your recursion. When the base condition is met, the recursion will come to an end. Now, lets try to implement it.

The main thing here is, splitting the list. You can use slicing to do that.

Simple version

``````>>> def listSum(ls):
...     # Base condition
...     if not ls:
...         return 0
...
...     # First element + result of calling `listsum` with rest of the elements
...     return ls[0] + listSum(ls[1:])
>>>
>>> listSum([1, 3, 4, 5, 6])
19
``````

Tail Call Recursion

Once you understand how the above recursion works, you can try to make it a little bit better. Now, to find the actual result, we are depending on the value of the previous function also. The `return` statement cannot immediately return the value till the recursive call returns a result. We can avoid this by, passing the current to the function parameter, like this

``````>>> def listSum(ls, result):
...     if not ls:
...         return result
...     return listSum(ls[1:], result + ls[0])
...
>>> listSum([1, 3, 4, 5, 6], 0)
19
``````

Here, we pass what the initial value of the sum to be in the parameters, which is zero in `listSum([1, 3, 4, 5, 6], 0)`. Then, when the base condition is met, we are actually accumulating the sum in the `result` parameter, so we return it. Now, the last `return` statement has `listSum(ls[1:], result + ls[0])`, where we add the first element to the current `result` and pass it again to the recursive call.

This might be a good time to understand Tail Call. It would not be relevant to Python, as it doesn’t do Tail call optimization.

Passing around index version

Now, you might think that we are creating so many intermediate lists. Can I avoid that?

Of course, you can. You just need the index of the item to be processed next. But now, the base condition will be different. Since we are going to be passing index, how will we determine how the entire list has been processed? Well, if the index equals to the length of the list, then we have processed all the elements in it.

``````>>> def listSum(ls, index, result):
...     # Base condition
...     if index == len(ls):
...         return result
...
...     # Call with next index and add the current element to result
...     return listSum(ls, index + 1, result + ls[index])
...
>>> listSum([1, 3, 4, 5, 6], 0, 0)
19
``````

Inner function version

If you look at the function definition now, you are passing three parameters to it. Lets say you are going to release this function as an API. Will it be convenient for the users to pass three values, when they actually find the sum of a list?

Nope. What can we do about it? We can create another function, which is local to the actual `listSum` function and we can pass all the implementation related parameters to it, like this

``````>>> def listSum(ls):
...
...     def recursion(index, result):
...         if index == len(ls):
...             return result
...         return recursion(index + 1, result + ls[index])
...
...     return recursion(0, 0)
...
>>> listSum([1, 3, 4, 5, 6])
19
``````

Now, when the `listSum` is called, it just returns the return value of `recursion` inner function, which accepts the `index` and the `result` parameters. Now we are only passing those values, not the users of `listSum`. They just have to pass the list to be processed.

In this case, if you observe the parameters, we are not passing `ls` to `recursion` but we are using it inside it. `ls` is accessible inside `recursion` because of the closure property.

Default parameters version

Now, if you want to keep it simple, without creating an inner function, you can make use of the default parameters, like this

``````>>> def listSum(ls, index=0, result=0):
...     # Base condition
...     if index == len(ls):
...         return result
...
...     # Call with next index and add the current element to result
...     return listSum(ls, index + 1, result + ls[index])
...
>>> listSum([1, 3, 4, 5, 6])
19
``````

Now, if the caller doesn’t explicitly pass any value, then `0` will be assigned to both `index` and `result`.

Recursive Power problem

Now, lets apply the ideas to a different problem. For example, lets try to implement the `power(base, exponent)` function. It would return the value of `base` raised to the power `exponent`.

``````power(2, 5) = 32
power(5, 2) = 25
power(3, 4) = 81
``````

Now, how can we do this recursively? Let us try to understand how those results are achieved.

``````power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32
power(5, 2) = 5 * 5             = 25
power(3, 4) = 3 * 3 * 3 * 3     = 81
``````

Hmmm, so we get the idea. The `base` multiplied to itself, `exponent` times gives the result. Okay, how do we approach it. Lets try to define the solution with the same function.

``````power(2, 5) = 2 * power(2, 4)
= 2 * (2 * power(2, 3))
= 2 * (2 * (2 * power(2, 2)))
= 2 * (2 * (2 * (2 * power(2, 1))))
``````

What should be the result if anything raised to power 1? Result will be the same number, right? We got our base condition for our recursion ðŸ™‚

``````            = 2 * (2 * (2 * (2 * 2)))
= 2 * (2 * (2 * 4))
= 2 * (2 * 8)
= 2 * 16
= 32
``````

Alright, lets implement it.

``````>>> def power(base, exponent):
...     # Base condition, if `exponent` is lesser than or equal to 1, return `base`
...     if exponent <= 1:
...         return base
...
...     return base * power(base, exponent - 1)
...
>>> power(2, 5)
32
>>> power(5, 2)
25
>>> power(3, 4)
81
``````

Okay, how will be define the Tail call optimized version of it? Lets pass the current result as the parameter to the function itself and return the result when the base condition it met. Let’s keep it simple and use the default parameter approach directly.

``````>>> def power(base, exponent, result=1):
...     # Since we start with `1`, base condition would be exponent reaching 0
...     if exponent <= 0:
...         return result
...
...     return power(base, exponent - 1, result * base)
...
>>> power(2, 5)
32
>>> power(5, 2)
25
>>> power(3, 4)
81
``````

Now, we reduce the `exponent` value in every recursive call and multiple `result` with `base` and pass it to the recursive `power` call. We start with the value `1`, because we are approaching the problem in reverse. The recursion will happen like this

``````power(2, 5, 1) = power(2, 4, 1 * 2)
= power(2, 4, 2)
= power(2, 3, 2 * 2)
= power(2, 3, 4)
= power(2, 2, 4 * 2)
= power(2, 2, 8)
= power(2, 1, 8 * 2)
= power(2, 1, 16)
= power(2, 0, 16 * 2)
= power(2, 0, 32)
``````

Since `exponent` becomes zero, the base condition is met and the `result` will be returned, so we get `32` ðŸ™‚

Early exit is typical for recursive functions. `seq` is falsy when empty (therefore when there are no numbers left to sum).

Slice syntax allows to pass sequence to recursively called function without integer consumed in current step.

``````def listSum(seq):
if not seq:
return 0
return seq[0] + listSum(seq[1:])

print listSum([1,3,4,5,6])  # prints 19
``````

``````def listSum(L):
"""Returns a sum of integers for a list containing
integers.
input: list of integers
output: listSum returns a sum of all the integers
in L.
"""
if L == []:
return []
if len(L) == 1:
return L[0]
else:
return L[0] + listSum(L[1:])
print listSum([1, 3, 4, 5, 6])
print listSum([])
print listSum([8])
``````

Another version:

``````def listSum(ls):
ls_len = len(ls)

# Base condition
if ls_len==1:
return ls[0]
if ls_len==0:
return None
# ls = listSum(ls[0:i]) + listSum(ls[i:])
elif ls_len%2==0:
i = int(ls_len/2)
return listSum(ls[0:i]) + listSum(ls[i:])
else:
i = int((ls_len-1)/2)
return listSum(ls[0:i]) + listSum(ls[i:])
``````

Follow @thefourtheye’s example, we can say:

``````listSum([1, 3, 4, 5, 6]) = listSum([1, 3]) + listSum([4, 5, 6])
= (listSum([1]) + listSum([3])) + (listSum([4]) + listSum([5, 6]))
= (listSum([1]) + listSum([3])) + (listSum([4]) + (listSum([5]) + listSum([6])))
``````

Base condition: when `ls` only has one element, return this value.

``````def listsum(list):
The basic idea behind this recursive function is that we want to check if we have a base case which is shown as `if len(list) == 1:`. For the base case we just return the value in the list `return list[0]`, otherwise, we still have multiple elements in the list. In the `else:` statement we will add the first element from the list which is `list[0]` to the rest of the elements in the list.This is shown by calling the function recursively with the list shorter by 1 element–the element at index 0– `listsum(list[1:])`, this process repeats with the list getting smaller until you arrive at the base case–a list of length 1 and then you will get a final result.