堆棧上的遞歸函數

Question

我有一個非常簡單的函數來找出一堆整數的最大非負值。我想將此函數轉換爲遞歸函數。 有幾點要記住：

• 運行功能之前，我們已經初始化num，但還沒有分配任何價值了。並請，我們不應該依賴於一個事實，即C的溫度將自動在一定條件下分配0至num
• 運行函數的棧s爲空後，我們必須存儲在num
• 我的最大非負值 「M C和數據結構是初學者，所以請好:)

這是迭代函數：

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

要匹配正是迭代代碼提供，我們也必須匹配假設即使在空堆棧上，0也是存儲在目標參數中的最小值。

隨着指出：

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; 
} 

說明

首先，我們需要一個默認的情況下（當有在堆棧中沒有元素）。就像您的迭代函數一樣，默認情況下存儲爲零。

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

所以我們需要保存關閉當前堆棧頂部的當前幀，然後彈出的是從堆棧（請記住，我們把它放在一個局部變量）：

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

一旦這個完成後，我們可以遞歸。

recursive_max_stack(s, num); 

當從遞歸返回時，每個lhs與的*num內容（將其設定爲0當我們擊中最大深度）進行比較。如果更大，則lhs將替換存儲在*num處的值。

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

這將繼續調用堆棧，因爲我們放鬆所調用，最後返回到初始調用，然後給調用者，用*num現在持有任何在堆棧中的最大的非負值是，或零，如果所有值爲負值（或堆棧爲空）。

就是這樣。這不關心在*num中存儲了什麼原始值。它最終被0在達到最大遞歸深度更換，然後再更換每當隨後幀具有lhs值比*num

Answer 2

這將工作的方式是，如果堆棧不是空的，那麼它會繼續調用自己傳遞的最大值。一旦堆棧爲空，函數將逐個返回，通過num指針返回最大值;

在這裏，在僞代碼：

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); 
    } 
} 

當第一次調用此函數就叫做像這樣：

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