Iterative Funktionen in rekursive Funktionen umbauen

Gibt es Verfahrenswege mit deren Hilfe man möglichst leicht eine iterative Funktion in eine rekursive Funktion umwandeln kann?

Wenn man z.B. eine iterative Funktion gegeben hat und diese in eine rekursive Funktion umbauen soll, aber den Wald vor lauter Bäumen nicht sieht, gibt es dann irgendwelche Regeln, Tipps, Schritt für Schritt Anweisungen usw. so daß man möglichst schnell einen Einfall hat, wie die Rekursive Funktion lauten könnte und man nicht ewig nachdenken muß und trotzdem auf keine Lösung kommt oder zu lange dafür braucht?

cooky451

Ist das irgendwie eine fixe Idee von dir? Warum sollte man denn von iterativ auf rekursiv wollen, der Weg macht nur andersrum Sinn.

Ansonsten: Schleifen sind immer der Anhaltspunkt. Die Änderungen die in der Schleife gemacht werden (Laufvariable erhöhen etc.) musst du jetzt über Funktionsparameter ausdrücken. Gleichzeitig musst du die Abbruchsbedingung in ein nicht rekursives return überführen. Das wars eigentlich, warum auch immer man das machen wollen würde.

cooky451 schrieb:

Ist das irgendwie eine fixe Idee von dir? Warum sollte man denn von iterativ auf rekursiv wollen, der Weg macht nur andersrum Sinn.

Ne, wenn du einen Alogithmus als iterative Funktion in einer imperativen Sprache vorliegen hast, und diesen in eine funktionale Sprache überführen willst, dann brauchst du dazu rekursive Funktionen.

cooky451

Hm.. na gut. Poste doch mal ein paar Beispiele falls du welche hast, wenn es jemand löst und erklärt ist das eigentlich immer recht lehrreich.

Also ich habe jetzt leider keine konkreten Beispiele.
Ich wollte nur wissen, ob es dafür einen allgemeinen Vorgehensweg gibt, den man immer anwenden kann.

Wie löst man zwei ineinander verschachtelte Schleifen rekursiv?

Z.B. wenn man so etwas hat?

int func(const int n){
  Anweisungen..
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
       Anweisungen...
    }
  }
  Anweisungen..
}

Da mit n nicht gerechnet werden kann, dachte ich mir, daß ich die Zählvariable
als Parameter mitnehme, allerdings würde das bedeuten, daß man desto mehr Parameter braucht, je mehr for Schleifen man rekursiv abbilden will.
Ist das richtig?

Die Funktionsdeklaration der rekursiven Funktion könnte also z.B. so aussehen:

int func2(const int n; int i; int j)

Man muss zwischen endrekursiven und nicht endrekursiven Iterationen Unterscheiden.

Endrekursiv: Die letzte Anweisung in einer Funktion ist der rekursive Aufruf. Die Bedingung zur Rekursion wird bei der iterativen Implementierung in eine Schleife gepackt.

Nicht endrekursiv: Nach dem rekursiven Aufruf passiert noch etwas, z. B. Wertzuweisung einer Variable. Nicht endrekursive Funktionen kann man hauptsächlich über Stacks in iterative Funktionen überführen.

Du suchst nun den umgekehrten Weg, aber meine Erklärungen müssten dafür auch hilfreich sein.

L. G.
Steffo

cooky451

Ratschläge gesucht schrieb:

allerdings würde das bedeuten, daß man desto mehr Parameter braucht, je mehr for Schleifen man rekursiv abbilden will.
Ist das richtig?

Ja. Also na ja, man könnte das eventuell auch mit zwei Funktionen lösen:

int func2_rec(const int n, int j) // Brauchst du n noch für etwas anderes? Sonst würde j reichen.

int func_rec(const int n, int i) // Brauchst du n noch für etwas anderes? Sonst würde i reichen.

Ich bin mir nicht sicher, aber ich denke, das würde ungefähr so aussehen:

int func2_rec(const int n, int j) {
   if (j < n) {
      //Anweisung
      func_rec2(n, ++j);
   }
}

int func_rec(const int n, int i) {
   if (i == 0) { //Einmalige Ausführung beim ersten Aufruf
       //Anweisung
   }
   if (i < n) {
      func_rec2(n, 0);
      func_rec(n, ++i);
   }
   if (i == 0) { //Einmalige Ausführung beim ersten Aufruf
       //Anweisung
   }
}