优化递归的效率zz

函数递归调用是很常见的做法，但是它往往是低效的，本文探讨优化递归效率的思路。

1.尾递归转换成迭代

尾递归是一种简单的递归，它可以用迭代来代替比如求阶乘函数的递归表达
intf(intn)

优化递归的效率zz {

if(n<=0)return1;

returnnf(n-1);

}
可以转换成完全等价的循环迭代
intf(intn)

{

intr=0;

while(n-->0)

r=n;

returnr;

}
尾递归是最简单的情形，好的编译器甚至可以自动的识别尾递归并把它转换成循环迭代。

2.动态规划

我一直把动态规划看作尾递归的推广（个人观点），在2维或更高的情况下，直接使用递归会造成大量的重复计算，例如在斐波那契数列的递归关系 Fib(n+2)=Fib(n+1)+Fib(n)中 Fib(3)在计算Fib(4)和Fib(5)都会用到他被重复计算了2遍，当数列长度增大时这种浪费会变得越来越明显。

动态规划方法将可能需要的结果全部计算出来并保存一般来说动态规划从最小数开始自底向上计算所有值（因为后面的结果会用到前面的结果）直到得到的结果中包含了要求的结果。
intFib(unsigned n)

优化递归的效率zz {

if(n==1)return1;

if(n==0)return0;

returnFib(n-1)+Fib(n-2);

}

intFib(unsigned n)

{

int*f=newint[n+1];

f[1]=1;f[0]=0;

for(inti=0;i<=n;i++);

f[i]=f[i-1]+f[i-2];

intr=f[n];

delete[] f;

returnr;

}
动态规划不会造成重复运算但是它可能计算不需要的结果例如关系式

a(n)=a(n-2)+a(n-4);

使用动态规划会计算很多不需要的结果，尽管如此，它的效率远远高于直接递归运算。

实际上，大部分时候动态规划把指数级时间复杂度的递归运算变成了多项式级时间复杂度的递推。

3.备忘录

减少重复值的另一个方法是使用备忘录，每次成功计算一个结果，就将它存入备忘录中，当再次遇到此问题时，无需重复计算，直接取出即可。

备忘录方法和直接递归相似，只是在函数在计算之前先访问备忘录，如果在备忘录中找到，就无须再计算，直接返回。

备忘录结构可以使用关联数组哈希表等实现，特别地，当递归参数是整数时直接用数组就可以了。

与动态规划相比，备忘录消耗了额外的备忘录查找时间，并且和直接递归一样有大量的多余函数调用开销，但它不会造成额外计算。

4.内联

这是来自Efficient C++的方法，C++编译器不会把递归函数内联，这样，函数调用的开销变得很大。为了提高效率，必须手动内联函数。

递归函数无法完全内联，但是我们可以把它展开，这是前面Fibnacci函数的一层展开
intFib(unsigned n)

优化递归的效率zz {

if(n==1)return1;

if(n==0)return0;

intfn1,fn2;

if(n-1==1)fn1=1;

elseif(n-1==0)fn1=0;

elsefn1=Fib(n-2)+Fib(n-3);

if(n-2==1)fn2=1;

elseif(n-2==0)fn2=0;

elsefn2=Fib(n-3)+Fib(n-4);

returnfn1+fn2

}
5.解递归

尽管我们倾向于虐待计算机让它帮我们处理较复杂的问题，但是很多时候我们需要获得效率，就必须自己动手，其实很多递归式可以手动解出，组合数学为我们提供了不少工具：

（１）解齐次递归方程

简单的递归方程可以按以下步骤求解：
解Fibonacci函数的递归方程优化递归的效率zz 首先把它转换成下面的式子这个代数方程被称为递归方程的特征方程，下一步是解特征方程求出它的所有解，对这个例子来说根据组合数学的结论再由F(0)=0和F(1)=1可以得出方程组解这个方程组可得到a和b的值代入前面的公式可以求出Fibnacci通项公式优化递归的效率zz 验证后可以知道，这个公式是正确的，显然用此公式做浮点运算，比使用递归方式快得多。（２）母函数组合数学中还提供了一种更强有力的处理手段：生成函数（又称为母函数）仍然以求解Fibonacci数列为例，为了易于理解，我这里把生成函数描述成一个以Fibonacci数列为系数的多项式。即优化递归的效率zz 现在考虑这样一个多项式按g(x)的定义，可以这样展开这个时候不要忘记我们的递推公式，可以进一步化简为这个式子与g(x)非常像，将它两边同时乘以x再整理一下等式利用F(0)=0,F(1)=1可以求出这样我们求出了g(x),等等,g(x)是什么来着？不是以Fibonacci数列为系数的多项式么？现在求出的东西是什么？不要急，用泰勒级数展开就能得到通项公式了，结果跟上面的是一样的。（太麻烦了，略过略过^_^）原文链接: https://www.cnblogs.com/end/archive/2011/09/15/2177805.html