Comment arrêter la fonction récursive?

Question

Je travaille sur une fonction récursive et c'est la première fois que je n'arrive pas à comprendre comment arrêter le calcul.

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]) 

Il convient de calculer la meilleure distribution en 4 trous. Donc, dans chaque trou, il y a une somme maximale de valeurs. La liste val dit ceci: pour val [0] trou, je peux y mettre le 1er article dont le prix val[0][0] etc.

Le problème est que les valeurs o a après quelques itérations nombres négatifs qui est interdite.

Par exemple rec(1,0,0,50,0) doit être 50 car aucune option n'est disponible sauf ceci.

EDIT:

En fait, ce que je veux est de dire la fonction qu'il ne devrait pas traiter des arguments avec la valeur 0.

Alors rec(2,0,1,0,1) devrait revenir max(rec(1,0,0,0,1)+val[2][1], rec(1,0,1,0,0) + val[2][3])

Answer 1

Si vous voulez qu'il ne traite pas la récursivité a avec l'argument 0, ajoutez simplement un cas de base pour cela. Ce que j'ai fait a été fait en sorte que la valeur retournée annule dans le niveau de révision ci-dessus 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

Vous devez vous assurer qu'il atteint un point où n == 1 ... Dans votre cas ici, si n est un flotteur, cela pourrait ne jamais arriver, vous devrez tester pour abs (n - 1) < petit epsilon ...

Alternativement, et cela peut être la meilleure solution dans ce cas, vous pouvez remplacer le test n == 1 par n < 1; comme ceci:

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