Linux C Programming Tutorial Teil 18:Rekursive Funktionen

Unabhängig von der Programmiersprache, die Sie verwenden, lernen Sie, je mehr Sie mit dem Codieren beginnen, Konzepte kennen, die Ihren Code klar und leicht lesbar/verständlich machen. Auch in C gibt es mehrere solcher Konzepte. Eine davon sind „rekursive Funktionen“, die wir hier in diesem Artikel besprechen werden.

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft. Der Aufruf kann direkt aus dem Rumpf der Funktion oder indirekt aus einer anderen Funktion erfolgen, die von der betreffenden Funktion aufgerufen wird.

Es folgt ein Beispiel für direkte Rekursion:

int func (int a)
{
    //statements

    func(a-1);

    // statements

    return 0;
}

Und hier ist ein Beispiel für indirekte Rekursion:

int func (int a)
{
    //statements

    func_new(a);

    // statements

    return 0;
}

int func_new(int b)
{
    //statements

    func(b-1);

    //statementsur

    return 0;
}

Wie bereits eingangs erwähnt, hilft Ihnen die Rekursion, kompakten Code zu erhalten, der nicht nur einfach zu schreiben, sondern auch leicht zu verstehen und zu überprüfen ist. Nehmen wir ein Beispiel, um diesen Vorteil deutlicher zu machen.

Ich bin sicher, dass Sie alle schon einmal vom Konzept der Fakultät gehört haben. Für diejenigen, die es nicht wissen, ist die Fakultät das Ergebnis, das Sie erhalten, wenn Sie eine ganze Zahl mit allen positiven ganzen Zahlen multiplizieren, die kleiner sind. Beispielsweise ist die Fakultät von 5 5x4x3x2x1, was 120 entspricht.

Hier ist ein einfacher Code, um die Fakultät einer Zahl zu finden:

#include <stdio.h>

int main()
{
 int a = 0, i = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 for(i=1; i<=a; i++)
 {
 fact = fact * i;
 
 }
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Beachten Sie, dass dieser Code nur dazu dient, Sie wissen zu lassen, wie die Fakultät einer Zahl durch ein C-Programm berechnet werden kann. Das Programm kümmert sich nicht um Sonderfälle, die die Genauigkeit des erzeugten Ergebnisses beeinträchtigen könnten.

Dies ist also eine der vielen Möglichkeiten, wie Sie die Fakultät einer Zahl berechnen können, ohne eine rekursive Funktion zu verwenden. Sehen wir uns nun ein Stück Code an, das Rekursion verwendet, um eine Fakultät zu berechnen.

#include <stdio.h>

int factorial (int b)
{
 if(!b)
 return 1;
 
 return (b * factorial(b-1));
}

int main()
{
 int a = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 fact = factorial(a);
 
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Wie Sie sehen, ist die Funktion "Fakultät", die die Fakultät tatsächlich berechnet, sehr kompakt. Und wenn Sie genau aufpassen, ist es auch sehr einfach zu verstehen.

Für diejenigen, die nicht wissen, was passiert, wird der vom Benutzer eingegebene Wert, z. B. 5, an die Funktion „factorial“ weitergegeben, wenn sie zum ersten Mal aus der Funktion „main“ aufgerufen wird. Innerhalb der Funktion „Factorial“ wird geprüft, ob der Eingabewert Null ist, was nicht der Fall ist, wenn die Funktion zum ersten Mal mit dem Eingabewert „5“ aufgerufen wird.

Dann enthält die return-Anweisung einen Ausdruck, der 5 mit dem Rückgabewert von 'factorial(4)' multipliziert. Jetzt wird also die Funktion „Fakultät“ erneut ausgeführt, und wir erreichen den folgenden Ausdruck:return (4 * factorial(3)). Und dann wieder diese Schritte wiederholen.

Wenn Sie also grob hinsehen, werden diese Funktionsaufrufe folgendermaßen gestapelt:

• 5 * Fakultät(4)
• 4 * Fakultät(3)
• 3 * Fakultät(2)
• 2 * Fakultät (1)
• 1 * Fakultät (0)

Wenn nun factorial(0) ausgeführt wird, wird die „if“-Bedingung in der „factorial“-Funktion wahr und der Wert „1“ wird zurückgegeben. So vervollständigen sich nun die oben aufgeführten Aufrufe (vergleichen Sie den letzten Eintrag in der vorherigen Liste mit dem ersten Eintrag in dieser Liste usw.):

• 1 * 1
• 2 * (1*1)
• 3 * (2*(1*1))
• 4 * (3*(2*(1*1)))
• 5 *  (4 * (3*(2*(1*1))))

Das ist effektiv 5 * 4 * 3 * 2 * 1, was wiederum 120 ist, die Fakultät von 5.

So funktionieren also rekursive Funktionen. Obwohl die Vorteile der rekursiven Funktion, die wir bisher aufgelistet haben, unbestritten sind, gibt es auch einige Nachteile.

In unserem Beispiel oben haben beispielsweise alle vorherigen Aufrufe von „factorial“ darauf gewartet, dass die Funktionsverarbeitung abgeschlossen wird, bis der Aufruf „factorial(0)“ abgeschlossen ist. Ganz zu schweigen von der Tatsache, dass automatische oder lokale Variablen für jeden rekursiven Aufruf Speicher belegen.

Es gibt also praktisch keine Einsparungen an Speicherplatz, wenn Sie Rekursion verwenden. Außerdem gibt es keine Garantie dafür, dass Ihr Code schneller ausgeführt wird. Der wirkliche Vorteil einer rekursiven Funktion ist, wenn Sie sich mit Datenstrukturen befassen, die später als Teil dieser fortlaufenden C-Tutorial-Serie besprochen werden.

Schlussfolgerung

Abschließend lässt sich sagen, dass Sie die rekursive Funktion zwar bei Ihren täglichen Codierungsaufgaben möglicherweise nicht häufig verwenden, es sich jedoch um ein wichtiges Konzept handelt, dessen Sie sich bewusst sein müssen. Probieren Sie das hier erwähnte Beispiel aus und optimieren Sie es, um das Konzept der rekursiven Funktionen noch besser zu verstehen.