递归计算向非递归计算转换模板

递归修改成迭代是不错的教材。

可是没很大实用性，因为瓶颈是递归算法的情况不很多，我们还可以把包含很多局部变量的代码段抽出成函数，还可以增加栈空间。

当然模版化的修改方法也不错，让机器完成这类工作，就更加不需要手动把递归改成非递归了。

建议不用在这种问题上纠结，因为太机械，这两算法本质上没什么区别。

像lisp就没有迭代，只有递归~~

如果你的算法会造成递归栈溢出，改成非递归以后很可能也会堆溢出-_-。




ps1：

递归与迭代的区别，其实是差分方程反向和正向递推的区别，也是归纳和演绎的区别。


ps2：

一些不需要栈就能改写的例子：

如f(n) = f(n-1) + f(n-2)

从n开始算就是递归，从2开始算就是迭代，这种转化连栈都不需要。


又如f(n) = f(n/2) + f(n/4)

我们可以设g(n) = g(n-1)/2

f*g(n) = f*g(n-1) + f*g(n-2)

设f' = f*g，则f = f'* g^-1

f'(n) = f'(n-1) + f'(n-2)

同样也不需要栈。


如果f(x)满足： 对任意a, f(a)==f(a)，

那么我们可以：写出对应的差分方程，求出差分方程的通解，将f改写成通解。

这样也不需要栈。


一些递归可以在编译期完成，c++的expression template，

这样运行时也不需要栈。