python 2.7 - Recursive Fibonacci blows up

Question

I have two functions fib1 and fib2 to calculate Fibonacci.

def fib1(n):
    if n < 2:
        return 1
    else:
        return fib1(n-1) + fib1(n-2)

def fib2(n):
    def fib2h(s, c, n):
        if n < 1:
            return s
        else:
            return fib2h(c, s + c, n-1)
    return fib2h(1, 1, n)

fib2 works fine until it blows up the recursion limit. If understand correctly, Python doesn't optimize for tail recursion. That is fine by me.

What gets me is fib1 starts to slow down to a halt even with very small values of n. Why is that happening? How come it doesn't hit the recursion limit before it gets sluggish?

CPU times: user 0.35 s, sys: 0.00 s, total: 0.35 s Wall time: 0.35 s ... thats how long it took me for `fib1(30)` .. seems reasonable — Joran Beasley, Oct 11 '12 at 00:04
`fib2(30)`, real: 0m0.032s, user: 0m0.025s, sys: 0m0.006s on Python 3. What version of Python are you using? — Waleed Khan, Oct 11 '12 at 00:06
@JBoyer: This will have a runtime that blows up exponentially. — Omnifarious, Oct 11 '12 at 00:10
yeah it starts getting bad fast later ... thats just the nature of the beast... — Joran Beasley, Oct 11 '12 at 00:10
you could use memoization ... and start with smaller numbers and work up to the bigger ones... — Joran Beasley, Oct 11 '12 at 00:13
@JoranBeasley: Actually, memoization works regardless of where you start, as long as the recursive calls are also memoized. Fibonacci is the classic case for memoization in many examples of the technique. — Omnifarious, Oct 11 '12 at 00:16

John La Rooy · Accepted Answer · 2012-10-11T00:37:01.137

6

Basically, you are wasting lots of time by computing the fib1 for the same values of n over and over. You can easily memoize the function like this

def fib1(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        memo[n] = 1
    else:
        memo[n] =  fib1(n-1) + fib1(n-2)
    return memo[n]

You'll notice that I am using an empty dict as a default argument. This is usually a bad idea because the same dict is used as the default for every function call.

Here I am taking advantage of that by using it to memoize each result I calculate

You can also prime the memo with 0 and 1 to avoid needing the n < 2 test

def fib1(n, memo={0: 1, 1: 1}):
    if n in memo:
        return memo[n]
    else:
        memo[n] =  fib1(n-1) + fib1(n-2)
    return memo[n]

Which becomes

def fib1(n, memo={0: 1, 1: 1}):
    return memo.setdefault(n, memo.get(n) or fib1(n-1) + fib1(n-2))

edited Oct 11 '12 at 00:37

answered Oct 11 '12 at 00:28

John La Rooy

295,403
53
369
502

1

+1 for teaching me something new today by actually taking advantage of having a default argument reference the same object across multiple calls. – Platinum Azure Oct 11 '12 at 00:32
The later versions will result in infinite recursion for `n < 0`, though admittedly that isn't within the problem domain anyway. – Platinum Azure Oct 11 '12 at 14:10
wouldnt a decorator be prettier? :P – Joran Beasley Oct 11 '12 at 15:52
You can set the recursive limit up, sys.setrecursionlimit(1500) but you will eventually run out, the limit is finite. – radtek Jan 11 '15 at 22:39

score 5 · Answer 2 · edited May 23 '17 at 10:28

5

Your problem isn't python, it's your algorithm. fib1 is a good example of tree recursion. You can find a proof here on stackoverflow that this particular algorithm is (~θ(1.6ⁿ)).

n=30 (apparently from the comments) takes about a third of a second. If computational time scales up as 1.6^n, we'd expect n=100 to take about 2.1 million years.

edited May 23 '17 at 10:28

Community

1
1

answered Oct 11 '12 at 00:12

spencer nelson

4,365
3
24
22

nice :) I like your explanation of how long n=100 would take :) ... time to get about 2.1 million cores... then you can be done in only one year :P – Joran Beasley Oct 11 '12 at 15:53

score 2 · Answer 3 · answered Oct 11 '12 at 00:09

Think of the recursion trees in each. The second version is a single branch of recursion with the addition taking place in the parameter calculations for the function calls, and then it returns the values back up. As you have noted, Python doesn't require tail recursion optimization, but if tail call optimization were a part of your interpreter, the tail recursion optimization could be triggered as well.

The first version, on the other hand, requires 2 recursion branches at EACH level! So the number of potential executions of the function skyrockets considerably. Not only that, but most of the work is repeated twice! Consider: fib1(n-1) eventually calls fib1(n-1) again, which is the same as calling fib1(n-2) from the point of reference of the first call frame. But after that value is calculated, it must be added to the value of fib1(n-2) again! So the work is needlessly duplicated many times.

python 2.7 - Recursive Fibonacci blows up

3 Answers3