Remplacer la récursivité (avec des valeurs renvoyées) par une pile explicite

Question

Je me demandais simplement s'il était possible de remplacer la récursivité par une pile explicite lorsque vous avez besoin de la ou des valeurs de retour et de les comparer pour trouver la meilleure solution (dynamique la programmation)?

donc quelque chose comme (il ne fait rien, juste un exemple):

int resursiveFunction (int state) { 

    if (known[state]) return cache[state]; 
    if (state == MAX_STATE) return 0; 

    int max = 0; 

    for (int i = 0 ; i < 5; i++) { 
     int points = curPoints (state) + recursiveFunction (state+i); 
     if (points > max) max = points; 
    } 

    known[state] = true; 
    cache[state] = max; 
    return max; 

}

Answer 1

Oui. C'est possible.

Il vous suffit de pousser et d'ouvrir si nécessaire. La récursivité crée simplement une «pile implicite». Vous pouvez également dérouler les fonctions récursives de TCO. Vous pouvez trouver Stacks and Recursion Elimination (c'est pour un cours) utile. Il couvre l'élimination (récursive à gauche) ainsi que l'émulation (pile).