CODEWITHSUNDEEP
pythonrecursion
user3206440
user3206440

Reputation: 5049

Recursion sequence - generic approach

We have the below classic recursion example for Fibonacci numbers

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

When we call fib(5), when the code is executed is there a sequence in which the fib(n-1) and fib(n-2) in the last line of fib() fcn would be executed - ie. to ask would the fib(n-1) part be first called, awaited the return and then the fib(n-2) part or they occur in parallel ?

Upvotes: 0

Views: 46

Answers (2)

9000
9000

Reputation: 40884

No, both computations will occur sequentially, and yes, this is a very wasteful way to compute Fibonacci series.

A less wasteful recursive function returns two consecutive numbers (current and previous):

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

An even better method uses matrix exponentiation, way more efficient.

Upvotes: 2

Scott Hunter
Scott Hunter

Reputation: 49803

The fib(n-1) part would be first computed and then the fib(n-2) part.

Upvotes: 1

Related Questions