小组PHP

尾递归很有意思~~~

拿快排说事的话,本来按照通俗易懂的理解,就是两次调用本身来进行左右排序。

按照尾递归的话得,可以省下一半的递归空间,直接拿一次的处理结果的low 或者high当参数传入下一次的调用。整个过程相比于同时进行两次本身的递归调用,这样只使用一次本身递归调用。

尾递归就是用迭代来代替递归全部过程。

递归调用会消耗大量的栈空间,每一次递归调用函数都会新开一个栈空间进行运行,同时要将上一次函数计算结果保存起来。所谓的保存现场,这样会消耗大量的栈空间。于是用迭代、用尾递归代替全递归调用就是一个很好的选择。

最常用距离都是斐波拉契数列,Feb(n) = n*(n-1)*(n-2)….2*1;

教科书就是用这个进行举例递归调用的。

这样就是一个递归调用的最经典的例子,不过在计算的过程中,每次调用的时候都得将上次计算的过程进行现场保存。所以当n很大的时候,这个n会占用很大的内存。

所以改用迭代的过程,或者尾递归的过程,即把每次的计算的结果存储起来同时传递给下一次函数得调用。

在快排改进排序中也是同样利用while迭代,来替代另外一次的递归调用。

突然发现一个问题,我原来混淆了斐波拉契数列。把n的阶乘当成斐波拉契数列数列啦。斐波拉契数列定义应该是Feb(n) = Feb(n-1)+Feb(n-2);

代码同理:

其实所谓尾递归,还是递归调用。但是内部就是用的所谓的迭代。其实可以用while循环来改写。将else部分替换成while的话,可能会更显而易见。

1 收藏


直接登录