CODEWITHSUNDEEP
pythonrecursion
JBoyer
JBoyer

Reputation: 43

python 2.7 - Recursive Fibonacci blows up

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?

Upvotes: 3

Views: 1088

Answers (3)

John La Rooy
John La Rooy

Reputation: 304147

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))

Upvotes: 6

spencer nelson
spencer nelson

Reputation: 4525

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.6n)).

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.

Upvotes: 5

Platinum Azure
Platinum Azure

Reputation: 46183

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.

Upvotes: 2

Related Questions