Rekursiv denken: Basisfall und Rekursion
Zerlegen Sie ein Problem in kleinere Kopien
Rekursiv denken: Basisfall und Rekursion ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was Rekursion bedeutet
Rekursion ist eine Funktion, die ein Problem löst, indem sie sich selbst für einen kleineren Teil aufruft, bis dieser Teil klein genug ist, um direkt beantwortet zu werden. 🌀
Vertrauen Sie auf die kleinere Kopie
Die entscheidende Denkweise ist der Vertrauenssprung: Nehmen Sie an, dass der rekursive Aufruf für die kleinere Eingabe bereits funktioniert, und bauen Sie darauf Ihre Antwort auf.
Jede Rekursion benötigt einen Basisfall
Der Basisfall ist die kleinste Eingabe, die Sie ohne Rekursion beantworten. Ohne ihn ruft die Funktion sich immer weiter selbst auf und stürzt ab.
Der Rekursionsfall
Der Rekursionsfall reduziert das Problem und ruft sich selbst mit der kleineren Variante auf. Jeder Aufruf muss dem Basisfall näher kommen.
Die Fakultät als erstes Beispiel
Hier zeigt Fakultät beide Teile: einen Basisfall bei null und einen rekursiven Aufruf mit n minus eins.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)So funktioniert der Aufrufstapel
Jeder Aufruf wartet auf dem Aufrufstapel, bis sein innerer Aufruf zurückkehrt. Der tiefste Aufruf wird zuerst abgeschlossen, danach werden die Ergebnisse wieder nach oben zurückgereicht.
Achten Sie auf die Rekursionstiefe
Python begrenzt die Rekursionstiefe standardmäßig auf ungefähr 1000. Für tiefe Rekursion in Programmierwettbewerben benötigen Sie sys.setrecursionlimit, um einen Laufzeitfehler zu vermeiden.
import sys
sys.setrecursionlimit(300000)Machen Sie bei jedem Aufruf Fortschritte
Eine korrekte Rekursion verkleinert die Eingabe immer in Richtung des Basisfalls. Wenn sie irgendwann erneut dieselbe Größe erreicht, läuft sie endlos weiter. ⚠️
Eine Liste rekursiv summieren
Diese rekursive Summe nimmt das erste Element weg und überlässt es dann dem Aufruf, den Rest der Liste zu addieren.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])Rekursionsbäume zeigen Verzweigungen
Wenn eine Funktion mehr als einen Aufruf erzeugt, bildet die Arbeit einen Rekursionsbaum. Seine Größe zeigt die Gesamtkosten.
Wiederholte Arbeit kann langsam sein
Die naive Fibonacci-Berechnung berechnet dieselben Werte immer wieder und führt zu exponentieller Laufzeit. Durch Memoisierung dieser Ergebnisse lässt sich das sofort beheben.
Kurze Überprüfung
Was passiert, wenn eine rekursive Funktion keinen Basisfall hat?
Zusammenfassung: Zwei Teile, eine Idee
Sie haben gelernt, dass Rekursion einen Basisfall zum Beenden und einen rekursiven Fall benötigt, der die Eingabe verkleinert. Vertrauen Sie dem kleineren Aufruf, und der Rest ergibt sich von selbst. 🎯
Häufig gestellte Fragen
Ist die Lektion „Rekursiv denken: Basisfall und Rekursion“ kostenlos?
Ja — der vollständige Text von „Rekursiv denken: Basisfall und Rekursion“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Rekursiv denken: Basisfall und Rekursion“?
Zerlegen Sie ein Problem in kleinere Kopien Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Rekursiv denken: Basisfall und Rekursion“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Rekursiv denken: Basisfall und Rekursion
- Alle Teilmengen erzeugen
- Permutationen und die N-Queens-Idee
- Mit Beschneiden das Zeitlimit einhalten