C语言 关于使用堆栈将递归转换为迭代的混淆

qyuhtwio  于 2023-06-05  发布在  其他
关注(0)|答案(2)|浏览(128)

我对使用堆栈将递归函数(尾函数和非尾函数)转换为迭代函数的一般方法的含义有很大的困惑。我举了一个简单的例子来说明这一点:

int sigma1(int n) {
  if(n == 0) 
    return 0;
  else 
    return n + sigma1(n-1);
}

下列哪个版本正确反映了该方法:
第1版

int sigma1_iter(int n) {
  stack* s = create_stack(n);
  push(s, n);
  int res = 0;
  while(!is_empty(s)) {
    int elm = pop(s);
    if(elm == 0)
      return res;
    else {
      res += n;
      push(s, n-1);
    }
  }
}

第二版

int sigma1_iter(int n) {
  stack* s = create_stack(n);
  push(s, n);
  int res = 0;
  while(!is_empty(s)) {
    if (n > 0) {
      n--;
      push(s, n);
    }
    else {
      int elm = pop(s);
      if(elm == 0)
        return res;
      else {
        res += n;
    }
  }
}

此外,在具有累加器的sigma的尾部递归版本的情况下:

int sigma2(int n, int res) {
  if (n == 0) 
    return res;
  else
    return sigma2(n-1, n+res);
}

怎么转换呢?我正在考虑为res创建第二个堆栈,但这可能如何工作?

vm0i2vca

vm0i2vca1#

当你问一个问题时,一定要发布一个minimal, reproducible example。这有助于每个人理解问题,并生成和测试潜在的答案。
如果您创建了这样一个示例,那么很明显,迭代解决方案的版本1永远不会返回,而版本2总是返回0,这两个都不是正确性的好候选。
递归可能很有挑战性,但我认为我们可以在这个例子中介绍一种将递归函数转换为迭代函数的通用方法。
让我们看看sigma1的递归实现,

int sigma1(int n) {
    if (n == 0)
        return 0;
    else
        return n + sigma1(n - 1);
}

在底层,调用这个函数会为每个递归调用生成一个新的堆栈帧(假设编译器没有优化它)。这些调用帧中的每一个都将具有该帧的参数n的值,该值将在递归的每一级减1。我们可以以同样的方式考虑迭代版本,将n的值存储在显式的std::stack<int>上,而不是由调用堆栈自动处理。
当递归终止并且调用帧展开时,n的本地值被添加到前一个调用的结果中,从而创建要返回的新结果。以同样的方式,我们可以从显式std::stack<int>中弹出值,并将它们添加到迭代版本中的运行总数中。
这个函数看起来像这样

int sigma1_stack(int n) {
    std::stack<int> stack;
    for (int i = n; i > 0; --i)
        stack.push(i);

    int res{};
    while (not stack.empty()) {
        res += stack.top();
        stack.pop();
    }

    return res;
}

现在,在这个特定的场景中,您可以将两个循环简化为一个没有堆栈的迭代循环。当然,情况并非总是如此。

int sigma1_iter(int n) {
    int res{};
    for (int i = n; i > 0; --i)
        res += i;
    return res;
}

因为你没有发布一个完整的例子,所以我把你发布的代码改为使用std::stack<int>编译。我还为sigma1sigma2添加了正确的迭代版本以及相应的输出。希望这对你有帮助。

示例代码

#include <iostream>
#include <stack>

using std::cout, std::endl;

int sigma1(int n) {
    if (n == 0)
        return 0;
    else
        return n + sigma1(n - 1);
}

int sigma1_iter_v1(int n) {
    std::stack<int> stack;
    stack.push(n);

    int res = 0;
    while (not stack.empty()) {
        int elm = stack.top();
        stack.pop();
        if (elm == 0)
            return res;
        else {
            res += n;
            stack.push(n - 1);
        }
    }

    return res;
}

int sigma1_iter_v2(int n) {
    std::stack<int> stack;
    stack.push(n);

    int res = 0;
    while (not stack.empty()) {
        if (n > 0) {
            n--;
            stack.push(n);
        } else {
            int elm = stack.top();
            stack.pop();
            if(elm == 0)
                return res;
            else {
                res += n;
            }
        }
    }

    return res;
}

int sigma1_iter(int n) {
    int res{};
    for (int i = n; i > 0; --i)
        res += i;
    return res;
}

int sigma1_stack(int n) {
    std::stack<int> stack;
    for (int i = n; i > 0; --i)
        stack.push(i);

    int res{};
    while (not stack.empty()) {
        res += stack.top();
        stack.pop();
    }

    return res;
}

int sigma2(int n, int res = 0) {
    if (n == 0)
        return res;
    else
        return sigma2(n - 1, n + res);
}

int sigma2_iter(int n) {
    int res{};
    for (int i = n; i > 0; --i)
        res += i;
    return res;
}

int main(int argc, const char *argv[]) {
    cout << "sigma1         : " << sigma1(20) << endl;
    cout << "sigma1_iter   : " << sigma1_iter(20) << endl;
    cout << "sigma1_stack  : " << sigma1_stack(20) << endl;
    // This never returns
    // cout << "sigma1_iter_v1 : " << sigma1_iter_v1(20) << endl;
    cout << "sigma1_iter_v1 : " << "never returns" << endl;
    cout << "sigma1_iter_v2 : " << sigma1_iter_v2(20) << endl;

    cout << endl;
    cout << "sigma2         : " << sigma2(20) << endl;
    cout << "sigma2_iter    : " << sigma2_iter(20) << endl;
    return 0;
}

输出

sigma1         : 210
sigma1_iter    : 210
sigma1_stack   : 210
sigma1_iter_v1 : never returns
sigma1_iter_v2 : 0

sigma2         : 210
sigma2_iter    : 210
tcomlyy6

tcomlyy62#

如果你只是想优化你的特定函数,你可以使用公式:(n+1)*(n/2)
->

unsigned int sigma1(unsigned int n) {
  return (n+1) * (n/2);
}

unsigned int sigma2(unsigned int n, unsigned int res) {
  return (n+1) * (n/2) + res;
}

如果你只支持无符号数,我会这样声明你的函数。否则,您可能会遇到未定义的行为。

相关问题