Рекурсия последовательность - общий подход

Question

У нас есть ниже классический пример рекурсии для чисел Фибоначчи

def fib(n): 
    assert type(n) == int & n >= 0 
    if n == 0 or n == 1: 
     return 1 
    else: 
     return fib(n-1) + fib(n-2) 

fib(5) #=> 8 

Когда мы называем выдумка (5), когда код выполняется есть последовательность, в которой выдумка (п-1) и fib (n-2) в последней строке fib() fcn будет выполняться - т.е. спросить, будет ли сначала вызвана часть fib (n-1), ожидаемая обратная связь, а затем часть fib (n-2) или они происходят параллельно?

Answer 1

Сначала будет вычислена часть fib (n-1), а затем часть fib (n-2).

Answer 2

Нет, оба вычисления будут происходить последовательно, и да, это очень расточительный способ вычислить серии Фибоначчи.

Менее расточительная рекурсивная функция возвращает два последовательные номера (текущие и предыдущие):

def fib2(n): 
    if n == 1: 
    return (0, 1) 
    else: 
    prev_1, prev_2 = fib2(n-1) 
    return (prev_1 + prev_2, prev_1) 

def fib(n): 
    value, _ = fib2(n) 
    return value 

еще лучший метод uses matrix exponentiation, способ более эффективны.