个人理解:尾调用与递归

尾调用就是指某个函数的最后一步是调用另一个函数。尾递归就是尾调用自身。

相信大家都看过阮老师的这篇文章《尾调用优化》

他是说，函数调用会在内存形成一个”调用记录”，又称”调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用记录上方，还会形成一个B的调用记录。等到B运行结束，将结果返回到A，B的调用记录才会消失。如果函数B内部还调用函数C，那就还有一个C的调用记录栈，以此类推。所有的调用记录，就形成一个”调用栈”（call stack）。

先要特别注意阮老师那个例子：

function f(x){

return g(x) + 1;

}这样子也不是

这理解起来也不难。但是个人还有一种方法理解：

正常递归（非尾递归，尾部调用非自身）

function f(n){

return g(f(n-1))

}

用数学公式的角度就是f（x）=g（f（x-1））

假设函数内部的关系用g表示（加减乘除幂对数赋值等等），对于函数f的n次递归，正常的递归就是f（n）=g(f（n-1）)=g(g(f(n-2)))=…=g(g(g(…..g(f(1))))),里面要嵌套n个g，复杂度O（n）

尾递归（尾部调用自身，没毛病，return就是f自己）

function f(n){

return f（n-1）

}

f（n）=f（n-1）=…=f（1）

复杂度就是O（1）

对于阶乘、斐波那契数列那些，主要是难在把他转换成f（n）=f（n-1）形式（例子网上多着，不列举了）。而不懂行的人看起来，有没有尾部递归也不是一眼秒看出来的