Rekursion

Eine rekursive Funktion, ist eine Funktion, die sich selber aufruft. Mit Ausnahme von main() können alle Funktionen sich selbst aufrufen. Doch was bringt uns das?

Rekursion trifft man oft an, denn in der Mathematik wird viel durch Rekursion definiert. So ist die n*m in der Mathematik "n₁+n₂+n₃+...+n_m".

Wir haben aber eine Multiplikation doch schon mittels Schleife gelöst (diese Lösungsweg nennt sich Iteration). Was bringt also Rekursion? In der Tat kann man nahezu jede Rekursion auch Iterativ lösen - so zB die Multiplikation. Bei anderen Aufgabenstellungen kann es sein, dass die iterative Lösung viel länger und komplizierter ist, als die rekursive. Generell gilt aber, dass Iteration zu bevorzugen ist (es sei denn, die rekursive Lösung ist simpler, klarer und kürzer).

Schauen wir uns einmal die Multiplikation rekursiv an:

    #include<iostream>
    using namespace std;

    int multiply(int, int);

    int main()
    {
      cout<<"5 * 32 = "<<multiply(5,32)<<"\n";
    }

    int multiply(int num, int times)
    {
      if(times==0) return 0;
      return num + multiply(num,times-1);
    }

Wir sehen, dass die rekursive Lösung kürzer ist, als die iterative. Aber dennoch ist die iterative Lösung wesentlich besser. Die iterative Lösung ist nicht wesentlich komplexer und länger.

Eine rekursive Funktion braucht immer eine Abbruch-Bedingung. In unserem Beispiel ist diese Bedingung: wenn times 0 ist, ist das Ergebnis auch 0. Jede Rekursion braucht so eine Ausnahme, denn sonst läuft sie ewig.

Dieses Beispiel war sehr mies, zugegeben - aber es verdeutlicht den Ablauf von Rekursion. Doch nun zu einem sinnvolleren Beispiel: Fakultät. Fakultät ist so definiert: Die Zahl n ist das produkt all ihrer Vorgänger. Wobei fakultaet(0) und fakultaet(1) per Definition 1 ergeben. Mathematische Notation: F(x)=x*F(x-1). Hier können wir die mathematische Notation wieder 1:1 übernehmen.

    #include<iostream>
    using namespace std;

    int factIter(int);
    int factRec(int);

    int main()
    {
      cout<<"Bitte eine Zahl eingeben: ";
      int zahl;
      cin>>zahl;
      cout<<zahl<<"! ist "<<factRec(zahl)<<"(rekursiv) und "<<factIter(zahl)<<"(iterativ)\n";
    }

    int factIter(int num)
    {
      int result=1;
      for(int i=1; i<=num; ++i)
      {
        result*=i;
      }
      return result;
    }

    int factRec(int num)
    {
      if(num==0)
        return 1;
      return num * factRec(num-1);
    }

Hier sehen wir, dass die iterative Version schon ein bisschen komplizierter geworden ist. Wir können erahnen, dass bei komplexeren Problemen die iterative Version auch immer komplexer wird, während die rekursive Version ziemlich klein und übersichtlich bleibt. Doch auch hier gilt: Iteration ist besser, denn das Beispiel ist nicht komplex genug um Rekursion zu rechtfertigen.

Das Problem von Rekursion ist, dass sie sich erst lohnt wenn man zu wirklich komplexen Strukturen kommt. (Dem erfahrenen Informatiker sei gesagt, dass sich Rekursion sehr gut bei Bäumen einsetzen lässt). Rekursion hat noch ein weiteres Manko: es kann zu einem Stack Overflow kommen. Dies passiert dann, wenn times zu groß ist - denn die Funktion wird times-mal aufgerufen und jedesmal werden num und times kopiert und auf den Stack gelegt. (weiters hat ein Funktionsaufruf auch noch einen gewissen Overhead). Das führt dazu, dass bei times = 100000 (oder auch etwas mehr) der Stack überfüllt ist, und das Programm abstürtzt. Die Stackgröße lässt sich zwar über den Compiler anpassen, aber bei Rekursion sollte man immer acht geben, dass die Rekursion nicht zu tief wird.

top