Python: Recursion, Part Duex

I ended up on a roll tonight writing my documentation on python recursive functions and decided to continue writing the second portion of this blog entry ,first post found here. In this post I plan to provide you with a slightly more complicated example of a recursive function while also showing a side-by-side comparison of recursion vs. iteration (Spoiler alert, iteration wins!).

Italians and integers, breeding like rabbits!

My example algorithm that I am introducing for advanced recursive method usage is none other than the Fibonacci number.

The Fibonacci numbers are a sequence of the following integer values:

[0,1,1,2,3,5,8,13,21,34,55,89,144 …]

The Fibonacci numbers are defined by the equation:

1
2

Fn = Fn-1 + Fn-2
with F0 = 0 and F1 = 1

The Fibonacci sequence(numbers) are named after the mathematician Leonardo of Pisa, who is better known as Fibonacci. In his book “Liber Abaci” (published 1202) he introduced the sequence as an exercise dealing with (biologically unrealistic) rabbit breeding habits. His sequence of the Fibonacci numbers begins with F1 = 1, while in modern mathematics the sequence starts with F0 = 0. But this has no effect on the other members of the sequence.

OK, now that you are familiar with the introduction of Fionacci numbers lets get to the gooey, nerdy center of this example! ☺

Solving for Fibonacci sequencing in Python

The Fibonacci numbers are the result of an artificial rabbit population, satisfying the following conditions:

A newly born pair of rabbits, one male, one female, build the initial population. The rabbits are able to successfully mate at the age of one month. This means that at the end of the second month of life, the female rabbit gives birth to 2 “hoppy”(harhar), healthy rabbits. The new sibling pair of rabbits consist of 1 male and one female. Did I mention that all of the rabbit spawn are immortal?!? Every rabbit from here on out will never die and just keep producing offspring. What a job, eh? Every new pair of male|female rabbits will continue to mate after the second month of life until infinity. The Fibonacci numbers are the numbers of rabbit pairs after n months, i.e. after 10 months we will have F10 rabbits.

The Fibonacci equation is very easy to program, as your equation depicted within the code is almost 1:1 with the original equation:

1
2
3
4
5
6
7

def fibonacci_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

The above example depicts the Fibonacci numbers solution by using recursive methods. Now I will provide an example of a python function that returns the same Fibonacci numbers only using iteration instead of recursion.

1
2
3
4
5

def fibonacci_iterative(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

If you try both of these functions in your python interpreter you will notice that fibonacci_iterative method is “Orders of magnitude” faster than the fibonacci_recursive equivalent.

Why is recursion so slow?!

In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame. In some C compilers, one can use a compiler flag to eliminate this overhead, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls.

In functional programming language implementations, sometimes, iteration can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations, which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

There are practical ways that we can help along recursive functions in order to speed them up however. Lets move onto the race between recursion vs. iteration and then we can describe how to speed up our recursion functions in this example.

The great race

In the example below we are going to place both of our above Fibonacci functions into an importable python file. Then we are going to write a new script that imports / executes both functions while performing timing calculations comparing the execution times.

1
2
3
4
5
6
7
8
9
10
11
12
13

def fibonacci_iterative(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def fibonacci_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

Now we will write a python script that will allow for us to import and execute the two functions within “import_me.py” and measure the execution times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from timeit import Timer
from import_me import fibonacci_recursive

t1 = Timer("fibonacci_recursive(10)","from import_me import fibonacci_recursive")

for i in range(1,41):
    #Import, execute and time recursive function.
    s = ("fibonacci_recursive(" + str(i) + ")")
    t1 = Timer(s,"from import_me import fibonacci_recursive")
    time1 = t1.timeit(3)

    #Import, execute and time iterative function. 
    s = ("fibonacci_iterative(" + str(i) + ")")
    t2 = Timer(s,"from import_me import fibonacci_iterative")
    time2 = t2.timeit(3)

    print("n=%2d, recursive exec time: %8.6f, iterative exec time:  %7.6f, iterative percent faster: %10.2f" % (i, time1, time2, time1/time2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

n= 1, recursive exec time: 0.000005, iterative exec time:  0.000007, iterative percent faster:       0.72
n= 2, recursive exec time: 0.000007, iterative exec time:  0.000007, iterative percent faster:       1.00
n= 3, recursive exec time: 0.000008, iterative exec time:  0.000007, iterative percent faster:       1.14
n= 4, recursive exec time: 0.000011, iterative exec time:  0.000008, iterative percent faster:       1.35
n= 5, recursive exec time: 0.000017, iterative exec time:  0.000008, iterative percent faster:       2.09
n= 6, recursive exec time: 0.000026, iterative exec time:  0.000008, iterative percent faster:       3.21
n= 7, recursive exec time: 0.006997, iterative exec time:  0.000016, iterative percent faster:     438.01
n= 8, recursive exec time: 0.000060, iterative exec time:  0.000009, iterative percent faster:       6.63
n= 9, recursive exec time: 0.000093, iterative exec time:  0.000010, iterative percent faster:       9.29
n=10, recursive exec time: 0.000148, iterative exec time:  0.000010, iterative percent faster:      14.79
n=11, recursive exec time: 0.000236, iterative exec time:  0.000010, iterative percent faster:      23.57
n=12, recursive exec time: 0.000381, iterative exec time:  0.000010, iterative percent faster:      38.05
n=13, recursive exec time: 0.007792, iterative exec time:  0.000012, iterative percent faster:     653.64
n=14, recursive exec time: 0.001105, iterative exec time:  0.000012, iterative percent faster:      92.70
n=15, recursive exec time: 0.008806, iterative exec time:  0.000012, iterative percent faster:     724.22
n=16, recursive exec time: 0.010133, iterative exec time:  0.000017, iterative percent faster:     598.61
n=17, recursive exec time: 0.019284, iterative exec time:  0.000018, iterative percent faster:    1064.25
n=18, recursive exec time: 0.022575, iterative exec time:  0.000017, iterative percent faster:    1333.61
n=19, recursive exec time: 0.056988, iterative exec time:  0.000020, iterative percent faster:    2845.54
n=20, recursive exec time: 0.079930, iterative exec time:  0.000019, iterative percent faster:    4243.67
n=21, recursive exec time: 0.114535, iterative exec time:  0.000018, iterative percent faster:    6405.25
n=22, recursive exec time: 0.157802, iterative exec time:  0.000018, iterative percent faster:    8708.80
n=23, recursive exec time: 0.261647, iterative exec time:  0.000018, iterative percent faster:   14439.83
n=24, recursive exec time: 0.425641, iterative exec time:  0.000018, iterative percent faster:   23803.57
n=25, recursive exec time: 0.685106, iterative exec time:  0.000019, iterative percent faster:   35919.29
n=26, recursive exec time: 1.090093, iterative exec time:  0.000018, iterative percent faster:   60962.41
n=27, recursive exec time: 1.777188, iterative exec time:  0.000019, iterative percent faster:   93175.84
n=28, recursive exec time: 2.874248, iterative exec time:  0.000020, iterative percent faster:  143517.50

In part three of this blog series I will cover in greater detail why the recursive solution is slower than the iterative solution. I will also cover some tips / tricks that we can do to help tune the recursive function in order to make it perform much like its iterative counterpart.

-g