尾递归

递归很常用，但是很耗内存，因为需要存储临时变量，当递归次数多了，占据的内存数量惊人。

如下， 是阶乘的递归：

int function(n) {
    return n==1?1:function(n-1)*n;
}

  还有更好的递归算法，称为尾递归。这种方式不需要存储临时变量。因为是从erlang中学到的，所以先给出erlang的实现方法：

-module(test).
-export([fac/1]).
fac(N) -> fac_temp(N, 1).
fac_temp(1, X) -> X;
fac_temp(N, X) -> fac_temp(N - 1, N + X).

 C的版本如下：

int funcTemp(int num, int n) {//中间方法，多了个起始值             
  if(num<=1) return n;
  return funcTemp(num-1, n*num);
}
int func(int num) {//调用这个方法，默认起始值为1
    return funcTemp(num, 1);
}

 学习erlang的时候，学到了这个尾递归，很有收获。所以嘛，专精一门，广泛涉猎其他技术，非常有好处。

评论

1 楼 draem0507 2013-04-27  

nice。android的文章写的很棒。