Rekursive Funktionen in C#, Python und Racket

Wenn ich an mein Informatik-Studium zurück denke, dann kommen mir auch rekursive Funktionen in den Sinn. Bereits in den ersten Vorlesungen und Übungen mussten wir verschiedene Funktionen als rekursive Funktionen in der Sprache Racket umsetzen. In diesem Beitrag möchte ich euch nun einige „Standard“-Funktionen zeigen, welche man sicherlich in jedem Informatik-Studium schreiben muss. Dabei werde ich neben C# diese auch in Python schreibe. Zunächst wollen wir aber die Frage beantworten, was eigentlich eine rekursive Funktion ist. Kurz gesagt, ist eine Funktion rekursiv, wenn sie sich selbst aufruft. Wir finden also im Rumpf der Funktion einen Aufruf derselben Funktion.

Man benutzt eine rekursive Funktion zum Beispiele gerne, um mathematische Funktionen abzubilden. So hat sicherlich jeder schon einmal von der Fakultät gehört. Diese Funktion multipliziert alle natürlichen Zahlen (ohne Null), welche kleiner oder gleich der übergebenen Zahl ist. So ist 5! = 5 * 4 * 3 * 2 * 1 oder aber 5! = 5 * 4! und so sehen wir hier bereits eine Rekursion.

Beginnen wir mit einer Funktion in Python, welche wir factorial nennen wollen.

def factorial(number):
    if number <= 1:
        return 1

    return number * factorial(number - 1)

Und hier folgt die gleiche Funktion in C# unter dem Namen GetFactorial.

static int GetFactorial(int number)
{
    if (number <= 1)
        return 1;

    return number * GetFactorial(number - 1);
}

Was schon auffällt, ist die Tatsache, dass der Aufbau beider Funktionen nahezu identisch ist. Wir bekommen jeweils eine Zahl übergeben und überprüfen, ob diese etwa 1 oder kleiner ist. Dies wird auch Abbruchbedingung genannt, denn an einem gewissen Punkt muss unsere Rekursion abbrechen. Ansonsten multiplizieren wir die übergebene Zahl mit dem Funktionsaufruf der nächst kleineren Zahl. Hier das ganze auch noch in Racket, der Sprache, welche ich im ersten Jahr an der Universität in Informatik lernen musste.

(define (factorial num)
  (if (<= num 1)
      1
      (* num (factorial (- num 1)))))

Auch hier ist der Aufbau nahezu identisch, aber man muss sich an die vielen Klammern gewöhnen…

Schauen wir uns noch ein weiteres Beispiel an: die Fibonacci-Folge. Diese Folge ist die unendliche Folge natürlicher Zahlen, die mit der Zahl 0 und von der Zahl 1 gefolgt wird. Im Anschluss ergibt jeweils die Summe zweier aufeinanderfolgender Zahlen die unmittelbar danach folgende Zahl.

Beginnen wir wieder mit Python.

def fibonacci(number):
    if number <= 0:
        return 0

    if number == 1:
        return 1

    return fibonacci(number - 1) + fibonacci(number - 2)

Gefolgt von C#.

static int GetFibonacciNumber(int number)
{
    if (number <= 0)
        return 0;

    if (number == 1)
        return 1;

    return GetFibonacciNumber(number - 1) + GetFibonacciNumber(number - 2);
}

Und zum Schluss wieder Racket.

(define (fibonacci num)  
  (if (<= num 0)
      0
      (if (= num 1)
          1
          (+ (fibonacci (- num 1)) (fibonacci (- num 2))))))

Auch hier beginnen wir wieder mit der Angabe der Abbruchbedingung. Sollte die übergebene Zahl kleiner als 0 sein, so liefern wir 0 zurück und für den Fall, dass die Zahl 1 ist, geben wir 1 zurück. Für die anderen Zahlen addieren wir einfach die beiden vorherigen Zahlen.

Mit diesen Funktionen hat damals mein Informatik-Studium begonnen. Daher hatte ich ein wenig Freude diese beiden Funktionen noch einmal in einer anderen Programmiersprachen zu schreiben, auch wenn der Aufbau der Methoden doch immer identisch ist und sich nur in der Syntax unterscheidet.