Python Fibonacci recursion (and not iteration) with O(n) time?

Question

I know my simple version of a Python Fibonacci algorithm has a time complexity of O(2^n)^2:

def fibonacci_naive(n):
    if n < 0:
        return None
    if n == 0 or n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

I'm trying to write another Fibonacci recursion, but with O(n) complexity instead. So far I can think of the how to do this with a simple for loop but I'm having trouble wrapping my head around how I can turn it into a recursive function instead. Any help is appreciated!

def fibonacci_fast(n):
    if n < 0:
        return None
    if n == 0 or n == 1:
        return 0
    if n == 2:
        return 1
    fn_minus_2 = 0
    fn_minus_1 = 1
    for _ in range(2, n+1):
        temp = fn_minus_2 + fn_minus_1
        fn_minus_2 = fn_minus_1
        fn_minus_1 = temp
    return fn_minus_1

def fibonacci_fast(n, fn_minus_1=1, fn_minus_2=0):
    if n < 0:
        return None
    if n == 0 or n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci_fast(???)

The Fibonacci sequence is one of the main examples why not to use recursion and think before implementing. The sequence is easily calculated by just adding the last two items together repeatedly, while some definition might lead you into a much more complex solution from the other direction, involving a fully grown tree of recursions. — Klaus D.
– Klaus D., Commented Mar 5, 2021 at 8:07
I think you just can't. You could use memoizing to cache already calculated values and prevent recursion calls, but better don't use recursion at all. — NobbyNobbs
– NobbyNobbs, Commented Mar 5, 2021 at 8:07
@NobbyNobbs you definitely can, you have to use recursion as an iterative process — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Mar 5, 2021 at 8:43

Alain T. · Accepted Answer · 2021-03-05 09:47:27Z

5

You can have defaulted parameters that move the sequence forward and use recursion to count down the number of elements:

def fibo(N,a=0,b=1): return fibo(N-1,b,a+b) if N else a

You can use the same approach to obtain the first N values of the sequence:

def fibo(N,a=0,b=1): return [a] + fibo(N-1,b,a+b) if N else []

edited Mar 5, 2021 at 9:47

answered Mar 5, 2021 at 8:51

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

juanpa.arrivillaga Over a year ago

ah this is much cleaner

juanpa.arrivillaga · Accepted Answer · 2021-03-05 08:57:13Z

3

You need to use an iterative process, something like:

def fib_r(n, depth=2, minus_1=1, minus_2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    elif depth < n:
        return fib_r(n=n, depth=depth+1, minus_1=minus_1 + minus_2, minus_2=minus_1)
    else:
        return minus_1 + minus_2

And just to show you, here it is compared to the version using iteration, basically, recursion acts as our loop:

In [1]: def fib(n):
   ...:     a, b = 0, 1
   ...:     for _ in range(n):
   ...:         a, b = b, a+b
   ...:     return a
   ...:

In [6]: def fibr(n, depth=2, a=1, b=0):
   ...:     if n == 0:
   ...:         return 0
   ...:     elif n == 1:
   ...:         return 1
   ...:     elif depth < n:
   ...:         return fibr(n=n, depth=depth+1, a=a+b, b=a)
   ...:     else:
   ...:         return a + b
   ...:
   ...:
    
In [3]: all(fib(i) == fibr(i) for i in range(1000))
Out[3]: True

So, everyone should read the Structure and Interpretation of Computer Programs by Ableson and Sussman.

Actually, MIT provides the PDF for free:

https://web.mit.edu/alexmv/6.037/sicp.pdf

Start reading section 1.2.1 about linear recursive processes versus iterative recursive processes (the efficient solution), and also, graph recursion (which is what the naive, inefficient solution uses).

edited Mar 5, 2021 at 8:57

answered Mar 5, 2021 at 8:30

juanpa.arrivillaga

97.6k14 gold badges141 silver badges190 bronze badges

5 Comments

idontknowanygoodusernames Over a year ago

Oh this makes sense! Is the acc=None parameter a mistake?

idontknowanygoodusernames Over a year ago

Also wouldn't it be possible to make n count down until it equals 2 rather than using depth? or would that not make sense...would it mess up minus_1 and minus_2?

idontknowanygoodusernames Over a year ago

oh yeah you're right, if we start from n and go backwards then we can't really use the defaults. Okay this works, thank you!

juanpa.arrivillaga Over a year ago

@idontknowanygoodusernames I've provided a link to a seminal textbook in computer science that explains this. The SCIP. It uses scheme, a dialect of LISP as a teaching language, which doesn't have loops, so you have to use recursion. It talks about linear recursive processes, iterative recursive processes (like the efficient recursive fibr), and tree recursion (the naive inefficient fib uses tree recursion). it actually talks about fibonnaci in section 1.2.2 and goes over both solutions!

juanpa.arrivillaga Over a year ago

@idontknowanygoodusernames and look at Alain T.'s solution for a version that counts down from N which is cleaner

seraph · Accepted Answer · 2021-03-05 08:38:49Z

0

I suppose you can learn much more from this post:

How to write the Fibonacci Sequence?

But I'll share a code anyway.

def fibonacci(n): 
      
    f = [0, 1] #first two nummber as 0, 1
     
    for i in range(2, n+1): #for i from range 2 to n+1
        f.append(f[i-1] + f[i-2])
    return f[n]

P/S: If I'm not mistaken, recursive fibonacci will always be O(2^n) / exponential

answered Mar 5, 2021 at 8:38

seraph

3502 silver badges15 bronze badges

Collectives™ on Stack Overflow

Python Fibonacci recursion (and not iteration) with O(n) time?

3 Answers 3

1 Comment

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related