堆栈上的递归函数

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