Wie schreibt man rekursive Funktionen beim Programmieren?

Ich habe ein Problem. Wenn ich eine rekursive Funktion/Methode sehe, dann weiß ich was diese macht, aber andersrum, wenn ich eine rekursive Methode schreiben will, dann bekomme ich es nur im seltensten Fall hin.

Hat jemand Tipps. wie man beim schreiben von rekursiven Funktionen vorgehen kann?

Answer 1

[tavkomann]

Hier wird die grundsätzliche Vorgehensweise verständlich dargestellt. Kurz und knapp:

1. Schreibe einen Prototyp für die rekursive Funktion
2. Mache dir klar und beschreibe selbst ganz genau, was diese Funktion tun soll
3. Ermittele den Basisfall (d.h. die Parameter, für die die Funktion nicht nochmals aufgerufen wird, weil dieser Fall genau definiert und unabhängig von vorherigen Lösungen ist [z.B. bei Fibonacci f(0) und f(1)])
4. Ermittele, welches kleinere Problem / welche kleineren Probleme gelöst werden müssen
5. Gehe davon aus (noch nicht überprüfen!), dass dein rekursiver Aufruf korrekt ist
6. Nutze die Lösungen der kleineren Probleme, um das größere Problem zu lösen. Wenn das Ergebnis inkorrekt ist, sind auch die Lösungen der kleineren Probleme falsch, sodass du wieder ein paar Schritte zurückgehen musst.

Answer 2

[tooneu]

Zunächst einmal: Was ist eine rekursive Funktion?

Antwort: Eine Funktion, die sich selbst wieder aufruft.

Wozu benötigt man das?

Wenn das Ergebnis der Funktion identisch zu seinem Ausgangspunkt ist. Übrigens lässt sich jede Rekursion durch eine Schleife ersetzen, aber nicht umgekehrt.

Beispiel für eine Rekursionsaufgabe: Durchsuche das ganze Dateisystem und träge sämtliche Dateien (aber nicht die Ordner) in eine Datenbank ein.

Lösungsansatz: Eine Funktion, die 1) einen Ordner und 2) eine Datenbank erhält. Sie trägt jede Datei in die Datenbank ein, ruft sich dann selbst auf jeden Unterordner auf.

Comments

[thomaszZz, Software Engineer bei gutefrage]

Umgekehrt: Jede iterative Lösung lässt sich auch rekursiv darstellen, aber nicht jede rekursive Lösung iterativ.

Grundsätzlich gilt, dass jedes Problem, welches sich über "Tail Recursive" (Endrekursive, d.h. die Rekursion ist die letzte Anweisung im Aufruf) Algorithmen lösen lässt, auch direkt iterativ geschrieben werden kann.

Answer 3

[agent888]

Zuerst einmal sei gesagt, dass Rekursion nur selten benutzt werden kann. Nicht jede Funktion benötigt Rekursion. Beispiel für Rekursion wären aber z.B. Fibonaccizahlen, Fakultät und das Erstellen von Ordnerstrukturen. Wenn du es verwendest solltest du darauf achten, dass der rekursive Aufruf immer an eine Bedingung gebunden ist, sonst wird es unendlich weiterlaufen. Sofern du das tust, sollte es kein Problem geben.

Answer 4

[PhotonX]

Versuche dir aus den Beispielen, die du nachvollziehst, ein allgemeingültiges "Skelett" zu abstrahieren, also eine Struktur, die in jeder rekursiven Funktion auftaucht.