Allgemeine Möglichkeit, eine Schleife (while / for) in eine Rekursion oder von einer Rekursion in eine Schleife umzuwandeln?

Dieses Problem konzentriert sich hauptsächlich auf den Algorithmus, vielleicht etwas Abstraktes und Akademischeres.

Das Beispiel bietet einen Gedanken, ich möchte einen generischen Weg, also wird das Beispiel nur verwendet, um uns klarer über Ihre Gedanken zu informieren.

Im Allgemeinen kann eine Schleife in eine rekursive umgewandelt werden.

z.B:

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

Und das damit verbundene rekursive ist:

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

Und schließlich, um dies zu vereinfachen, wird ein Schwanzrekursiv benötigt:

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

Die meisten Fälle sind jedoch nicht so einfach zu beantworten und zu analysieren. Was ich wissen möchte ist:

1) Können wir einen "allgemeinen Weg" finden, um eine Schleife (für / während ...) in eine rekursive zu konvertieren? Und auf was sollten wir bei der Bekehrung achten? Es wäre besser, detaillierte Informationen mit einigen Beispielen und Ihren Persudo-Theorien sowie dem Konvertierungsprozess zu schreiben.

2) "Rekursiv" hat zwei Formen: rekursiv und rekursiv. Also was ist besser zu konvertieren? Welche "Regel" sollen wir meistern?

3) Manchmal müssen wir die "Geschichte" von rekursiv halten, dies kann leicht in einer Schleifenanweisung gemacht werden:

z.B:

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);
   }
}

Das folgende Ergebnis ist:

Das Ergebnis von 1 ist 1.

Das Ergebnis von 1 + 2 ist 3.

Das Ergebnis von 1 + 2 + 3 ist 6 …………

Ich denke jedoch, dass es schwierig ist, den Verlauf rekursiv zu halten, da sich ein rekursiv basierter Algorithmus darauf konzentriert, das letzte Ergebnis zu erhalten und einen Rückruf durchzuführen. All dies geschieht also über den Stapel, der von der Programmiersprache verwaltet wird, die den Speicher automatisch in Form eines Stapels zuweist. Und wie können wir "manuell" jeden der "Stapelwerte" herausnehmen und mehrere Werte durch einen rekursiven Algorithmus zurückgeben?

Und was ist mit "von einem rekursiven Algorithmus zu einer Schleife"? Können sie ineinander umgewandelt werden (ich denke, das sollte theoretisch gemacht werden, aber ich möchte genauere Dinge, um meine Gedanken zu beweisen) .

Eigentlich solltest du zuerst die Funktion aufschlüsseln:

Eine Schleife besteht aus mehreren Teilen:

1. den Header und die Verarbeitung vor der Schleife. Kann einige neue Variablen deklarieren

2. die Bedingung, wann die Schleife zu stoppen ist.

3. der eigentliche Schleifenkörper. Es werden einige der Variablen des Headers und / oder die übergebenen Parameter geändert.

4. der Schweif; Was passiert nach der Schleife und dem Rückgabeergebnis?

Oder um es aufzuschreiben:

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

Die Verwendung dieser Blöcke für einen rekursiven Aufruf ist ziemlich einfach:

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à; eine rekursive Endversion einer beliebigen Schleife. breaks und continues im Schleifenkörper müssen weiterhin bei Bedarf ersetzt return tailund zurückgegeben foo_recursion(params, modified_header_vars)werden, aber das ist einfach genug.

Den anderen Weg zu gehen ist komplizierter; Zum Teil, weil es mehrere rekursive Aufrufe geben kann. Dies bedeutet, dass es jedes Mal, wenn wir einen Stapelrahmen einfügen, mehrere Stellen geben kann, an denen wir fortfahren müssen. Es kann auch Variablen geben, die über den rekursiven Aufruf und die ursprünglichen Parameter des Aufrufs hinweg gespeichert werden müssen.

Wir können einen Schalter verwenden, um das zu umgehen:

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;
        }
    }
}

Nach der Antwort von @ratchet freak habe ich dieses Beispiel erstellt, wie die Fibonacci-Funktion in Java in eine while-Schleife umgeschrieben werden kann. Beachten Sie, dass es eine viel einfachere (und effizientere) Möglichkeit gibt, die Fibonacci mit einer while-Schleife neu zu schreiben.

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;
}