Stack Abuse: Understanding Recursive Functions with Python

Introduction

When we think about repeating a task, we usually think about the for and while loops. These constructs allow us to perform iteration over a list, collection, etc.

However, there's another form of repeating a task, in a slightly different manner. By calling a function within itself, to solve a smaller instance of the same problem, we're performing recursion.

These functions call themselves until the problem is solved, practically dividing the initial problem to a lot of smaller instances of itself – like for an example, taking small bites of a larger piece of food.

The end goal is to eat the entire plate of hot pockets, you do this by taking a bite over and over. Each bite is a recursive action, after which you undertake the same action the next time. You do this for every bite, evaluating that you should take another one to reach the goal, until there are no hot pockets left on your plate.

What is Recursion?

As stated in the introduction, recursion involves a process calling itself in the definition. A recursive function generally has two components:

• The base case which is a condition that determines when the recursive function should stop
• The call to itself

Let's take a look at a small example to demonstrate both components:

# Assume that remaining is a positive integer
def hi_recursive(remaining):  
    # The base case
    if remaining == 0:
        return
    print('hi')

    # Call to function, with a reduced remaining count
    hi_recursive(remaining - 1)

The base case for us is if the remaining variable is equal to 0 i.e. how many remaining "hi" strings we must print. The function simply returns.

After the print statement, we call hi_recursive again but with a reduced remaining value. This is important! If we do not decrease the value of remaining the function will run indefinitely. Generally, when a recursive function calls itself the parameters are changed to be closer to the base case.

Let's visualize how it works when we call hi_recursive(3):

After the function prints 'hi', it calls itself with a lower value for remaining until it reaches 0. At zero, the function returns to where it was called in hi_recursive(1), which returns to where it was called in hi_recursive(2) and that ultimately returns to where it was called in hi_recursive(3).

Why not use a Loop?

All traversal can be handled with loops. Even so, some problems are often easier solved with recursion rather than iteration. A common use case for recursion is tree traversal:

Traversing through nodes and leaves of a tree is usually easier to think about when using recursion. Even though loops and recursion both traverse the tree, they have different purposes – loops are meant to repeat a task whereas recursion is meant to break down a large task into smaller tasks.

Recursion with trees for example fork well because we can process the entire tree by processing smaller parts of the tree individually.

Examples

The best way to get comfortable with recursion, or any programming concept, is to practice it. Creating recursive functions are straightforward: be sure to include your base case and call the function such that it gets closer to the base case.

Sum of a List

Python includes a sum function for lists. The default Python implementation, CPython, uses an indefinite for-loop in C to create those functions (source code here for those interested). Let's see how to do it with recursion:

def sum_recursive(nums):  
    if len(nums) == 0:
        return 0

    last_num = nums.pop()
    return last_num + sum_recursive(nums)

The base case is the empty list - the best sum for that is 0. Once we handle our base case, we remove the last item of the list. We finally call the sum_recursive function with the reduced list, and we add the number we pulled out into the total.

In a Python interpreter sum([10, 5, 2]) and sum_recursive([10, 5, 2]) should both give you 17.

Factorial Numbers

You may recall that a factorial of a positive integer, is the product of all integers preceding it. The following example would make it clearer:

5! = 5 x 4 x 3 x 2 x 1 = 120  

The exclamation mark denotes a factorial, and we see that we multiply 5 by the product of all the integers from 4 till 1. What if someone enters 0? It's widely understood and proven that 0! = 1. Now let's create a function like below:

def factorial(n):  
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

We cater for the cases where 1 or 0 is entered, and otherwise we multiply the current number by the factorial of the number decreased by 1.

A simple verification in your Python interpreter would show that factorial(5) gives you 120.

Fibonacci Sequence

A Fibonacci sequence is one where each number is the sum of the proceeding two numbers. This sequence makes an assumption that Fibonacci numbers for 0 and 1 are also 0 and 1. The Fibonacci equivalent for 2 would therefore be 1.

Let's see the sequence and their corresponding natural numbers:

    Integers:   0, 1, 2, 3, 4, 5, 6, 7
    Fibonacci:  0, 1, 1, 2, 3, 5, 8, 13

We can easily code a function in Python to determine the fibonacci equivalent for any positive integer using recursion:

def fibonacci(n):  
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

You can verify it works as expected by checking that fibonacci(6) equals to 8.

Now I'd like you to consider another implementation of this function that uses a for loop:

def fibonacci_iterative(n):  
    if n <= 1:
        return n

    a = 0
    b = 1
    for i in range(n):
        temp = a
        a = b
        b = b + temp
    return a

If the integer is less than or equal to 1, then return it. Now that our base case is handled. We continuously add the first number with the second one by storing the first number in a temp variable before we update it.

The output is the same as the first fibonacci() function. It's possible that it may even be faster. The solution however, is not as easily readable as our first attempt. There lies one of recursion's greatest powers: elegance. Some programming solutions are most naturally solved using recursion.

Conclusion

Recursion allows us to break a large task down to smaller tasks by repeatedly calling itself. A recursive function requires a base case to stop execution, and the call to itself which gradually leads to the function to the base case. It's commonly used in trees, but other functions can be written with recursion to provide elegant solutions.

from Planet Python
via read more