Rekursive Algorithmen

Ein rekursiver Algorithmus ist eine Methode, bei der ein Problem gelöst wird, indem man auf eine kleinere Version seiner selbst verweist. Die Idee entspricht den rekursiven Definitionen in der Mathematik: Wir beginnen mit einer Basis, und darauf folgt ein rekursiver Schritt, der den Algorithmus auf einem einfacheren Teil des Problems wiederholt.

 

 

Von der Definition zum Code

Wenn wir eine rekursive Definition haben, kann sie oft direkt in einen Algorithmus übersetzt werden. Man muss nur übersetzen:

 

• Basis: wann der Algorithmus stoppen kann.
• Rekursiver Schritt: wie das Problem reduziert wird und der Algorithmus sich selbst aufruft.

 

 

Beispiel: Fakultät

Die Fakultätsfunktion ist rekursiv definiert als

 

$$ \large 0! = 1 $$

$$ \large n! = n \cdot (n-1)!, \quad n \geq 1 $$

 

Dies lässt sich als Algorithmus in Pseudocode schreiben:

 

function factorial(n):
    if n = 0:
        return 1        // Basis
    else:
        return n * factorial(n - 1)   // rekursiver Schritt

 

 

Der Algorithmus stoppt, wenn \( \large n = 0 \); andernfalls ruft er sich selbst mit einer kleineren Zahl auf. Schließlich werden alle Aufrufe zum Ergebnis zurückgeführt.

 

 

Beispiel: Maximum in einer Liste

Wir können auch einen Algorithmus rekursiv definieren, um die größte Zahl in einer Liste zu finden:

 

• Basis: Wenn die Liste nur ein Element hat, ist dieses Element das Maximum.
• Rekursiver Schritt: Vergleiche das erste Element mit dem Maximum der restlichen Liste.

 

 

function max(list):
    if list has length 1:
        return list[0]            // Basis
    else:
        m = max(rest of list)     // rekursiver Schritt
        return the larger of list[0] and m

 

 

Praktisches Beispiel

 

Wenn wir die Liste \( \large [7, 2, 9, 4] \) haben:

max([7,2,9,4])

= größer von 7 und max([2,9,4])

= größer von 7 und größer von 2 und max([9,4])

= größer von 7 und größer von 2 und größer von 9 und max([4])

= größer von 7 und größer von 2 und größer von 9 und 4

= größer von 7 und größer von 2 und 9

= größer von 7 und 9

= 9

 

 

Zusammenfassung

Ein rekursiver Algorithmus übersetzt die Idee hinter einer rekursiven Definition in Code. Zuerst wird ein Basisfall angegeben, bei dem der Algorithmus stoppt. Danach wird ein rekursiver Schritt beschrieben, bei dem der Algorithmus sich selbst auf ein einfacheres Problem anwendet. Dieses Muster findet sich in vielen bekannten Algorithmen, wie Sortieren, Suchen und der Verarbeitung von Datenstrukturen.