计算机中的黑魔法:尾递归(4)

虽然两者都在定义过程的时候调用了自身,但是很显然,迭代的定义过程属于用递归的方式定义过程。递归属于递归计算进程。

黑魔法终极奥义:尾递归

一般的编程语言都是通过循环等一些复杂的结构来描述迭代的,但是在scheme中却可以用递归的形式来描述迭代。

观察上面两个求阶乘的过程,我们可以看到。虽然两者都是调用了自身,用了递归的形式来定义整个过程,表面上都属于递归调用,但是,『递归』版本中,在最后的递归调用之后,还需要进行乘n的操作才算作是完成了此次计算,而在 [迭代]版本中,递归的调用属于最后一个方法,末尾的递归调用执行完,此次的计算也就执行完了,属于该过程的最后一个操作,这就是”尾递归”。尾递归相对于正常的递归来说,它的递归调用处于过程最后,之前过程计算积累的信息对于接下来的这次递归调用的最终结果没有任何影响,那么本次过程调用存储在栈内的信息就可以完全清除。把空间留给之后的递归过程使用。所以说,这意味着如果使用尾递归的方式,是可以实现无限递归的。

尾递归的本质,其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。这样上一次的调用就不用再保存一些额外的信息,并且在计算到边界的时候,因为计算的结果一直在累积,所以计算到终点的时候,也就得到的最后的结果,可以直接返回给最开始调用这个方法的调用者。

至于把正常递归转化为尾递归的方法,我觉得比较直接的做法就是,正常递归是从后向前考虑,如果写尾递归,那么就把问题从前向后考虑,并且把所需的信息当做参数传递。

一般来讲,虽然在过程定义上,看起来是递归的,但是实际的计算进程的原理有可能是迭代的,也有可能是递归的,因为,迭代的计算是可以用尾递归来进行定义的。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/c6b66c1476bb1e840ad5167de46e6595.html