0

While studying from the book Algorithms by Michael Goodrich I came upon this "different than usual" recursive algorithm to compute the nth Fibonacci number. The algorithm isn't much explained in the book and the only answer I come up with is (1,1) .

def fibonacci(n):
    if n<=1:
        return (n,0)
    else:
        (a,b) = fibonacci(n-1)
        return (a+b,a)
print(fibonacci(5))

It does work perfectly but I just can't understand how is it working and I do know how recursion works . Any help would be appreciated thanks.

user9797560
  • 3
  • 2
  • Does this answer your question? [How does the fibonacci recursive function "work"?](https://stackoverflow.com/questions/8845154/how-does-the-fibonacci-recursive-function-work) – Majid Hajibaba Jul 19 '20 at 09:06
  • I don't think so, i know how that algorithm works it just returns f(n-1) + f(n-2) but in this algorithm it will never reach line 6 before n<=1 then how does the algorithm still computes the nth Fibonacci? – user9797560 Jul 19 '20 at 09:10

1 Answers1

0

In every recursive function, there is (must be) a stop point, which is a condition and a return value (for your example if n<=1: return (n,0))

So in your example you have:

F(5) => F(4) => F(3) => F(2) => F(1);

F(1) returns (1,0)

  • So F(2) pass line 5 and reach to line 6. And F(2) return (1,1).
  • Now F(3) pass line 5 and reach to line 6. And F(3) return (2,1).
  • Now F(4) pass line 5 and reach to line 6. And F(4) return (3,2).
  • Now F(5) pass line 5 and reach to line 6. And F(5) return (5,3).

The result will be (5,3).

Majid Hajibaba
  • 3,105
  • 6
  • 23
  • 55
  • Thank you so much for you help , i have been solving recusion problems but the really got me and I couldn't understand it . I still haven't got it fully . Thanks for your help though ! – user9797560 Jul 19 '20 at 09:31
  • You don't need to thanks in comments, Just upvote if the response is helpful or approve if it answers the question. Ask your new questions in comments if you have problem yet. – Majid Hajibaba Jul 19 '20 at 10:12