換人跟蹤Python代碼

Question

我想這個代碼做了替換跟蹤：

def hanoi(n): 
    if n == 1: 
     return 1 
    else: 
     return 2 * hanoi(n - 1) + 1 

print hanoi(4) 

輸出：

15 

這是我做過什麼：

2 * (4 - 1) + 1 

2 * (3) + 1 

6 + 1 

7 

我我不知道我做錯了什麼。

Answer 1

你有遞歸功能，每一個步驟後，轉換爲子功能與n-1： 其實你有這樣的：

2 * hanoi(4 - 1) + 1 
2 * hanoi(3) + 1 
2 * (2 * hanoi(2) + 1) + 1 
2 * (2 * (2 * hanoi(1) + 1) + 1) + 1 
2 * (2 * (2 * 1 + 1) + 1) + 1 = 15 

Answer 2

2 * hanoi(4-1) + 1是不一樣的2 * (4-1) + 1