26行代码讲清楚什么是尾递归

2018-12-16 07:38 来源:未知

  计算机专业本科的朋友在大二的专业课《数据结构》里想必都学过“递归”的概念。但是教材里并没有提到尾递归。而很多朋友在找程序员这份工作时,经常被面试官问起什么是尾递归。今天我们就说一说吧。如果一个函数中所有递归形式的调用都出现在函数的末尾,则该递归函数是尾递归的。为什么我们会强调尾递归?因为大多数现代的编译器会针对尾递归自动进行代码优化。新建一个txt文件,把下列代码拷贝进去,另存为html,用浏览器打开。

  注意看下图的Call Stack列表,此时我们已经有两个factorial函数的栈帧了。什么是栈帧?复习一下大学计算机原理学到的知识:因为在函数执行中,每一个函数调用都会把当前函数的调用位置和内部变量保存在栈里面,称为一个栈帧(Stack Frame)。

  其中最下面的保存了n=5的计算上下文,最顶层的代表当前栈帧,即n=4的计算上下文。

  递归调用自身,因为不知道5的阶乘怎么算,但是因为上面提到过,这个尾递归函数的第二个参数实际上存放的就是当前输入参数为n时的阶乘计算结果。尾递归的结束条件就是,当n为1时,返回这个阶乘计算结果。当n大于1时,首先将n和当前的阶乘计算结果相乘,结果作为输入参数传到递归调用的下一个栈帧中去。同时,因为当前参数n已经计算了一次乘法,因此我们需要把n减一。于是,才有了本文中尾递归函数的这个代码实现。

  注意看Jerry上面的这几个图里,tailFactorial都标注成useless(无用)。为什么呢?因为按照尾递归的阶乘计算公式,当前阶乘的计算结果已经通过第二个参数total保存了起来,因此没有必要再用一个栈帧去保存当前的计算上下文了。因此对于现代编译器,一旦检测到函数是尾调用调用后,编译器会进行代码优化,所以不再需要使用额外的栈帧保留每次递归调用记录,因为调用位置、中间计算结果,内部局部变量等信息都不再需要了。这就是所谓的“尾递归优化”可以有效防止栈溢出(stack overflow)。

  大家可以把我上面代码的N改为20,比较用普通阶乘递归函数和用尾递归函数计算20的阶乘,发现性能有巨大差异:前者需要10毫秒,后者仅需不到1毫秒!

  希望这26行代码能帮助大家理解尾递归和尾递归优化,在将来面试官问到这个话题时能从容应答。

TAG标签:
版权声明:转载须经版权人书面授权并注明来源