Seite 1 von 1
Hilfe bei Rekursion
Verfasst: Mittwoch 21. April 2021, 11:32
von Tyroun
Guten Tag zusammen,
ich beschäftige mich gerade mit dem Thema Rekursion, da das momentan in meinem Studium dran kommt. Nun ja ich verstehe, die Mechanik das sich bei der Rekursion sich immer die Funktion selbst aufruft schon, aber bei mir hängt es noch die Umsetzung in Code.
Also die lineare Rekursion kapier ich langsam, also wie man zum Beispiel die Fibonacci-Zahlen mit Rekursion berechnet. Aber die verzweigte Rekursion kapier ich noch nicht ganz. Hat da jemand Tipps, für Tutorials oder Bücher?
Ich habe zum Beispiel eine Aufgabe die ich jetzt schon länger versuche zu lösen und zwar:
Schreiben sie eine Funktion, die eine Liste mit Integer-Werten als Input bekommt. Die Funktion
soll nun die Summe dieser Listenelemente bestimmen. Implementieren Sie eine solche Funktion in Python, und zwar (1) einmal als lineare Rekursion und (2) einmal als verzweigte Rekursion.
Den linearen Teil hab ich hinbekommen der war nicht so schwer, aber der Teil mit der verzweigten Rekursion bekomme ich einfach nicht hin, könnte mir hier jemand helfen ?
LG
Re: Hilfe bei Rekursion
Verfasst: Mittwoch 21. April 2021, 13:27
von __deets__
Was ist denn in deinen Worten der Unterschied zwischen linearer und verzweigter Rekursion? Und was kennst du an Beispielen für letztere?
Re: Hilfe bei Rekursion
Verfasst: Mittwoch 21. April 2021, 13:57
von Tyroun
__deets__ hat geschrieben: Mittwoch 21. April 2021, 13:27
Was ist denn in deinen Worten der Unterschied zwischen linearer und verzweigter Rekursion? Und was kennst du an Beispielen für letztere?
Also Merge Sort ist zum Beispiel eine verzweigte Rekursion, da Splittet man ja die Liste in der Mitte in eine Rechte und Linker Hälfte, mit denen man wiederum die Funktion aufruft. Bei der linearen Rekursion ist das anders zum Beispiel mit der Liste aus der Aufgabe, da splittet man die Liste ja nicht immer in der Mitte, sondern nimmt das erste Element und addiert den Funktionsaufruf mit der Liste ohne das erst Element (Also zB:
return arr[0] + arr[1:]
Besser kann ich es grad nicht erklären.
Re: Hilfe bei Rekursion
Verfasst: Mittwoch 21. April 2021, 14:18
von Sirius3
Damit hast Du auch fast schon die Lösunge Deines Summen-Problems beschrieben: Du nimmst die Linke Häfte, bildest die Summe, und die rechte Hälfte, und addierst beide.
Re: Hilfe bei Rekursion
Verfasst: Samstag 24. April 2021, 09:18
von Tyroun
Sirius3 hat geschrieben: Mittwoch 21. April 2021, 14:18
Damit hast Du auch fast schon die Lösunge Deines Summen-Problems beschrieben: Du nimmst die Linke Häfte, bildest die Summe, und die rechte Hälfte, und addierst beide.
Hmm ok ich bin leider nicht auf die Lösung gekommen. Ich hab das Problem, dass ich nicht weiß wie ich den Additionsschritt realisieren kann.
Also so würde ich auf jeden fall die Liste teilen:
Code: Alles auswählen
def sum_list(arr):
if len(arr) > 1:
#Mitter des Arrays abgerundet
m = len(arr)//2
#Array in 2 Hälften zerteilen
L = arr[:m]
R = arr[m:]
#Erste Hälfte Sortieren
merge_sort(L)
#Zweite Hälfte Sortieren
merge_sort(R)
Aber danach komm ich nicht mehr weiter
Re: Hilfe bei Rekursion
Verfasst: Samstag 24. April 2021, 09:23
von __deets__
Wenn du nur zwei hast, addierst du die. Und natürlich musst du auch die Ergebnisse addieren. Und dazu solltest du auch die richtige Funktion aufrufen, und nicht ein merge sort.
Re: Hilfe bei Rekursion
Verfasst: Samstag 24. April 2021, 10:46
von Tyroun
__deets__ hat geschrieben: Samstag 24. April 2021, 09:23
Wenn du nur zwei hast, addierst du die. Und natürlich musst du auch die Ergebnisse addieren. Und dazu solltest du auch die richtige Funktion aufrufen, und nicht ein merge sort.
OK ich setzt mich nochmal dran und schau ob ich es schaff
Re: Hilfe bei Rekursion
Verfasst: Sonntag 25. April 2021, 13:31
von Tyroun
Tyroun hat geschrieben: Samstag 24. April 2021, 10:46
__deets__ hat geschrieben: Samstag 24. April 2021, 09:23
Wenn du nur zwei hast, addierst du die. Und natürlich musst du auch die Ergebnisse addieren. Und dazu solltest du auch die richtige Funktion aufrufen, und nicht ein merge sort.
OK ich setzt mich nochmal dran und schau ob ich es schaff
Also ich habe es endlich geschafft, also hat sich es erledigt. Danke für eure Hilfe
Re: Hilfe bei Rekursion
Verfasst: Montag 26. April 2021, 06:57
von Sirius3
Hier die Lösung, für alle, die auf diesen Thread stoßen:
Code: Alles auswählen
def sum_list(numbers):
length = len(numbers)
if length > 1:
return sum_list(numbers[:length//2]) + sum_list(numbers[length//2:])
if length == 1:
return numbers[0]
return 0
Re: Hilfe bei Rekursion
Verfasst: Montag 26. April 2021, 18:24
von nezzcarth
Ich finde, das ist ein sehr schönes Beispiel dafür, was ein guter Algorithmus so ausmachen kann, insb. auch, was Pythons Rekursionslimit angeht. (Und vermutlich das einfachste Beispiel für Divide & Conquer, das ich bisher gesehen habe).