Wie kann man die richtige Idee für ein Programm rekursiv lösen?
Mir fällt es aus irgendwelchen Gründen extrem schwer rekusiv zu denken und Programme für die Uni rekursiv zu schreiben. Mit schleifen usw. hab ich schnell eine Idee und auch wenn ich mir dann die rekursiven Musterlösungen anschaue frage ich mich oft, wie ich da nicht drauf kommen könnte. Könnt ihr dieses Problem nachvollziehen und habt ihr Tipps?
5 Antworten
Rekursive Lösungen sind nun einmal einfach komplexer als iterative Lösungen (also Schleifen), auch wenn die rekursiven Lösungen meist kürzer sind.
Rekursiv zu denken ist natürlich schwieriger. Von selbst auf die Lösung zu kommen erfordert auch eindeutig Übung. Das gilt für Programmieren ja sowieso ganz allgemein. Etwas auf dem Blatt Papier zu verstehen ist das eine, es später anzuwenden etwas ganz anderes.
Die Wahrheit ist aber auch: Rekursion muss man kennen und können, bei der Softwareentwicklung kommt sie aber nicht gerade häufig zum Einsatz. Natürlich hängt das komplett vom Einsatzbereich etc ab, aber dennoch kann ich an einer Hand abzählen, wie oft ich Rekursive Implementierungen im Job gesehen oder selbst vorgenommen habe. In meinem Fall kam es auch nur bei Strukturen vor, wo ein Objekt beliebig viele Objekte der gleichen Klasse enthalten konnte. Wenn man nun sowas wie Volumenberechnung o.ä. machen muss oder herausfinden muss, ob Artikel x in dem Objekt oder irgendeinem Unterobjekt ist, muss man rekursiv arbeiten. Das ist dann aber wiederum ziemlich selbsterklärend.
Rekursion ist manchmal eben nicht so intuitiv wie ein anderer Ansatz - das hängt aber teils sehr davon ab, worum es geht. Bei rekursiven Strukturen sind Rekursionen oft nicht nur kürzer, sondern auch einfacher - auch dort, wo man sonst selbst einen Stack pflegen müßte.
Wie immer: üben hilft. Wenn man rekursiv denkt, sind dann iterative Lösungen wieder umständlicher. Letztlich übst du dabei etwas, das in der Softwareentwicklung wichtig ist, nämlich das Zerlegen großer in kleine Aufgabenstellungen.
Literaturtipp: https://mitpress.mit.edu/9780262560993/the-little-schemer/
Das ist ganz normal und gilt für alles.
Es ist immer schwerer, eine Lösung selber zu finden, als eine fertige Lösung zu verstehen. Das macht die Softwareentwicklung ja auch so schwer - unter Anderem.
Und bei der Rekursion kommt noch dazu, dass gedanklich rekursive Verzweigungen im Kopf behalten musst. Wenn Du eine rekursive Struktur (z.B. eine Baum-Struktur) hast, ist das einfacher, weil man sich das besser vorstellen kann, aber nicht immer hat man eine leicht verständliche rekursive Struktur.
Und da es nicht so viele reale Beispiele für *vernünftige* Rekursion gibt, rate ich einfach mal, dass die rekursiven Aufgaben, die Ihr da vorgesetzt bekommt, eher weniger sinnvoll sind, was es natürlich nochmal schwerer macht. Also z.B. sowas wie Zählen mit Rekursion - geht, ist dann halt sch**ße :D.
Tatsächlich versuche ich Rekursion in der Regel zu vermeiden, aus einigen Gründen:
- Rekursion kann zu einem Stack Overflow führen
- Rekursion ist schwerer zu verstehen
- Rekursion ist schwerer zu debuggen
- Rekursion kann langsamer sein
Wobei das natürlich immer von der Situation abhängig ist, z.B. kann Rekursion bei der Baumstruktur einfacher zu verstehen sein, dann greife ich auch lieber zur Rekursion.
Mit der Zeit wird das aber alles einfacher, deshalb ist Erfahrung in dem Beruf so wichtig.
Wie es so schön heißt: "Um Rekursion zu verstehen, muss man erst einmal Rekursion verstehen." (Dieser Satz ist seinerseits ein Beispiel von Rekursion.)
Vermutlich hast du in der Mathematik auch Schwierigkeiten mit vollständiger Induktion - die ist die Umkehrung von Rekursion.
Bei vollständiger Induktion fängt man z. B. mit der Aussage für die Zahl 0 an, und geht dann von einer natürlichen Zahl zur nächst höreren.
Bei Rekursion löst man zunächst ein gleichartiges (aber ein in gewissem Sinne einfacheres) Problem, bis man auf ein "triviales" Problem stößt ("Rekursionsabbruch").
Vielleicht wird es mit einem Beispiel verständlicher:
Wenn man die natürlichen Zahlen synthetisch aufbaut, definiert man erst einmal eine "Nachfolgerelation" (es ist eine Funktion):
0 ist nicht Nachfolger einer natürlichen Zahl
Jede weitere Zahl hat genau einen Nachfolger. Den Nachfolger von n nennen wir n'.
(wir nennen 0' "1", 1' "2" etc.)
Die Addition ("m + n") definieren wir induktiv:
m + 0 := m
m + n' := m' + n
Wenn wir Summen ausrechnen wollen, gehen wir in umgekehrter Richtung vor ("rekursiv"). Z. B.
5 + 3
3 = 2'
also 5 + 3 = 5 + 2' = 5' + 2
5' = 6
also 5 + 3 = 5 + 2' = 5' + 2 = 6 + 2
(erster Rekursionsschritt)
6 + 2 = 6 + 1' = 6' + 1 = 7 + 1 (zweiter Rekursionsschritt)
7 + 1 = 7 + 0' = 7' + 0 = 8 + 0 (dritter Rekursionsschritt)
Hiermit sind wir am Rekursionsende angekommen: 8 + 0 = 8