[原]关于线性递归与尾递归

长平狐 发布于 2012/11/14 12:20
阅读 162
收藏 0

作为读书笔记使用:

线性递归:

1 fac(0) -> 1 ; 2 fac(N) -> N*fac(N-1).

尾递归:

1 fac(0,Sum) -> 2 Sum; 3 fac(N,Sum) -> 4 fac(N-1,Sum*N).

尾递归定义:

函数最后一步调用自身,即最后一行代码一定是对于自己的一个递归调用。

Erlang尾递归这样带来的好处是可以让编译器做到将递归优化,转化为跳转指令而不是,可以防止栈空间爆炸。

 

尾递归通常的做法是将中间状态加入到参数中,还可以防止共享变量的问题。这也是传说中的中间状态

python中对于尾递归的优化我还不得而知,Erlang对于线性递归做到了一定的优化,GCC也可以。

想去买一本《递归可枚举度与图灵度》


原文链接:http://www.cnblogs.com/Bozh/archive/2012/06/13/2548358.html
加载中
返回顶部
顶部