我对使用堆栈将递归函数(尾函数和非尾函数)转换为迭代函数的一般方法的含义有很大的困惑。我举了一个简单的例子来说明这一点:
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创建第二个堆栈,但这可能如何工作?
2条答案
按热度按时间vm0i2vca1#
当你问一个问题时,一定要发布一个minimal, reproducible example。这有助于每个人理解问题,并生成和测试潜在的答案。
如果您创建了这样一个示例,那么很明显,迭代解决方案的版本1永远不会返回,而版本2总是返回0,这两个都不是正确性的好候选。
递归可能很有挑战性,但我认为我们可以在这个例子中介绍一种将递归函数转换为迭代函数的通用方法。
让我们看看
sigma1
的递归实现,在底层,调用这个函数会为每个递归调用生成一个新的堆栈帧(假设编译器没有优化它)。这些调用帧中的每一个都将具有该帧的参数
n
的值,该值将在递归的每一级减1。我们可以以同样的方式考虑迭代版本,将n
的值存储在显式的std::stack<int>
上,而不是由调用堆栈自动处理。当递归终止并且调用帧展开时,
n
的本地值被添加到前一个调用的结果中,从而创建要返回的新结果。以同样的方式,我们可以从显式std::stack<int>
中弹出值,并将它们添加到迭代版本中的运行总数中。这个函数看起来像这样
现在,在这个特定的场景中,您可以将两个循环简化为一个没有堆栈的迭代循环。当然,情况并非总是如此。
因为你没有发布一个完整的例子,所以我把你发布的代码改为使用
std::stack<int>
编译。我还为sigma1
和sigma2
添加了正确的迭代版本以及相应的输出。希望这对你有帮助。示例代码
输出
tcomlyy62#
如果你只是想优化你的特定函数,你可以使用公式:(n+1)*(n/2)
->
如果你只支持无符号数,我会这样声明你的函数。否则,您可能会遇到未定义的行为。