Recursion, Fib Numbers-CodePudding

On a call to fib(10), how many times is fib(4) computed? I can't seem to figure this out, could anyone help?

def fib ( n ):

        if n < 3:

            return 1

        else:

            return fib(n-1)   fib(n-2)

Trying to figure out how many times fib(4) is computed.

CodePudding user response：

Set T(n) = the times fib(n) call fib(4)

We know that

T(4)=1, T(5)=1

T(n) = T(n-1) T(n-2)

T(6) = T(5)   T(4) = 2
T(7) = T(6)   T(5) = 3
T(8) = T(7)   T(6) = 5
T(9) = T(8)   T(7) = 8
T(10) = T(9)   T(8) = 13

Also you can make some changes in your code

a = 0

def fib ( n ):
        if(n==4):
            global a
            a=a 1
            print(a)

        if n < 3:
            return 1

        else:
            return fib(n-1)   fib(n-2)

fib(10)

CodePudding user response：

You can add a counter to the function

def fib (n, cntr = None):
    if cntr is None:
        cntr = {}
    cntr[n] = cntr.get(n, 0)   1   # update count of current argumenet
    
    if n < 3:
        return 1
    else:
        return fib(n-1, cntr)   fib(n-2, cntr)  # mutate cntr in recursive calls

Test

cntr = {}              # Initialize counter
print(fib(10, cntr))   # Calculate fib(10)
# Output: 55

print(cntr[4])         # get count of number of times fib(4) called
# Output: 13