主要是为了回复 Zeds 简单递归......
为什么假定递归比迭代更好?尤其是在 C++ 中。有什么问题...
int myPow (int x, int p) {
int i = 1;
for (int j = 1; j <= p; j++) i *= x;
return i;
}
我并不是说你的答案是错误的或者更糟——只是我觉得你认为它很好,因为它是递归的。IMO,尤其是在 C++ 中,这种偏见会导致程序运行缓慢甚至损坏。缓慢的程序,因为你正在增长一个巨大的堆栈,导致缓存和虚拟内存分页。程序损坏,因为在迭代解决方案可以工作的地方出现堆栈溢出。
有些人会查看您的答案并认为它是尾递归的,并且无论如何都会被优化为迭代。当然这不是真的——在每个递归调用退出后,还有一个乘法要做,所以它不是尾递归。问题是,在 C++ 中,有很多更微妙的东西可以防止尾递归优化——即使编译器完全这样做了。例如...
void myrecurse (plan *p)
{
plan i;
i.prev = p;
// more plan setup, checks, and special case handling
myrecurse (&i);
}
在这种情况下,所有“计划”实例必须保留在堆栈中。因此,堆栈帧不能被丢弃。因此,这在迭代中是不可优化的,即使在递归调用之后执行的操作恰好为零。甚至没有像析构函数清理这样的隐藏操作,因为 plan 被假定为 POD 结构。
顺便说一句,这是基于我在真实代码中所做的事情 - 在递归期间计划的数据结构操作,但在递归到达根/叶之前,原始节点中没有任何变化,所有需要的新节点都已成功分配,获得所有锁,并且没有更糟的破坏。那时,通过计划实例的链接列表完成迭代以提交更改 - 作为迭代的逻辑比分解为与递归调用的展开相关的片段更清晰。
这里的重点显然不是声称递归是自动坏的。当人们似乎默认递归比迭代更好时,这让我感到紧张。