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

1、尾递归转换成迭代

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

int f( int n)

{

if(n<=0)return 1;

return n*f(n-1);

}

可以转换成完全等价的循环迭代

int f( int n)

{

int r=0;

while(n-->0)

r*=n;

return r;

}

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

2、动态规划

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

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

int Fib(unsigned n)

{

if(n==1)return 1;

if(n==0)return 0;

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

}

int Fib(unsigned n)

{

int* f=new int[n+1];

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

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

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

int r=f[n];

delete[] f;

return r;

}

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

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

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

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

3、备忘录

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

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

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

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

4、内联

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

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

int Fib(unsigned n)

{

if(n==1)return 1;

if(n==0)return 0;

int fn1,fn2;

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

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

else fn1=Fib(n-2)+Fib(n-3);

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

else if(n-2==0)fn2=0;

else fn2=Fib(n-3)+Fib(n-4);

return fn1+fn2

}

5、解递归

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

(１)解齐次递归方程

简单的递归方程可以按以下步骤求解：

解Fibonacci函数的递归方程

首先把它转换成下面的式子

这个代数方程被称为递归方程的特征方程，下一步是解特征方程求出它的所有解，对这个例子来说

根据组合数学的结论

再由

F(0)=0和F(1)=1可以得出方程组

解这个方程组可得到a和b的值

代入前面的公式可以求出Fibnacci通项公式

验证后可以知道，这个公式是正确的，显然用此公式做浮点运算，比使用递归方式快得多。

(２)母函数

组合数学中还提供了一种更强有力的处理手段：生成函数(又称为母函数)

仍然以求解Fibonacci数列为例，为了易于理解，我这里把生成函数描述成一个以Fibonacci数列为系数的多项式。即

现在考虑这样一个多项式

按g(x)的定义，可以这样展开

这个时候不要忘记我们的递推公式，可以进一步化简为

这个式子与g(x)非常像，将它两边同时乘以x

再整理一下等式

利用F(0)=0,F(1)=1可以求出

这样 我们求出了g(x),等等,g(x)是什么来着？不是以Fibonacci数列为系数的多项式么？现在求出的东西是什么？不要急，用泰勒级数展开就能得到通项公式了，结果跟上面的是一样的。(太麻烦了，略过略过^_^)

https://www.cnblogs.com/end/category/82543.html

packagecom.changhong.csc.ie.mdm.test.org;importjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importcom.alibaba.fastjson.JSON;public classTreeTest {privateInteger id;privateInteger pId;privateString name;private Listchildren;publicTreeTest() {

}publicTreeTest(Integer id, Integer pId, String name) {super();this.id =id;this.pId =pId;this.name =name;

}publicInteger getId() {returnid;

}public voidsetId(Integer id) {this.id =id;

}publicInteger getpId() {returnpId;

}public voidsetpId(Integer pId) {this.pId =pId;

}publicString getName() {returnname;

}public voidsetName(String name) {this.name =name;

}public ListgetChildren() {returnchildren;

}public void setChildren(Listchildren) {this.children =children;

}

@OverridepublicString toString() {return "TreeTest [id=" + id + ", pId=" + pId + ", name=" +name+ ", children=" + children + "]";

}//测试数据

public static voidmain(String[] args) {

List list = new ArrayList();

Map map = new HashMap();

TreeTest terr1= new TreeTest(1, 0, "一级父节点");

TreeTest terr2= new TreeTest(2, 1, "一级1子节点");

TreeTest terr3= new TreeTest(3, 2, "一级2子节点");

TreeTest terr4= new TreeTest(4, 0, "二级父节点");

TreeTest terr5= new TreeTest(5, 4, "二级1子节点");

TreeTest terr6= new TreeTest(6, 4, "二级1子节点2");

TreeTest terr7= new TreeTest(7, 3, "一级3子节点");

TreeTest terr8= new TreeTest(8, 5, "二级2子节点");

map.put(terr1.getId(), terr1);

map.put(terr2.getId(), terr2);

map.put(terr3.getId(), terr3);

map.put(terr4.getId(), terr4);

map.put(terr5.getId(), terr5);

map.put(terr6.getId(), terr6);

map.put(terr7.getId(), terr7);

map.put(terr8.getId(), terr8);/** List li = getChildren(map,0,1);

*

* System.out.println(JSON.toJSON(li));*/Map> treemap = new HashMap>();for(TreeTest treeTest : map.values()) {

List listTree =treemap.get(treeTest.getpId());if (listTree == null) {

listTree= new ArrayList();

listTree.add(treeTest);

treemap.put(treeTest.getpId(), listTree);

}else{

List ordTree =treemap.get(treeTest.getpId());

ordTree.add(treeTest);

treemap.put(treeTest.getpId(), ordTree);

}

}

List lists = new ArrayList();

lists.add(terr1);

List li =getChildren(lists, treemap);

System.out.println(JSON.toJSON(li));

}//递归树

public static List getChildren(Listtrees,

Map>children) {

List childrenTree = null;for(TreeTest tree : trees) {//获得子节点

childrenTree =children.get(tree.getId());if (childrenTree != null) {//添加子节点

tree.setChildren(childrenTree);//递归

getChildren(tree.getChildren(), children);

}

}returnchildrenTree;

}

}