Modifier une fonction récursive qui a une boucle for dans une fonction itérative?

Question

J'ai donc cette fonction que j'essaye de convertir d'un algorithme récursif à un algorithme itératif. Je ne suis même pas sûr si j'ai les bons sous-problèmes, mais cela semble déterminer ce dont j'ai besoin de la bonne manière, mais la récursivité ne peut pas être utilisée, vous devez utiliser la programmation dynamique, donc je dois changer en itératif. down programmation dynamique.

La fonction récursive de base ressemble à ceci:

Recursion(i,j) { 
    if(i > j) { 
     return 0; 
    } 
    else { 
     // This finds the maximum value for all possible 
     // subproblems and returns that for this problem 
     for(int x = i; x < j; x++) { 
      if(some subsection i to x plus recursion(x+1,j) is > current max) { 
       max = some subsection i to x plus recursion(x+1,j) 
      } 
     } 
    } 
} 

Telle est l'idée générale, mais étant donné que récurrences n'ont généralement pas pour les boucles en eux, je ne suis pas sûr de savoir comment exactement je convertir en itérative . Quelqu'un a-t-il une idée?

Answer 1

bien moins qu'il y ait un problème avec la logique non inclus encore, il devrait être bien

pour & tout sont ok dans récursion

assurez-vous de retour dans tous les cas qui peuvent se produire

Answer 2

Vous avez une fonction récursive qui peut se résumer comme ceci:

recursive(i, j): 
    if stopping condition: 
     return value 

    loop: 
     if test current value involving recursive call passes: 
      set value based on recursive call 

    return value # this appears to be missing from your example 

(je vais être assez lâche avec le code pseudo il re, pour souligner la structure du code plutôt que la mise en œuvre spécifique)

Et vous voulez l'aplatir à une approche purement itérative. Tout d'abord, il serait bon de décrire exactement ce que cela implique dans le cas général, car vous semblez être intéressé par cela. Ensuite, nous pouvons passer à l'aplatissement du pseudo-code ci-dessus.

Maintenant aplatir une fonction récursive primitive est assez simple. Lorsque vous le code donné qui ressemble à:

simple(i): 
    if i has reached the limit: # stopping condition 
     return value 

    # body of method here 

    return simple(i + 1) # recursive call 

Vous pouvez voir rapidement que les appels récursifs continueront jusqu'à ce que i atteint la limite prédéfinie. Lorsque cela se produit, le value sera retourné. La forme itérative de ceci est:

simple_iterative(start): 
    for (i = start; i < limit; i++): 
     # body here 

    return value 

Cela fonctionne parce que les appels récursifs forment l'arbre d'appel suivant:

simple(1) 
    -> simple(2) 
    -> simple(3) 
     ... 
     -> simple(N): 
      return value 

Je décrirais cet arbre d'appel comme un morceau de ficelle. Il a un début, un milieu et une fin. Les différents appels se produisent à différents points de la chaîne. Une chaîne d'appels de ce type ressemble beaucoup à une boucle for - tout le travail effectué par la fonction est passé à l'invocation suivante et le résultat final de la récursivité est simplement renvoyé. La version for loop prend juste les valeurs qui seraient passées dans les différents appels et exécute le code du corps sur eux.

Simple jusqu'ici!

Maintenant, votre méthode est plus complexe de deux façons:

• Il y a plusieurs états distincts qui font des appels récursifs
• Ces états sont eux-mêmes dans une boucle

donc votre arbre d'appel est quelque chose comme:

recursive(i, j): 
    for (v in 1, 2, ... N): 
    -> first_recursive_call(i + v, j): 
     -> ... inner calls ... 
    -> potential second recursive call(i + v, j): 
     -> ... inner calls ... 

Comme vous pouvez le voir s pas du tout comme une chaîne. Au lieu de cela, c'est vraiment comme un arbre (ou un buisson) en ce que chaque appel entraîne deux autres appels. À ce stade, il est vraiment très difficile de revenir à une fonction entièrement itérative.

Ceci est dû à la relation fondamentale entre les boucles et la récursivité. Toute boucle peut être réaffirmée comme un appel récursif. Cependant, tous les appels récursifs ne peuvent pas être transformés en boucles.

La classe d'appels récursifs qui peuvent être transformés en boucles est appelée primitive récursion. Votre fonction semble initialement avoir transcendé cela. Si tel est le cas, vous ne pourrez pas le transformer en une fonction purement itérative (à moins d'implémenter une pile d'appels et similaire dans votre fonction).

Cette vidéo explique la différence entre récursion primitive et types fondamentalement récursifs qui suivent:

https://www.youtube.com/watch?v=i7sm9dzFtEI

Je voudrais ajouter que votre condition et la valeur que vous attribuez à max semblent être les mêmes. Si tel est le cas, vous pouvez supprimer l'un des appels récursifs, ce qui permet à votre fonction de devenir une instance de récursivité primitive enveloppée dans une boucle. Si vous l'avez fait, vous pourrez peut-être l'aplatir.