Manière générale de convertir une boucle (while / for) en récursivité ou d'une récursion en boucle?

Ce problème se concentre principalement sur l'algorithme, peut-être quelque chose d'abstrait et de plus académique.

L'exemple offre une pensée, je veux une manière générique, donc l'exemple n'est utilisé que pour nous éclairer plus clairement sur vos pensées.

D'une manière générale, une boucle peut être convertie en récursive.

par exemple:

for(int i=1;i<=100;++i){sum+=i;}

Et son récursif connexe est:

int GetTotal(int number)
{
   if (number==1) return 1;   //The end number
   return number+GetTotal(number-1); //The inner recursive
}

Et enfin pour simplifier cela, une queue récursive est nécessaire:

int GetTotal (int number, int sum)
{
    if(number==1) return sum;
    return GetTotal(number-1,sum+number);
}

Cependant, la plupart des cas ne sont pas si faciles à répondre et à analyser. Ce que je veux savoir c'est:

1) Pouvons-nous obtenir un «moyen commun général» pour convertir une boucle (pendant / pendant ……) en une récursive? Et à quels types de choses devons-nous faire attention lors de la conversion? Il serait préférable d'écrire des informations détaillées avec quelques exemples et vos théories de persudo ainsi que le processus de conversion.

2) "Récursif" a deux formes: Linéairement récursif et Tail-Récursif. Alors, quel est le meilleur à convertir? Quelle "règle" devons-nous maîtriser?

3) Parfois, nous devons garder "l'historique" de la récursivité, cela se fait facilement dans une déclaration en boucle:

par exemple:

List<string> history = new List<string>();
int sum=0;
for (int i=1;i<=100;++i)
{
   if(i==1) history.Add(i.ToString()+"'s result is:1.");
   else
   {
     StringBuilder sub = new StringBuilder();

      for(int j=1;j<=i;++j)
      {
          if(j==i) sbu.Append(j.ToString());
          else
          {
            sub.Append(j.ToString()+"+");
          }
      }
    sum +=i;
    sbu.Append("'s result is:"+sum+Environment.NewLine);
   }
}

Le résultat ci-dessous est:

Le résultat 1 est 1.

Le résultat 1 + 2 est 3.

Le résultat 1 + 2 + 3 est 6 …………

Cependant, je pense qu'il est difficile de conserver l'historique dans une position récursive, car un algorithme basé sur la récursivité se concentre sur l'obtention du dernier résultat et sur un retour de rappel. Donc, tout cela se fait via la pile maintenue par le langage de programmation affectant automatiquement la mémoire sous forme de pile. Et comment retirer "manuellement" chacune des "valeurs de pile" et renvoyer plusieurs valeurs via un algorithme récursif?

Et qu'en est-il de "d'un algorithme récursif à une boucle"? Peuvent-ils être convertis les uns aux autres (je pense que cela devrait être fait théoriquement, mais je veux des choses plus précises pour prouver mes pensées) .

En fait, vous devez d'abord décomposer la fonction:

Une boucle se compose de quelques parties:

1. l'en-tête et le traitement avant la boucle. Peut déclarer de nouvelles variables

2. la condition, quand arrêter la boucle.

3. le corps de boucle réel. Il modifie certaines variables d'en-tête et / ou les paramètres transmis.

4. la queue; ce qui se passe après la boucle et retourne le résultat.

Ou pour l'écrire:

foo_iterative(params){
    header
    while(condition){
        loop_body
    }
    return tail
}

L'utilisation de ces blocs pour effectuer un appel récursif est assez simple:

foo_recursive(params){
    header
    return foo_recursion(params, header_vars)
}

foo_recursion(params, header_vars){
    if(!condition){
        return tail
    }

    loop_body
    return foo_recursion(params, modified_header_vars)
}

Et voilà; une version récursive de queue de n'importe quelle boucle. breaks et continues dans le corps de la boucle devront toujours être remplacés par return tailet retournés foo_recursion(params, modified_header_vars)selon les besoins, mais c'est assez simple.

Aller dans l'autre sens est plus compliqué; en partie parce qu'il peut y avoir plusieurs appels récursifs. Cela signifie que chaque fois que nous ouvrons un cadre de pile, il peut y avoir plusieurs endroits où nous devons continuer. Il peut également y avoir des variables que nous devons enregistrer à travers l'appel récursif et les paramètres d'origine de l'appel.

Nous pouvons utiliser un commutateur pour contourner cela:

bar_recurse(params){
    if(baseCase){
        finalize
        return
    }
    body1
    bar_recurse(mod_params)
    body2
    bar_recurse(mod_params)
    body3
}


bar_iterative(params){
    stack.push({init, params})

    while(!stack.empty){
        stackFrame = stack.pop()

        switch(stackFrame.resumPoint){
        case init:
            if(baseCase){
                finalize
                break;
            }
            body1
            stack.push({resum1, params, variables})
            stack.push({init, modified_params})
            break;
        case resum1:
            body2
            stack.push({resum2, params, variables})
            stack.push({init, modified_params})
            break;
        case resum2:
            body3
            break;
        }
    }
}

Suite à la réponse de @ratchet freak, j'ai créé cet exemple de la façon dont la fonction Fibonacci peut être réécrite dans une boucle while en Java. Notez qu'il existe un moyen beaucoup plus simple (et efficace) de réécrire le Fibonacci avec une boucle while.

class CallContext { //this class is similar to the stack frame

    Object[] args;

    List<Object> vars = new LinkedList<>();

    int resumePoint = 0;

    public CallContext(Object[] args) {
        this.args = args;
    }

}


static int fibonacci(int fibNumber) {
    Deque<CallContext> callStack = new LinkedList<>();
    callStack.add(new CallContext(new Object[]{fibNumber}));
    Object lastReturn = null; //value of last object returned (when stack frame was dropped)
    while (!callStack.isEmpty()) {
        CallContext callContext = callStack.peekLast();
        Object[] args = callContext.args;
        //actual logic starts here
        int arg = (int) args[0];
        if (arg == 0 || arg == 1) {
            lastReturn = arg;
            callStack.removeLast();
        } else {
            switch (callContext.resumePoint) {
                case 0: //calculate fib(n-1)
                    callStack.add(new CallContext(new Object[]{arg - 1}));
                    callContext.resumePoint++;
                    break;
                case 1: //calculate fib(n-2)
                    callContext.vars.add(lastReturn); //fib1
                    callStack.add(new CallContext(new Object[]{arg - 2}));
                    callContext.resumePoint++;
                    break;
                case 2: // fib(n-1) + fib(n-2)
                    callContext.vars.add(lastReturn); //fib2
                    lastReturn = (int) callContext.vars.get(0) + (int) callContext.vars.get(1);
                    callStack.removeLast();
                    break;
            }
        }
    }
    return (int) lastReturn;
}