Rekursion

Von Rekursion spricht man, wenn eine Funktion sich selber aufruft. Dies lässt sich manchmal als Ersatz für eine Schleife nutzen. Eine Rekursion sollte immer an eine Bedingung geknüpft sein, um eine Endlosrekursion zu vermeiden. Anders als bei einer Schleife führt eine Endlosrekursion aber zum Stackoverflow, da irgendwann der zu Verfügung stehende Stackspace des Programmes aus ist, und somit kein Speicher im Stackbereich mehr für den n-ten Aufruf der Rekursion zur Verfügung steht.
Als Beispiel dient die Rekursive Berechnung der Fibonacci Folge:
int fibonacci(int n)
{
    if(n > 2)
        return fibonacci(n-1) + fibonacci(n-2);
    if(n > 0)
        return 1;
    return 0;
}


Solange n größer 2 ist, ruft sich die Funktion rekursiv selber auf. Für die Fibonacci Folge sind 2 rekursive Aufrufe nötig, welche addiert werden. Zum Schluss gibt der eigentliche Funktionsaufruf das Ergebnis zurück.
Wie schon vorher erwähnt, ist es in C++ üblich, Code in .h/.hpp und .cpp Datei aufzuspalten, so das die Headerdatei von anderen .cpp Dateien eingebunden werden kann, und die Implementation in der .cpp Sourcedatei liegt. Anhand des Fibonaccibeispiels möchte ich dies nun demonstrieren.
fibonacci.h:
#ifndef FIBONACCI_H//(1)
#define FIBONACCI_H
int fibonacci(int n);//(2)
#endif // FIBONACCI_H //(3)


  1. Als erstes wird in der Headerdatei ein sogenannter Includeguard erstellt. Dieser besteht aus den 2 Präprozessoranweisungen #ifndef und #defined, wenn das Symbol FIBONACCI_H nicht definiert ist, wird es mit dem #define definiert, darauf hin folgt der einzubindende Codeblock, bei (3) endet dann der #if Block des Präprozessors aus (1). Dies verhindert, das eine Headerdatei mehrmals durch den Präprozessor in eine Sourcedatei eingebunden wird. Dies würde dann zu einem Namenskonflikt führen, da ja die Funktion fibonacci(int n) vorher schon durch die erste Einbindung in die Sourcedatei definiert wurde.
  2. Die Deklaration der Funktion fibonacci.
  3. Mit #endif wird der #ifndef Block des Präprozessors aus Zeile 1 abgeschlossen.
Die meisten IDEs generieren diesen Code direkt selber, wenn man die entsprechende Funktion nutzt. Es gibt noch die Alternative statt den Include Guards einfach den Präprozessorbefehl #pragma once zu nutzen. Dieser wird von allen gängigen Compilern unterstützt, ist aber nicht teil des C++ Standards.
fibonacci.cpp:
#include "fibonacci.h"//(1)

int fibonacci(int n){...}//(2)


Die fibonacci.cpp Datei enthält nun als erstes die #include Anweisung für fibonacci.h, danach folgen in der Regel weitere #include Anweisungen, welche in der .cpp Datei benötigt werden. Danach kommt die Implementation der fibonacci Funktion, welche die gleiche ist, wie die oben gezeigte.