Linux C Programmierung Tutorial Teil 18: Rekursive Funktionen

Unabhängig von der Programmiersprache, die Sie verwenden, lernen Sie beim Programmieren immer mehr Konzepte, die Ihren Code prägnant und leicht lesbar/verständlich machen. Es gibt mehrere solcher Konzepte auch in C. Eines davon sind die ‘rekursiven Funktionen’, über die wir in diesem Artikel sprechen werden.

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

Nachfolgend ein Beispiel für direkte Rekursion:

int func (int a)  
{  
    //Anweisungen  
  
    func(a-1);  
  
    // Anweisungen  
  
    return 0;  
}

Und hier ist ein Beispiel für indirekte Rekursion:

int func (int a)  
{  
    //Anweisungen  
  
    func_new(a);  
  
    // Anweisungen  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //Anweisungen  
  
    func(b-1);  
  
    //Anweisungen  
  
    return 0;  
}

Wie bereits zu Beginn erwähnt, hilft Ihnen Rekursion, kompakten Code zu erreichen, der nicht nur leicht zu schreiben, sondern auch leicht zu verstehen und zu überprüfen ist. Lassen Sie uns ein Beispiel nehmen, um diesen Vorteil deutlicher zu machen.

Ich bin mir sicher, dass Sie alle schon von dem 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, die kleiner sind als sie, multiplizieren. Zum Beispiel ist die Fakultät von 5 gleich 5x4x3x2x1, was 120 entspricht.

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

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("Geben Sie eine Zahl ein: ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("Die Fakultät der Zahl ist: %d ", fact);  
 return 0;  
}

Bitte beachten Sie, dass dieser Code nur dazu dient, Ihnen zu zeigen, wie die Fakultät einer Zahl durch ein C-Programm berechnet werden kann. Das Programm berücksichtigt keine Randfälle, die die Genauigkeit des Ergebnisses beeinflussen könnten.

Dies ist also eine der vielen Möglichkeiten, die Fakultät einer Zahl ohne Verwendung einer rekursiven Funktion zu berechnen. Lassen Sie uns nun einen Codeabschnitt ansehen, der Rekursion verwendet, um eine Fakultät zu berechnen.

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("Geben Sie eine Zahl ein: ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("Die Fakultät der Zahl ist: %d ", fact);  
 return 0;  
}

Wie Sie sehen können, ist die Funktion ‘factorial’, die tatsächlich die Fakultät berechnet, sehr kompakt. Und wenn Sie genau hinsehen, ist sie auch sehr leicht zu verstehen.

Für diejenigen, die nicht wissen, was passiert, wird der Wert, den der Benutzer eingegeben hat, sagen wir 5, beim ersten Aufruf der Funktion ‘factorial’ aus der ‘main’-Funktion übergeben. Innerhalb der Funktion ‘factorial’ gibt es eine Überprüfung, ob der Eingabewert null ist, was beim ersten Aufruf der Funktion mit dem Eingabewert ‘5’ nicht der Fall ist.

Dann enthält die Rückgabewertung einen Ausdruck, der 5 mit dem Rückgabewert von ‘factorial(4)’ multipliziert. Jetzt wird die Funktion ‘factorial’ erneut ausgeführt, und wir erreichen den folgenden Ausdruck: return (4 * factorial(3)). Und dann wiederholen sich diese Schritte.

Wenn Sie also weitreichend betrachten, sieht es so aus, als würden diese Funktionsaufrufe gestapelt:

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

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

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

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

So funktionieren rekursive Funktionen. Während es keinen Zweifel an den Vorteilen rekursiver Funktionen gibt, die wir bisher aufgelistet haben, gibt es auch einige Nachteile.

Zum Beispiel warteten in unserem obigen Beispiel bis der Aufruf ‘factorial(0)’ abgeschlossen war, alle vorherigen ‘factorial’-Aufrufe darauf, dass die Funktionsverarbeitung abgeschlossen wurde. Ganz zu schweigen von der Tatsache, dass automatische oder lokale Variablen für jeden rekursiven Aufruf Speicher belegen.

Es gibt also effektiv keine Einsparungen im Speicherplatz, wenn Sie Rekursion verwenden. Außerdem gibt es keine Garantie, dass Ihr Code schneller ausgeführt wird. Der wirkliche Vorteil einer rekursiven Funktion zeigt sich, wenn Sie mit Datenstrukturen arbeiten, über die wir später im Rahmen dieser fortlaufenden C-Tutorial-Serie sprechen werden.

Fazit

Zusammenfassend lässt sich sagen, dass Sie möglicherweise nicht häufig rekursive Funktionen in Ihren täglichen Programmieraufgaben verwenden, es jedoch ein wichtiges Konzept ist, dessen Sie sich bewusst sein sollten. Probieren Sie das Beispiel aus, das wir hier erwähnt haben, und passen Sie es an, um das Konzept der rekursiven Funktionen noch besser zu verstehen.