Python recursion function

Question

Consider this basic recursion in Python:

def fibonacci(number): if number == 0: return 0 elif number == 1: return 1 else: return fibonacci(number-1) + fibonacci(number-2) 

Which makes sense in accordance with the (n-1) + (n-2) function of the Fibonacci series.

How does Python execute a recursion that contains another recursion, not inside, but inside the same line of code? Does "finobacci (number-1)" get all the recursion until it reaches "1", and then does the same with "fibonacci (number-2)" and add them?

For comparison, the following recursive function to raise the number "x" to the power of "y", I can understand the recursion, def power, calling itself up to y == 0, since there is only one recursive call in one line. Still, not all results will be "1", since the last command executed is "return 1" when y == 0, so x does not return?

 def power(x, y): if y == 0: return 1 else: return x*power(x, y-1) 

Answer 1

In the expression fibonacci(number-1) + fibonacci(number-2) first function call must end before the second function call is called.

So, the entire recursion stack for the first call must be completed before the start of the second call.

Answer 2

Short answer

Each time Python "sees" fibonacci() , it makes another call to the function and does not move on until it completes this call to the function.

Example

So let's say he evaluates fibonacci(4) .

As soon as it gets into the string return fibonacci(number-1) + fibonacci(number-2) , it "sees" the call to fibonacci(number-1) .

So now it works fibonacci(3) - he hasn't seen fibonacci(number-2) yet. To start fibonacci(3) , he must find fibonacci(2)+fibonacci(1) . Again, it launches the first function that it sees, this time fibonacci(2) .

Now it finally gets into the base register when fibonacci(2) is executed. It evaluates fibonacci(1) , which returns 1 , then for the first time it can continue part + fibonacci(number-2) calling fibonacci() . fibonacci(0) returns 0 , which then returns fibonacci(2) return 1 .

Now that fibonacci(3) received the value returned from fibonacci(2) , it can go on to evaluate fibonacci(number-2) ( fibonacci(1) ).

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

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

Answer 3

Does "finobacci (number-1)" complete the entire recursion before reaching "1", and then does the same with "fibonacci (number-2)" and add them?

Yes, that's for sure. In other words, the following

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

equivalently

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

Answer 4

I would recommend you put your code in a Python teacher .

You can get it on the fly. See Stack, links, etc.

Answer 5

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

Here's the visualization for your code above:

The ribs are numbered in the order in which they were completed. The edges disappear from black to gray to indicate the traversal order: black edges first, gray edges last.

(I wrote the rcviz module on GitHub .)

Answer 6

Your second recursion function does this (example), so 1 will not be returned.

 power(2, 3) 2 * power(2, 2) 2 * 2 * power(1,2) 2 * 2 * 2 * power(0,2) # Reaching base case 2 * 2 * 2 * 1 8 

Answer 7

You can figure it out yourself by putting the print function in the function and adding depth so that we can print it more beautifully:

 def fibonacci(number, depth = 0): print " " * depth, number if number == 0: return 0 elif number == 1: return 1 else: return fibonacci(number-1, depth + 1) + fibonacci(number-2, depth + 1) 

Calling fibonacci(5) gives us:

 5 4 3 2 1 0 1 2 1 0 3 2 1 0 1 

We see that 5 calls 4 , which goes to completion, and then calls 3 , which then ends.

Answer 8

Matthew and Martine are right, but I thought I could clarify:

Python does things from left to right whenever possible. Exceptions to this rule are implied in parentheses.

in x*power(x, y-1) : x is evaluated then power is rated

While in fibonacci(number-1) + fibonacci(number-2) , fibonacci(number-1) is evaluated (recursively until it stops) and then fibonacci(number-1) is evaluated

Answer 9

 def fib(n): if n <= 1: return n else : return fib(n - 1) + fib(n - 2)