Rekursion

Rekursion

"Um die Rekursion zu verstehen, muss man zuerst die Rekursion verstehen"

lat. recurrere: zurücklaufen

Informatik: "eine Funktion, die sich selbst aufruft"

man spricht von: rekursiven Funktionen / Methoden / Prozeduren (Aufruf selbst: Rekursion)
wichtig: benötigt Terminierungs- / Abbruchbedingung (damit nicht endlos)

Idee / Prinzip: Teile und Herrsche
"Problem auf ein einfacheres, aber gleichartiges zurückzuführen"

Rekursion vs. Iteration

jede Schleife lässt sich durch eine Rekursion ersetzen

iterativ

schleife(bedingung) {  
    // machetwas  
}  

orientiert sich stärker an der Ausführung / Optimierung der Algorithmen auf sequenziell arbeitenden Maschinen

rekursiv

void schleife() {  
    if(bedingung) {  
        //machetwas  
        schleife();  
    }  
}  

kompakte, klar strukturierte und leicht zu verifizierende Funktionsdefinitionen

Form: direkt über eine oder indirekt (wechselseitig) über mehrere Funktionen

Beispiel

iterativ

#include <stdio.h>  

void printLines(int x) {  
    while(x > 0) {  
        printf("\nlineNR. %d", x);  
        x--;  
    }  
}  

int main() {  
    printLines(5);  
    return 0;  
}  

rekursiv

#include <stdio.h>  

void printLines(int x) {  
    if(x > 0) {  
        printf("\nlineNR. %d", x);  
        printLines(x-1);  
    }  
}  

int main() {  
    printLines(5);  
    return 0;  
}  

Vor- und Nachteile

• kurze Form / leicht verständliche Lösung
• eventuelle Einsparung von Variablen
• teilweise sehr effiziente Problemlösungen
• bei rekursiven Datenstrukturen empfehlenswert
• weniger effizientes Laufzeitverhalten
  (Overhead / Stack-Funktionsaufruf)

📋 Fakultät

Schreibe eine rekursive Funktion, die die Fakultät einer nicht-negativen ganzen Zahl berechnet. Die Fakultät von n (geschrieben als n!) ist das Produkt aller positiven ganzen Zahlen kleiner oder gleich n. Beachte den Basisfall für 0!

📋 Türme von Hanoi

Eine beliebige Anzahl an Scheiben sollen sich von A nach C bewegen.
Wie viele Schritte werden benötigt um den Transfer durchzuführen?

Regeln:

• es darf immer nur jeweils eine Scheibe bewegt werden
• es kann immer nur die oberste Scheibe eines Stapels bewegt werden
• eine Scheibe kann nur abgelegt werden, wenn der Stab leer ist, oder wenn die Scheibe kleiner als die oberste Scheibe des Zielstapels ist