Recursion Function In Python

Consider this basic recursion in Python: def fibonacci(number): if number == 0: return 0 elif number == 1: return 1 else: return fibonacci(number-1) + f

Solution 1:

Short Answer

Each time Python "sees" fibonacci() it makes another function call and doesn't progress further until it has finished that function call.

Example

So let's say it's evaluating fibonacci(4).

Once it gets to the line return fibonacci(number-1) + fibonacci(number-2), it "sees" the call fibonacci(number-1).

So now it runs fibonacci(3) - it hasn't seen fibonacci(number-2) at all yet. To run fibonacci(3), it must figure out fibonacci(2)+fibonacci(1). Again, it runs the first function it sees, which this time is fibonacci(2).

Now it finally hits a base case when fibonacci(2) is run. It evaluates fibonacci(1), which returns 1, then, for the first time, it can continue to the + fibonacci(number-2) part of a fibonacci() call. fibonacci(0) returns 0, which then lets fibonacci(2) return 1.

Now that fibonacci(3) has gotten the value returned from fibonacci(2), it can progress to evaluating fibonacci(number-2) (fibonacci(1)).

This process continues until everything has been evaluated and fibonacci(4) can return 3.

To see how the whole evaluation goes, follow the arrows in this diagram:

Solution 2:

In the expression fibonacci(number-1) + fibonacci(number-2) the first function call will have to complete before the second function call is invoked.

So, the whole recursion stack for the first call has to be complete before the second call is started.

Solution 3:

does the 'finobacci(number-1)' completes all the recursion until it reaches '1' and then it does the same with 'fibonacci(number-2)' and add them?

Yes, that's exactly right. In other words, the following

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

is equivalent to

f1 = fibonacci(number-1)
f2 = fibonacci(number-2)
return f1 + f2

Solution 4:

You can use the rcviz module to visualize recursions by simply adding a decorator to your recursive function.

Here's the visualization for your code above:

The edges are numbered by the order in which they were traversed by the execution. The edges fade from black to grey to indicate order of traversal: black edges first, grey edges last.

(I wrote the rcviz module on GitHub.)

Solution 5:

I would really recommend that you put your code in the Python tutor.

You will the be able to get it on the fly. See the stackframe, references, etc.