CODEWITHSUNDEEP
pythonrecursionfibonacci
Mysteltainn
Mysteltainn

Reputation: 421

What is going on with the "return fibonacci... " in this program?

I have problem understanding what the return fibonacci( number-1 ) + fibonacci( number-2 ) does in the following program:

import sys
def fibonacci( number ):
    if( number <= 2  ):
        return 1
    else:
        return fibonacci( number-1 ) + fibonacci( number-2 )

The problem is that I can't imagine how this line works:

return fibonacci( number-1 ) + fibonacci( number-2 )

Does the both of the "fibonacci( number-1 )" and "fibonacci( number-2 )" being processed at the same time? or the "fibonacci( number-1 )" is the first to be processed and then the second one?

I only see that processing both of them would eventually return '1' so the last result I expect to see it is a '1 + 1' = '2'

I would appreciate a lot, If someone can elaborately explain the process of its calculation.

I think this is a very newb question but I can't really get a picture of its process.

Upvotes: 3

Views: 214

Answers (4)

Hugh Bothwell
Hugh Bothwell

Reputation: 56634

I very much like Nolen Royalty's answer, but it's still a bit hard to visualize. So, after a bit of mucking about: enter image description here

... where time flows left-to-right, with minor tweaking to prevent some overlapping edges. Leaf nodes, which do not recurse, are orange.

Upvotes: 2

Trufa
Trufa

Reputation: 40717

I had some trouble understanding recursion at first, so I'll try to go through the function.

Now lets say you call fibonacci(4)

Since the number is greater that 2 python will go to this line:

return fibonacci( number-1 ) + fibonacci( number-2 )

So it will start evaluating and call:

fibonacci(3) #this is fibonacci(4 - 1)

Since every time it encounters a function call it must run it (so to say).

So now it will try to do fibonacci(3), and since it is greater than 2:

it will go to this line again:

return fibonacci( number-1 ) + fibonacci( number-2 )

Now it was calling it with 3 so when it gets to fibonacci( number-1 ) it will do:

fibonacci(2) #this is fibonacci(3 - 1)

Since the numer is equal to 2, this recursive call will return 1. Now you have to remember/imagine that python knows the answer to fibonacci(2) so to say.

So now that it has an answer for fibonacci(2) it will continue to execute this line:

return fibonacci( number-1 ) + fibonacci( number-2 )

Specifically this: + fibonacci( number-2 )

Remember we are standing in fibonacci(2) so this will do fibonacci(1) and this will return 1.

So now when we return we start going back up so to say, we go out of the function recursively.

What was the problem? when we did fibonacci(4) we needed to know fibonacci(3),fibonacci(2),fibonacci(1) and now we know.

So when it goes out recursively to the fibonacci(3) it will need to know fibonacci(2) and fibonacci(1) and it knows, so now we now fibonacci(3).

Now we go back up to fibonacci(4) for which we need to know fibonacci(3) and fibonacci(2) and we know both so what will it return, the sum of both.

I hope it's clear, recursion is quite hard to follow but it gets better with practice.

Try to follow the function call by call writing down (in pencil) what calls are you calling, and the results you are getting from the calls.

Remember that in this kind of recursion you go down in the levels of recursion "looking for answers" and when you get those answers (returns) you go back up again to give the answers to unknown values.

Upvotes: 2

Nolen Royalty
Nolen Royalty

Reputation: 18633

Why don't you do something like this:

>>> def fibonacci(number):
...     if number < 2:
...         return number
...     print "Number is currently %d, getting fibonacci(%d)" % (number, number - 1)
...     minus_one = fibonacci(number-1)
...     print "Number is currently %d, just got fibonacci(%d), now getting fibonacci(%d)" % (number, number - 1, number - 2)
...     minus_two = fibonacci(number-2)
...     print "Number is currently %d, returning %d + %d" % (number, minus_one, minus_two)
...     return minus_one + minus_two

So that when you call fibonacci you get something like this:

>>> fibonacci(4)
Number is currently 4, getting fibonacci(3)
Number is currently 3, getting fibonacci(2)
Number is currently 2, getting fibonacci(1)
Number is currently 2, just got fibonacci(1), now getting fibonacci(0)
Number is currently 2, returning 1 + 0
Number is currently 3, just got fibonacci(2), now getting fibonacci(1)
Number is currently 3, returning 1 + 1
Number is currently 4, just got fibonacci(3), now getting fibonacci(2)
Number is currently 2, getting fibonacci(1)
Number is currently 2, just got fibonacci(1), now getting fibonacci(0)
Number is currently 2, returning 1 + 0
Number is currently 4, returning 2 + 1
3

It's still complex, but at least now you can see what the function is doing to calculate your number.

Upvotes: 5

Oded
Oded

Reputation: 498992

Does the both of the "fibonacci( number-1 )" and "fibonacci( number-2 )" being processed at the same time? or the "fibonacci( number-1 )" is the first to be processed and then the second one?

Does it matter?

What is happening is that the function is called twice. Once with the value of number -1 and once -2, for the value of number that was passed in to the current "instance" of the function.

Say you call fibonacci(3). That line would end up being:

return fibonacci(2) + fibonacci(1)

Upvotes: 3

Related Questions