Einordnung Rekursion
Schauen wir uns jetzt die Funktionen von eben nochmal genauer an. Was haben die beiden Funktionen gemeinsam?
In beiden Fällen können wir das eigentliche Problem nicht direkt lösen. Wenn die Liste beispielswiese nur aus einem Element besteht, ist es trivial, die Summe aller Elemente der Liste zu bestimmen. Genauso ist es bei der Quersumme einer einstelligen Zahl. Zugegebenermaßen kann es auch noch relativ leicht sein, ein paar wenige Zahlen im Kopf zu addieren. Allerdings wird das auf Anhieb schon schwieriger, wenn die Listen bzw. Zahlen plötzlich deutlich größer sind.
Wenn wir uns sum_list nochmal genauer anschauen:
- Anstatt direkt alle Elemente der Liste auf einmal aufzusummieren, summieren wir einen Teil der Listenelemente und addieren dann ein weiteres Element drauf
- Das ist also, als würden wir das Problem in Teilprobleme aufteilen. Zum Beispiel ist die Summe aller Elemente der Liste
[4,7,1,1]die selbe wie die der Liste[7,1,1]plus die der Liste[4]. - Dieses Aufteilen können wir jetzt noch öfter machen, bis wir vier Listen mit nur je einem Element haben, die wir alle trivial aufsummieren können:
sum_list([4]) + sum_list([7]) + sum_list([1]) + sum_list([1]) = 4 + 7 + 1 + 1 = 13
Analoge Überlegungen können wir auch für die Quersumme eine Zahl machen. Bei beiden Funktionen lösen wir sozusagen das Problem nicht direkt, sondern wir verkleinern das Problem Schritt für Schritt, bis es nicht mehr möglich ist bzw. das Problem dann einfach zu lösen ist. Das ist die grundlegende Idee der Rekursion.
