計數遞歸調用 - 河內塔

Question

我正在處理一個問題，處理河內問題的塔上的變化，其中一個只能移動到相鄰的樁，我們只限於3樁問題。我已經得到了代碼來打印光盤數量所需的動作，但我無法弄清楚如何打印遞歸調用的數量。

def adjacent_hanoi(num_discs, start_peg, end_peg): 
""" 
Given the number of discs in Adjacent-Peg Tower of Hanoi: 
1. Prints each move necessary to solve the puzzle (minimum number of moves) 
2. Returns the total number of moves required 

For this problem, discs should always start on the first peg and 
end on the last peg. 

num_discs: an integer number of discs 
start_peg: starting peg 
end_peg: ending peg 
returns: an integer number of moves 
""" 

if num_discs > 0: 
    adjacent_hanoi(num_discs-1, start_peg, end_peg) 
    print "Move disc", num_discs, "from peg", start_peg, "to peg", 2 
    adjacent_hanoi(num_discs-1, end_peg, start_peg) 
    print "Move disc", num_discs, "from peg", 2 , "to peg", end_peg 
    adjacent_hanoi(num_discs-1, start_peg, end_peg) 

Answer 1

添加一個計數器這是一個全局變量。在你的函數的開頭由1

recursionCounter = 0 

def functionToTrack: 
    recursionCounter += 1 
    #the rest of your code... 

增加，如果你只是想跟蹤遞歸店它的水平，並在每次從函數外部調用時間重置recursionCounter爲0。

functionToTrack() 
firstCallRecursion = recursionCounter 
recursionCounter = 0 
functionToTrack() 
secondCallRecursion = recursionCounter 
recursionCounter = 0 

Answer 2

您可以添加一個新參數，可以稱之爲count。

def adjacent_hanoi(num_discs, start_peg, end_peg, count): 

您可以遞增它的每次遞歸調用。

另一種方法是添加一個全局變量並只增加它。如果沒什麼特別的話，我會這樣做。

Answer 3

我會建議增加一個額外的參數，以你的函數作爲增量計數器：

def adjacent_hanoi(num_discs, start_peg, end_peg, count=0): 
    #do something with num_discs, start_peg, and end_peg 
    count += 1 
    print count 
    return adjacent_hanoi(num_discs, start_peg, end_peg, count) 

Answer 4

使用裝飾！

class Counter(object): 
    def __init__(self, func): 
     self.func = func 
     self.count = 0 
    def __call__(self, *args): 
     self.count += 1 
     return self.func(*args) 
@Counter 
def your_function(): 
    return "Hello" 

for i in range(10): 
    print your_function() 

print your_function.count #=> 10 

Answer 5

這是一個數學序列。

只是做一個輔助方法

hanoi_recurse(num_discs, start, end) 

它做同樣的事情，第一種方法

現在你的代碼看起來像

def adjacent_hanoi(num_discs, start_peg, end_peg): 
    adjacent_hanoi_recurse(num_discs, start_peg, end_peg) 
    print (3 ** num_discs) - 1