Hilfsraum für rekursive Funktionen im C-Programm verwenden?

Hier werden wir sehen, wie rekursive Funktionsaufrufe Hilfsraum benötigen. Wie unterscheidet es sich von einem normalen Funktionsaufruf?

Angenommen, wir haben eine Funktion wie unten gezeigt -

long fact(int n){
   if(n == 0 || n == 1)
      return 1;
   return n * fact(n-1);
}

Diese Funktion ist eine rekursive Funktion. Wenn wir es wie fact(5) aufrufen, speichert es die Adresse wie unten gezeigt im Stapel. -

fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)

Wenn sich die rekursive Funktion immer wieder selbst aufruft, wird die Adresse dem Stapel hinzugefügt. Wenn die Funktion also n-mal rekursiv aufgerufen wird, belegt sie O(n) Hilfsraum. Dies bedeutet jedoch nicht, dass die Raumkomplexität O(n) beträgt, wenn eine Normalfunktion n-mal aufgerufen wird. Bei normalen Funktionen wird die Adresse beim Aufruf auf den Stapel gelegt. Sobald der Vorgang abgeschlossen ist, wird die Adresse vom Stapel entfernt und in die Aufruffunktion eingegeben. Dann rufen Sie noch einmal an. Seine Komplexität ist also O(1).

Das obige ist der detaillierte Inhalt vonHilfsraum für rekursive Funktionen im C-Programm verwenden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!