如何停止遞歸函數？

Question

我正在研究遞歸函數，這是我第一次不知道如何停止計算。

val = [[12, 11, 3, 38], [13, 18, 49, 41], [12, 17, 33, 45], [45, 36, 32, 33]] 

def rec(n, o1, o2, o3, o4): 
    if n==1: # BECAUSE IN CASE THAT N==1, THERE IS JUST ONE ARGUMENT WITH VALUE 1, OTHER ARGUMENTS SHOULD HAVE VALUE 0 
     if o1==1: 
      return val[0][0] 
     elif o2==1: 
      return val[0][1] 
     elif o3==1: 
      return val[0][2] 
     else: 
      return val[0][3] 

    return max(rec(n - 1, o1 - 1, o2, o3, o4) + val[n][0], 
       rec(n - 1, o1, o2 - 1, o3, o4) + val[n][1], 
       rec(n - 1, o1, o2, o3 - 1, o4) + val[n][2], 
       rec(n - 1, o1, o2, o3, o4 - 1) + val[n][3]) 

它應該計算最好的分佈到4個孔。所以在每個洞裏都有最大的價值總和。該val名單告訴本：爲val [0]洞，我可以把有第一個項目與價格val[0][0]等

的問題是，o值後，有幾個迭代負數這是被禁止的。

例如rec(1,0,0,50,0)應該是50，因爲除此之外沒有任何選項可用。

編輯：

其實，我要的是告訴它不應該與價值的過程參數的函數0

所以rec(2,0,1,0,1)應該返回max(rec(1,0,0,0,1)+val[2][1], rec(1,0,1,0,0) + val[2][3])

Answer 1

如果你不想使用參數0來處理遞歸a，只需要爲它添加一個基本情況。我所做的是確保返回的價值將取消在上述修訂級別爲0

def rec(n, o1, o2, o3, o4): 
    if o1 <= 0: 
     return -val[n+1 if n<len(val)-1 else n][0] 
     # checks for out of bounds with inline if, 
     # return negative value so compared value in upper level will be 0, 
     # and it will never be chosen 
    if o2 <= 0: 
     return -val[n+1 if n<len(val)-1 else n][1] 
    if o3 <= 0: 
     return -val[n+1 if n<len(val)-1 else n][2] 
    if o4 <= 0: 
     return -val[n+1 if n<len(val)-1 else n][3] 
    if n<=1: # like Reblochon said, n might be float if you are unlucky 
     if o1==1: 
      return val[0][0] 
     elif o2==1: 
      return val[0][1] 
     elif o3==1: 
      return val[0][2] 
     else: 
      return val[0][3] 

    return max(rec(n - 1, o1 - 1, o2, o3, o4) + val[n][0], \ # you will need these for line continuations 
      rec(n - 1, o1, o2 - 1, o3, o4) + val[n][1], \ 
      rec(n - 1, o1, o2, o3 - 1, o4) + val[n][2], \ 
      rec(n - 1, o1, o2, o3, o4 - 1) + val[n][3]) 

Answer 2

你必須確保它達到當n == 1 ...在你的情況下，如果n是一個浮點數，可能永遠不會發生，你將需要測試abs（n-1）<小epsilon ...

或者，那可能在這種情況下是最好的解決方案，您可以將n == 1測試更改爲n < 1;像這樣：

val = [[12, 11, 3, 38], [13, 18, 49, 41], [12, 17, 33, 45], [45, 36, 32, 33]] 

def rec(n, o1, o2, o3, o4): 
    if n < 1: 
     if o1 == 1: 
      return val[0][0] 
     elif o2 == 1: 
      return val[0][1] 
     elif o3 == 1: 
      return val[0][2] 
     else: 
      return val[0][3] 

    return max(rec(n - 1, o1 - 1, o2, o3, o4) + val[n][0], 
       rec(n - 1, o1, o2 - 1, o3, o4) + val[n][1], 
       rec(n - 1, o1, o2, o3 - 1, o4) + val[n][2], 
       rec(n - 1, o1, o2, o3, o4 - 1) + val[n][3]) 

rec(3, 2, 2, 2, 2) 

>>> 164