Eine Funktion ist rekursiv, wenn sie sich selbst aufruft. Sie braucht zwei Teile. Die Abbruchbedingung (Basisfall) löst den kleinsten Fall direkt, ohne weiteren Aufruf. Der Rekursionsschritt führt das Problem auf ein kleineres zurück und ruft dafür die Funktion selbst auf. Jeder Aufruf muss dem Basisfall näherkommen, sonst endet die Rekursion nie. Das Standardbeispiel ist die Fakultät:

Bei jedem Aufruf legt der Rechner einen Block auf den Aufrufstapel: Er enthält die Parameter, die lokalen Variablen und die Stelle, an der es nach dem Aufruf weitergeht. Der Stapel arbeitet wie ein Tellerstapel, es wird oben abgelegt und oben entfernt. Endet ein Aufruf, wird sein Block entfernt, und der Aufrufer macht weiter. Der Stapel hat begrenzte Größe: Zu viele verschachtelte Aufrufe führen zum Stapelüberlauf, in Python zum Fehler RecursionError (Grenze standardmäßig etwa 1000 Aufrufe).

Bei linearer Rekursion ruft sich die Funktion pro Durchlauf höchstens einmal selbst auf, wie $\texttt{fak}$. Bei verzweigter Rekursion ruft sie sich mehrfach auf, und die Aufrufe bilden einen Baum. Beispiel sind die Fibonacci-Zahlen 0, 1, 1, 2, 3, 5, 8, ...: Jede ist die Summe der beiden vorigen.

Die Funktion hat zwei Abbruchfälle ($n = 0$ und $n = 1$) und zwei rekursive Aufrufe. Die Zahl der Aufrufe wächst schnell: $\texttt{fib(5)}$ braucht 15 Aufrufe, $\texttt{fib(30)}$ etwa 2,7 Millionen, weil dieselben Teilwerte immer wieder berechnet werden.

Divide and Conquer (teile und herrsche) zerlegt ein Problem in kleinere, gleichartige Teilprobleme, löst sie rekursiv und setzt die Teillösungen zur Gesamtlösung zusammen. Die Phasen heißen Teilen, Lösen und Zusammenführen. Mergesort, Quicksort und die binäre Suche arbeiten so. Die Funktion $\texttt{maxi}$ liefert das größte Element von $\texttt{l[lo]}$ bis $\texttt{l[hi]}$:

Jede rekursive Funktion lässt sich durch eine Schleife ersetzen, notfalls mit einem selbst verwalteten Stapel, und umgekehrt. Die Quersumme aus der Lektion Algorithmik und Programmierung geht rekursiv so: $\texttt{def quersumme(n):}$, dann bei $\texttt{n < 10}$ den Wert $\texttt{n}$ zurückgeben, sonst $\texttt{return n \% 10 + quersumme(n // 10)}$. Für 4729 ergibt das 9 + 2 + 7 + 4 = 22.

Die iterative Fibonacci-Funktion merkt sich die letzten beiden Werte und braucht nur $n$ Durchläufe.

Backtracking (Zurückverfolgen) löst Suchprobleme, indem es eine Teillösung Schritt für Schritt aufbaut. Lässt sie sich nicht mehr zu einer Lösung erweitern (Sackgasse), nimmt es den letzten Schritt zurück und probiert die nächste Möglichkeit. Das Zurücknehmen übernimmt der Aufrufstapel: Kehrt ein Aufruf ohne Erfolg zurück, macht der Aufrufer mit seiner nächsten Wahl weiter. Beispiel ist das n-Damen-Problem: n Damen sollen so auf ein Brett mit n mal n Feldern, dass keine eine andere schlägt. Eine Dame schlägt in ihrer Zeile, Spalte und beiden Diagonalen. Man setzt Zeile für Zeile eine Dame: