如何使這個方法非遞歸？

Question

嘿。這個例子非常具體，但我認爲它可以應用於廣泛的功能。 它來自一些在線編程比賽。

有一個簡單的獲勝條件的遊戲。平局是不可能的。遊戲不能永遠持續下去，因爲每一步都會讓你更接近終止條件。在給定狀態的情況下，該功能應該確定現在要移動的玩家是否具有獲勝策略。 在該示例中，狀態是一個整數。玩家選擇一個非零數字並從數字中減去：新的狀態是新的整數。勝利者是達到零的玩家。

我這個編碼：

from Memoize import Memoize 

@Memoize 
def Game(x): 
    if x == 0: return True 
    for digit in str(x): 
     if digit != '0' and not Game(x-int(digit)): 
      return True 
    return False 

我想很明顯它是如何工作的。我也意識到，對於這個特定的遊戲可能有一個更聰明的解決方案，但我的問題是一般的。然而，即使對於相對較小的輸入，這也會使python變得瘋狂。有沒有什麼辦法讓這段代碼在循環中工作？

感謝

這就是我的意思翻譯成一個循環：

def fac(x): 
    if x <= 1: return x 
    else: return x*fac(x-1) 

def fac_loop(x): 
    result = 1 
    for i in xrange(1,x+1): 
     result *= i 
    return result 

## dont try: fac(10000) 
print fac_loop(10000) % 100 ## works 

Answer 1

一般來說，只有在遞歸函數爲primitive-recursive時，纔有可能將遞歸函數轉換爲循環;這基本上意味着他們只在體內自稱一次。你的函數自動調用多次。這樣的功能確實需要一個堆棧。可以使堆棧顯式化，例如，與列表。使用一個明確的堆棧你的算法的一個再形成是

def Game(x): 
    # x, str(x), position 
    stack = [(x,str(x),0)] 
    # return value 
    res = None 

    while stack: 
     if res is not None: 
      # we have a return value 
      if not res: 
       stack.pop() 
       res = True 
       continue 
      # res is True, continue to search 
      res = None 
     x, s, pos = stack.pop() 
     if x == 0: 
      res = True 
      continue 
     if pos == len(s): 
      # end of loop, return False 
      res = False 
      continue 
     stack.append((x,s,pos+1)) 
     digit = s[pos] 
     if digit == '0': 
      continue 
     x -= int(digit) 
     # recurse, starting with position 0 
     stack.append((x,str(x),0)) 

    return res 

基本上，你需要將每一種局部變量堆棧幀的元素;這裏的局部變量是x，str（x）和循環的迭代計數器。做返回值有點棘手 - 如果函數剛剛返回，我選擇將res設置爲not-None。

Answer 2

通過「發瘋」我想你的意思是：

>>> Game(10000) 
# stuff skipped 
RuntimeError: maximum recursion depth exceeded in cmp 

你可以在底部啓動相反 - 一個粗略的變化將是：

# after defining Game() 
for i in range(10000): 
    Game(i) 

# Now this will work: 
print Game(10000) 

這是因爲，如果你從一個很高的數字開始，在到達底部（0）之前你需要經過很長的一段時間，所以你的memoization裝飾器沒有幫助它。

通過從底部開始，確保每次遞歸調用都立即觸碰結果字典。你可能會使用額外的空間，但是你不會遠慮。

您可以使用循環和堆棧將任何遞歸函數轉換爲迭代函數 - 本質上是手動運行調用堆棧。例如，參見this question或this quesstion進行一些討論。這裏可能有一個更優雅的基於循環的解決方案，但它不會跳到我身上。

Answer 3

那麼，遞歸主要是關於能夠執行一些代碼而不會丟失先前的上下文和順序。特別是，函數框架在遞歸期間放入並保存到調用堆棧中，因此由於堆棧大小有限而給予遞歸深度約束。您可以通過在堆內存上創建狀態堆棧，手動管理/保存每次遞歸調用所需的信息來「增加」遞歸深度。通常，可用堆內存的數量大於堆棧的數量。認爲：良好的快速排序實現通過創建具有不斷變化的狀態變量的外部循環（在QS示例中爲下部/上部數組邊界和樞軸）來消除向較大側的遞歸。

當我打字時，Martin v。Löwis發表了關於將遞歸函數轉換爲循環的良好答案。

Answer 4

您可以修改您的遞歸版本有點：

def Game(x): 
    if x == 0: return True 
    s = set(digit for digit in str(x) if digit != '0') 
    return any(not Game(x-int(digit)) for digit in s) 

這樣，你不檢查位數多次。例如，如果你在做111，你不必三次看110。

我不知道這是否算作你提出的原始算法的迭代版本，但這裏是一個memoized迭代版本：

import Queue 
def Game2(x): 
    memo = {} 
    memo[0] = True 
    calc_dep = {} 
    must_calc = Queue.Queue() 
    must_calc.put(x) 
    while not must_calc.empty(): 
     n = must_calc.get() 
     if n and n not in calc_dep: 
      s = set(int(c) for c in str(n) if c != '0') 
      elems = [n - digit for digit in s] 
      calc_dep[n] = elems 
      for new_elem in elems: 
       if new_elem not in calc_dep: 
        must_calc.put(new_elem) 
    for k in sorted(calc_dep.keys()): 
     v = calc_dep[k] 
     #print k, v 
     memo[k] = any(not memo[i] for i in v) 
    return memo[x] 

它首先計算集X號，輸入， 依賴於取決於。然後它會計算這些數字，從底部開始並趨向x。

代碼是如此之快，因爲calc_dep的測試。它避免了計算多個依賴關係。因此，它可以在400毫秒內完成遊戲（10000），而原始遊戲則需要 - 我不知道多久。很長時間。

以下是性能測試：

Elapsed: 1000 0:00:00.029000 
Elapsed: 2000 0:00:00.044000 
Elapsed: 4000 0:00:00.086000 
Elapsed: 8000 0:00:00.197000 
Elapsed: 16000 0:00:00.461000 
Elapsed: 32000 0:00:00.969000 
Elapsed: 64000 0:00:01.774000 
Elapsed: 128000 0:00:03.708000 
Elapsed: 256000 0:00:07.951000 
Elapsed: 512000 0:00:19.148000 
Elapsed: 1024000 0:00:34.960000 
Elapsed: 2048000 0:01:17.960000 
Elapsed: 4096000 0:02:55.013000 

它相當活潑。