在河內塔計數函數調用？

Question

所以我想算功能moveSingleDisk（）有多少時間被調用，但我似乎無法推測出來......使用此代碼：

#include <iostream> 
using namespace std; 

void moveTower(int n, char start, char finish, char temp, int count); 
void moveSingleDisk(char moveFrom, char moveTo, int count); 
void calcHanoi(int n); 

int main (int argc, const char * argv[]) 
{ 
    calcHanoi(5); 
    return 0; 
} 

void calcHanoi(int n) 
{ 
    int count = 0; 
    moveTower(n, 'A', 'B', 'C', count); 
} 

void moveTower(int n, char start, char finish, char temp, int count) 
{ 
    if (n == 1) 
    { 
     count++; 
     moveSingleDisk(start, finish, count); 
     return; 
    } 
    moveTower(n-1, start, temp, finish, count); 
    count++; 
    moveSingleDisk(start, finish, count); 
    moveTower(n-1, temp, finish, start, count); 
} 

void moveSingleDisk(char moveFrom, char moveTo, int count) 
{ 
    cout << count << ": " << moveFrom << " -> " << moveTo << endl; 
} 

我得到以下輸出：

1: A -> B 
1: A -> C 
2: B -> C 
1: A -> B 
2: C -> A 
2: C -> B 
3: A -> B 
1: A -> C 
2: B -> C 
2: B -> A 
3: C -> A 
2: B -> C 
3: A -> B 
3: A -> C 
4: B -> C 
1: A -> B 
2: C -> A 
2: C -> B 
3: A -> B 
2: C -> A 
3: B -> C 
3: B -> A 
4: C -> A 
2: C -> B 
3: A -> B 
3: A -> C 
4: B -> C 
3: A -> B 
4: C -> A 
4: C -> B 
5: A -> B 

我試圖追查問題，但遞歸使追蹤這種類型的事情相當困難（至少對我而言）。

任何幫助或解釋將不勝感激！謝謝:)

Answer 1

您按值傳遞count，所以遞歸調用moveTower不會修改它的本地副本。按引用傳遞，而不是：

void moveTower(int n, char start, char finish, char temp, int & count) 
                  ^

這可能是稍微整潔遞增櫃檯裏面moveSingleDisk，而不是每次調用之前，所以你可以確保你不會錯過任何來電。在那種情況下，你也需要通過引用來傳遞。

Answer 2

使用遞歸數據/算法，功能性方法可以簡化代碼：從遞歸函數中返回計數，「聚合」嵌套級別。但是這樣你將失去「步」數的顯示。

int moveTower(int n, char start, char finish, char temp); 
int moveSingleDisk(char moveFrom, char moveTo); 
void calcHanoi(int n); 

int main (int argc, const char * argv[]) 
{ 
    calcHanoi(5); 
    return 0; 
} 

void calcHanoi(int n) 
{ 
    int count = moveTower(n, 'A', 'B', 'C'); 
} 

int moveTower(int n, char start, char finish, char temp) 
{ 
    if (n == 1) 
     return moveSingleDisk(start, finish); 
    return 
     moveTower(n-1, start, temp, finish) + 
     moveSingleDisk(start, finish) + 
     moveTower(n-1, temp, finish, start); 
} 

int moveSingleDisk(char moveFrom, char moveTo) 
{ 
    cout << moveFrom << " -> " << moveTo << endl; 
    return 1; 
} 

Answer 3

，如果你只需要算moveSingleDisk電話，才使在moveSingleDisk

static int count = 0; 
count++; 

看看這個例子，你並不需要通過計數器參數

#include <iostream> 

using namespace std; 

int f(){ 
    static int i = 0; 
    cout << i++; 
    return i < 5 ? f() : 5; 
} 

int main(){ 
    f(); 
    return 0; 
}