3

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?

6
  • 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 Commented Oct 11, 2012 at 0:04
  • fib2(30), real: 0m0.032s, user: 0m0.025s, sys: 0m0.006s on Python 3. What version of Python are you using? Commented Oct 11, 2012 at 0:06
  • 1
    @JBoyer: This will have a runtime that blows up exponentially. Commented Oct 11, 2012 at 0:10
  • yeah it starts getting bad fast later ... thats just the nature of the beast... Commented Oct 11, 2012 at 0:10
  • 2
    @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. Commented Oct 11, 2012 at 0:16

3 Answers 3

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

1
  • 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 Commented Oct 11, 2012 at 15:53
2

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.