Considere esta recursão básica em Python:

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

O que faz sentido de acordo com a função (n-1) + (n-2) da série de Fibonacci.

Como o Python executa a recursão que contém outra recursão não dentro, mas dentro da mesma linha de código? O 'finobacci (número-1)' completa toda a recursão até atingir '1' e depois faz o mesmo com 'fibonacci (número-2)' e os adiciona?

Para comparação, a seguinte função recursiva para elevar um número 'x' para poder 'y', eu posso entender a recursividade, def power chamando a si mesmo até y == 0, já que há apenas uma chamada recursiva em uma única linha. Ainda assim, todos os resultados não devem ser '1', pois o último comando executado é 'return 1' quando y == 0, portanto x não é retornado?

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