如何解释到达第n层的计数方式的代码？

Question

我试图从极客健忘者那里解读这段代码：

def fib(n): 
    if n <= 1: 
        return n 
    return fib(n-1) + fib(n-2) 

def countWays(s): 
    return fib(s + 1) 

s = 4
print "Number of ways = ", 
print countWays(s) 

当我把数字替换到函数中时，我似乎无法得到正确的答案。以下是我的思考过程：

def countWays(s): 
    return fib(4 + 1) #5

#this goes into fib(n). 5 is not less than or equal to n so I skip to the else statement:

fib(5-1) + fib(5-2) 

#fib(4) + fib(3) since these are still not less than or equal to n I input 
#them into the function again.

 fib(4-1) + fib(3-2) 

#fib(3) + fib(1) now that one of the n is less than or equal to n, 
#I return n and get 4 (3+1). The answer is supposed to be 5.

Answer 1

就像这样检查一下：

# Python 3
def fib(n): 
    print(f'Fib: {n}')
    if n <= 1:
        print('End')
        return n
    else:
        print(f'Send: {n-1} and {n-2}')
    return fib(n-1) + fib(n-2) 

def countWays(s): 
    return fib(s + 1) 

s = 4
print("Number of ways = ")
print(countWays(s))

结果

Fib: 5           # A
Send: 4 and 3    # A.B and A.C
Fib: 4           # A.B
Send: 3 and 2    # A.B.1 and A.B.2
Fib: 3           # A.B.1
Send: 2 and 1    # A.B.1.1 and A.B.1.2
Fib: 2           # A.B.1.1
Send: 1 and 0    # A.B.1.1.1 and A.B.1.1.2
Fib: 1           # A.B.1.1.1
End              # (END) A.B.1.1.1       -> 1
Fib: 0           # A.B.1.1.2
End              # (END) A.B.1.1.2       -> 0
Fib: 1           # A.B.1.2
End              # (END) A.B.1.2         -> 1
Fib: 2           # A.B.2
Send: 1 and 0    # A.B.2.1 and A.B.2.2
Fib: 1           # A.B.2.1
End              # (END) A.B.2.1         -> 1
Fib: 0           # A.B.2.2
End              # (END) A.B.2.2         -> 0
Fib: 3           # A.C
Send: 2 and 1    # A.C.1 and A.C.2
Fib: 2           # A.C.1
Send: 1 and 0    # A.C.1.1 and A.C.1.2
Fib: 1           # A.C.1.1
End              # (END) A.C.1.1         -> 1
Fib: 0           # A.C.1.2
End              # (END) A.C.1.2         -> 0
Fib: 1           # A.C.2
End              # (END) A.C.2           -> 1
5                                     # 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1

现在替代

>>> print(fib(5))
Fib: 5
Send: 4 and 3
Fib: 4
...
Fib: 1
End
5

同样的结果。