Rekursive Funktion auf Stack

Question

Ich habe eine sehr einfache Funktion, um den maximalen, nicht negativen Wert eines ganzen Zahlenstapels herauszufinden. Ich möchte diese Funktion in eine rekursive transformieren. Es gibt mehr Punkte im Auge zu behalten:

• Bevor die Funktion ausgeführt wird, haben wir num initialisiert, haben aber keinen Wert zugewiesen. Und bitte, sollten wir nicht darauf verlassen, dass C automatisch 0-num unter bestimmten Bedingungen
• Nach dem Ausführen der Funktion des Stapel s leer vergeben werden und wir haben den maximalen nicht negativen Wert gespeichert in num
• I ist ein Anfänger in C und Datenstrukturen, also bitte schön :)

Dies ist die iterative Funktion:

void max_stack(stack *s, int *num){ 
    *num = 0; 
    int aux = 0; 
    while (!emptyStack(*s)){ 
     aux = top(*s); 
     pop(s); 
     if (aux>*num){ 
      *num = aux; 
     } 
    } 
} 

Answer 1

genau der iterativen Code zur Verfügung gestellt, um übereinstimmen, müssen wir auch überein die Annahme, dass 0 auch bei einem leeren Stack der Mindestwert ist, der im Zielparameter gespeichert wird.

Damit:

void recursive_max_stack(stack *s, int *num) 
{ 
    if (emptyStack(*s)) 
    { 
     *num = 0; 
     return; 
    } 

    int lhs = top(*s); 
    pop(s); 

    recursive_max_stack(s, num); 

    if (lhs > *num) 
     *num = lhs; 
} 

Erklärung

Zuerst müssen wir einen Standardfall (wenn es keine Elemente in dem Stapel). Genau wie Ihre iterative Funktion speichert der Standardfall als Ergebnis null.

if (emptyStack(*s)) 
{ 
    *num = 0; 
    return; 
} 

Also müssen wir den aktuellen Stack oben im aktuellen Rahmen sparen, dann, dass der Stapel Pop-off (denken Sie daran, wir halten es in einer lokalen Variablen):

lhs = top(*s); 
pop(s); 

Sobald das ist fertig, wir können rekrutieren.

recursive_max_stack(s, num); 

Wenn von der Rekursion der Rückkehr jedes lhs wird mit dem Inhalt des *num verglichen (die 0 eingestellt wurde, als man die maximale Tiefe Hit). Wenn größer, ersetzt lhs den unter *num gespeicherten Wert.

if (lhs > *num) 
    *num = lhs; 

Damit setzt sich der Call-Stack, wie wir Invokes entspannen, schließlich in die Anfangs invoke Rückkehr, dann mit dem Anrufer, mit *num jetzt, was die größte nicht-negativen Wert in dem Stapel halten war, oder Null, wenn alle Werte waren negativ (oder der Stapel war leer).

Das ist es. Es ist egal, welcher ursprüngliche Wert in *num gespeichert wurde. Es wird schließlich durch 0 bei Erreichen maximale Rekursionstiefe ersetzt, ersetzt dann wieder, wenn der nachfolgende Rahmen ein lhs Wert größer als der aktuelle gespeicherte Wert in *num

Answer 2

Das funktioniert, wenn der Stapel nicht leer ist, dann ruft er sich selbst weiter und übergibt den größten Wert weiter. Sobald der Stapel leer ist, werden die Funktionen nacheinander zurückgegeben, wobei der größte Wert durch den Zahlzeiger zurückgegeben wird.

Hier in Pseudo-Code:

void max_stack(stack *s, int * num){ 
    int aux = 0; 
    if(!emptyStack(*s)){ 
     aux = top(*s); 
     pop(s); 
     if (aux > (*num)){ 
      (*num) = aux; 
     } 
     max_stack(s, num); 
    } 
} 

Wenn er zum ersten Aufruf dieser Funktion können Sie es wie so nennen würde:

int num = 0 
max_stack(s, &num);