Rekrusives Programmieren

[Newcomer]

Hi
da ich ja diesen wörtergenerator rekrusiv ansetzen wollte, haben einige gesagt, dass ich erstmal mit einfachen bsps anfangen sollte. Also zurück zu meinen Programmieranfängen.
Ich hab hier n Code der nicht so funktionieren soll, wie er soll (-:

Code: Alles auswählen

def verdoppeln(int,bis):
    for i in range(1,bis):
        return verdoppeln(int*2,bis-1)

tja und jetzt hab ich es so aufgerufen:

Code: Alles auswählen

a=verdoppeln(10,30)
print(a)

und was kommt bei mir!

Code: Alles auswählen

>>> 
None
>>> 

versteh ich nicht das soll doch was zurückgeben, iterativ würd ichs halt übernen generator machen.
Könnt ihr mir das erklären?
Danke im Vorraus

[EyDu]

Hallo.

Das einfachst Mittel um Rerkusion nachvollziehen zu können, ist jeden Schritt auf einem Blatt Papier nachzuvollziehen. Mach das einfach mal für bis=2 und gehe jede Anweisung schritt für Schritt durch. Ganz besonders wichtig ist natürlich der letze rekursive Aufruf der Funktion und dessen Ergebnis.

Dann stellt sich mir natürlich die Frage, was du mit der for-Schleife bezwecken möchtest. Die ist hier vollkommen überflüssig. Hinzu kommt, dass die for-Schleife sofort verlassen wird. Du führst sie also höchstens einmal aus.

Sebastian

[pillmuncher]

Ich hab hier n Code der nicht so funktionieren soll, wie er soll (-:

Code: Alles auswählen

def verdoppeln(int,bis):
    for i in range(1,bis):
        return verdoppeln(int*2,bis-1)

Wenn du es rekursiv machen willst, brauchst du keine for-Schleife. Statt dessen brauchst du einen sog. base case, AKA Abbruchbedingung:

Code: Alles auswählen

def verdoppeln(i, n):
    if n == 0:
        return i
    elif n > 0:
        return verdoppeln(i * 2, n - 1)
    else:
        raise ValueError('Zahl kaputt!! n muss größer als Null sein')

Der base case hier ist n == 0. n ist dabei eine Steuer-Variable, die solange modifiziert wird, bis der base case erreicht wird. i ist ein sog. Accumulator, dh. eine Datenstruktur, die die Ergebnisse jeder Rekursions-Stufe aufnimmt und die in die Rekursion weitergereicht wird. In deinem Beispiel ist es einfach ein int dessen Wert jedesmal verdoppelt wird. Hier ein anderes Beispiel:

Code: Alles auswählen

def umkehren(alist, acc):
    if alist == []:  # base case
        return acc
    else:            # rekursion
        return umkehren(alist[:-1], acc + alist[-1:])

print umkehren([1, 2, 3, 4], []) # --> [4, 3, 2, 1]

Rekursion braucht immer wenigstens einen base case und einen rekursiven Aufruf. Einen Accumulator braucht man nicht immer:

Code: Alles auswählen

def umkehren1(alist):
    if alist == []:  # base case
        return []
    else:            # rekursion
        return alist[-1:] + umkehren1(alist[:-1])

print umkehren1([1, 2, 3, 4]) # --> [4, 3, 2, 1]

Auch dein Beispiel braucht keinen Accumulator:

Code: Alles auswählen

def verdoppeln1(i, n):
    if n == 0:  # base case
        return i
    elif n > 0: # rekursion
        return 2 * verdoppeln1(i, n - 1)
    else:
        raise ValueError('Zahl kaputt!! n muss größer als Null sein')

Als Übungs-Aufgaben für Rekursion werden gerne das Umkehren von Listen verwendet, wie oben, oder das Erzeugen der Fibonacci-Folge oder die Türme von Hanoi. Die hab ich in QBASIC geschrieben als ich Rekursion gelernt habe, mitsamt grafischer Ausgabe.

Gruß,
Mick.

[mkesper]

Du hast auch ein Problem beim Funktionsaufruf, "int" ist eine eingebaute Funktion und sollte nicht überschrieben werden (genau wie z.B. "file").

[Newcomer]

Danke Leute, rekursion muss ich mir quasi selbst beibringen, denn ich hab in den Übungsbüchern ist das sehr schlecht erklärt. Die for schleife wird ja nicht mehr ausgeführt wenn n==0 ist. da dachte ich mir das könnte man als base case gebrauchen (: