Rekursive Programmierung - Hilfe

[FramaLama]

Hallo Miteinander,
ich studiere Informatik und wir behandeln eben die rekursive Programmierung, die für mich, als Anfänger mit oberflächlichen Kenntnissen, eine echte Belastung darstellt
Könnt mir jemand bitte bei diesem Auszug helfen?
def palindrome(word):
if len(word) <=1:
return True
if word[0] != word[-1]:
return False
return palindrome(word[1:-1])
Der Code soll iterative umgeschrieben werden, ich verstehe jedoch nicht, wie die Rekursion geht, bzw. ich mit dieser arbeiten soll.
Ich möchte keine komplette Lösung (hätte natürlich nichts dagegen ), will aber die Thematik echt verstehen, daher wäre ein Ratschlag, Tipp usw. echt super
Dankeschön

[__blackjack__]

@FramaLama: Was genau verstehst Du daran denn nicht? Spiel das doch mal für ein paar einfache Beispiele für Palindrome und Nicht-Palindrome mit Papier und Bleistift durch. Also beispielsweise was passiert bei einer leeren Zeichenkette, was bei einem einzelnen Buchstaben, und was bei "anna", "python", und "revolver" in jedem Schritt.

[FramaLama]

@FramaLama: Was genau verstehst Du daran denn nicht? Spiel das doch mal für ein paar einfache Beispiele für Palindrome und Nicht-Palindrome mit Papier und Bleistift durch. Also beispielsweise was passiert bei einer leeren Zeichenkette, was bei einem einzelnen Buchstaben, und was bei "anna", "python", und "revolver" in jedem Schritt.

Danke für deine Antwort
Speziell die letzte Zeile.. also ich weiß, dass das der Aufruf der Funktion ist und wir dadurch quais merken können ,dass es sich um eine Rekursion handelt, aber was macht sie da, also welchen nutzen hat sie und wie kann ich das umschreiben?
Die Ergebnisse aus den einzelnen Strings habe ich verstanden, nur bin ich bei der Vorgehensweise überfragt

[__blackjack__]

@FramaLama: Ich verstehe immer noch nicht was Du da nicht verstehst. Was die Rekursion macht steht doch da, Du musst nur nachvollziehen was passiert. Wenn Du Funktionsaufrufe verstanden hast, dann müsstest Du auch rekursive Aufrufe verstehen, denn da ist an sich nichts besonderes dran. Die letzte Zeile ruft eine Funktion auf und gibt deren Rückgabewert zurück. Das ist in diesem Fall die Funktion selbst die da aufgerufen wird. Die Laufzeitumgebung erkennt da nicht das es sich um einen rekursiven Aufruf handelt, sondern sieht da einfach nur einen Aufruf wie jeden anderen auch. Und das ist er wie gesagt auch. Wenn Du das nachvollziehen willst, musst Du also nur ganz normal Funktionsaufrufe verstanden haben.

Also wenn eine Funktion zu einem Aufruf kommt, werden die Argumente ausgewertet, an die aufgerufene Funktion übergeben, die macht dann was damit, gibt ein Ergebnis zurück, und dann geht es an der Stelle in der aufrufenden Funktion mit diesem Ergebnis weiter.

Vielleicht hilft das mit dem drüber nachdenken wie die Schritte aussehen, wenn man das nicht so prozedural formuliert, sondern als *einen Ausdruck*, wo man die konkreten Werte eines Beispiels leichter einsetzen kann:

Code: Alles auswählen

def is_palindrome(word):
    return len(word) <= 1 or (word[0] == word[-1] and is_palindrome(word[1:-1]))

[grubenfox]

Speziell die letzte Zeile.. also ich weiß, dass das der Aufruf der Funktion ist und wir dadurch quais merken können ,dass es sich um eine Rekursion handelt, aber was macht sie da, also welchen nutzen hat sie und wie kann ich das umschreiben?

Vielleicht einfach ausprobieren?

Code: Alles auswählen

def is_palindrome(word):
    print('Funktion wurde aufgerufen mit', word, '| word ist', len(word), 'Zeichen lang')
    if len(word) <=1:
        return True
    if word[0] != word[-1]:
        return False
    print('Rufe is_palindrome auf mit', word[1:-1])
    return is_palindrome(word[1:-1])

print(is_palindrome("ANNA"))
print(is_palindrome("RELIEFPFEILER"))

was das umschreiben betrifft: mir würde ja reichen wenn die iterative Lösung die gleichen Ergebnisse liefert wie die rekursive Variante. Egal was da die einzelnen Zeilen der rekursiven Ausführung da machen. Aber ich bin weder hier noch sonst wo ein Lehrer.

Also vergesse die Rekursion und denke einfach iterativ... Das Problem geistig umzuschalten wenn man eine Lösung verstanden hat um dann eine ganz andere Lösung zu konstruieren kenne ich aber auch.

[__blackjack__]

Naja die Standardlösung wenn man einfach eine `is_palindrome()`-Funktion schreiben will, ist ja einfach:

Code: Alles auswählen

def is_palindrome(word):
    return word == word[::-1]

Da dürfte es dann aber herausfordernd werden wenn der Dozent oder Tutor nach den Umformungsschritten von der rekursiven zu dieser Lösung fragt.

Und letztlich sollte das nicht so schwer sein weil die Originalfunktion endrekursiv ist, und es dafür ja ein sehr einfaches Vorgehen gibt, das in eine Schleife zu überführen, wo man eigentlich gar nicht mal auf den Inhalt schauen muss. Man muss sich nur anschauen mit welchem/welchen Wert(en) die rekursive Funktion am Ende aufgerufen wird, und diese(n) Wert(e) am Ende einer Schleife entsprechend zuweisen. Das ist in diesem Fall eine ganz triviale Änderung der Originalfunktion.

[__blackjack__]

Hier mal die wahrscheinlich am wenigsten erklärungsbedürftige Lösung die bei jeder Endrekursion funktionieren sollte: Den gesamten Funktionskörper in eine Endlosschleife stecken (die ja durch den/die Rekursionsanker abgebrochen wird) und am Ende der Schleife den rekursiven Aufruf einfach durch eine entsprechende Zuweisung an die Argumente der Funktion ersetzen:

Code: Alles auswählen

def is_palindrome(word):
    if len(word) <= 1:
        return True

    if word[0] != word[-1]:
        return False

    return is_palindrome(word[1:-1])

# =>

def is_palindrome(word):
    while True:
        if len(word) <= 1:
            return True

        if word[0] != word[-1]:
            return False

        word = word[1:-1]