Fachkonzept - Natürliche Zahlen als rekursive Datenstruktur

Natürliche Zahlen als rekursive Datenstruktur

Eine natürliche Zahl ist entweder eine Null oder Nachfolger einer natürlichen Zahl.

Die Struktur der Menge der natürlichen Zahlen kann somit rekursiv beschrieben werden.

Diese rekursive Struktur ist die Grundlage vieler rekursiver Algorithmen zur Verarbeitung natürlicher Zahlen.

Entwicklung rekursiver Algorithmen zur Verarbeitung natürlicher Zahlen

Die Entwicklung rekursiver Algorithmen zur Verarbeitung natürlicher Zahlen soll anhand eines Beispiels verdeutlicht werden.

Beispiel: Es soll die Summe der ersten n natürlichen Zahlen berechnet werden.

Wir betrachten zunächst konkrete Fälle und entwickeln für diese Fälle (rekursive) Problemreduktionsschritte:

summe(0) -> 
    0

summe(5) ->
    5 + summe(4)

Der erste Problemreduktionsschritt betrifft den Rekursionsanfang. Hier kann man direkt die Lösung angeben. Der zweite Problemreduktionsschritt ist rekursiv. Hier wird das Problem auf ein strukturgleiches, aber verkleinertes Problem reduziert. Die Verkleinerung des Problems erfolgt dadurch, dass die zu verarbeitende natürliche Zahl kleiner wird. Mit Hilfe solcher Problemreduktionsschritte lässt sich die gesuchte Anzahl bestimmen - wie die folgende Reduktionskette zeigt.

summe(5) -> 
5 + summe(4) ->
5 + (4 + summe(3)) ->
5 + (4 + (3 + summe(2))) ->
5 + (4 + (3 + (2 + summe(1)))) ->
5 + (4 + (3 + (2 + (1 + summe(0))))) ->
5 + (4 + (3 + (2 + (1 + 0)))) ->
5 + (4 + (3 + (2 + 1))) -> 
5 + (4 + (3 + 3)) -> 
5 + (4 + 6) -> 
5 + 10 ->
15

Folgende Problemreduktionsstrategie liegt der gezeigten rekursiven Problemlösung zu Grunde:

Betrachte zunächst den Fall, dass die natürliche Zahl die Zahl 0 ist und gib die Lösung für diesen Fall direkt an.

Betrachte dann den Fall, dass die natürliche Zahl größer als 0 ist und somit Nachfolger einer natürlichen Zahl ist. Führe die Berechnung auf eine analoge Berechnung der Vorgängerzahl zurück.

Die konkreten Problemreduktionsschritte werden jetzt zu einem Algorithmus / Programm verallgemeinert.

def summe(zahl):
    if zahl == 0:
        return 0
    else:
        return zahl + summe(zahl-1)

Ein Test bestätigt das oben bereits per Reduktionskette ermittelte Ergebnis.

>>> summe(5)
15