Recursion function in Python

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 according to the (n-1) + (n-2) function of the Fibonacci series.

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

For comparison, the following recursive function for raising a number 'x' into power 'y', I can understand the recursion, def power calling itself until y==0 , since there's only one recursive call in a single line. Still shouldn't all results be '1' since the last command executed is 'return 1' when y==0, therefore x is not returned?

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

Answer 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: