Hilfe bei Rekursion

[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

[__deets__]

Was ist denn in deinen Worten der Unterschied zwischen linearer und verzweigter Rekursion? Und was kennst du an Beispielen für letztere?

[Tyroun]

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.

[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.

[Tyroun]

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

[__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.

[Tyroun]

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

[Tyroun]

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

[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

[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).