问：某人登泰山,此人一步可登一个台阶,也可以一步登两个台阶,问他登上1000个台阶的方式有几种?为什么?

显然,登上1级台阶只有一种方法；
登上2级台阶有两种方法；
登上3级台阶有两种考虑方法,先登上一级台阶,剩下的同2级台阶情形,或先登上2级台阶,剩下的同1级台阶情况,故有1＋2＝3种；
登上4级台阶也可仿上面考虑,先登一级,剩下的3级变成上面的情况,或先登2级,剩下的变成登2级台阶的情形,故有3＋2＝5种
类似地,
登上5级台阶的情况相当于一个登4级台阶情形和一个登3级台阶情形,即有：5＋3＝8种
登上6级台阶的情况相当于一个登5级台阶情形和一个登4级台阶情形,即有：8＋5＝13种
.
依此类推
登n级的情况可以转化成登n－1级台阶和n－2级台阶情形
化为公式：f(n)=f(n-1)+f(n-2)

代码如下

  1. function fibonacci(n) {
  2.   if (n <= 1) {
  3.     return 1
  4.   }
  5.   return fibonacci(n - 1) + fibonacci(n - 2)
  6. }

递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）
在使用递归的时候我们通常使用尾调用优化递归，尾递归优化

什么是尾调用？

尾调用（Tail Call）是函数式编程的一个重要概念，本身非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。

  1. function f(x){
  2.   return g(x);
  3. }

上面代码中，函数f的最后一步是调用函数g，这就叫尾调用。
以下三种情况，都不属于尾调用。

  1. // 情况一
  2. function f(x){
  3.   let y = g(x);
  4.   return y;
  5. }
  6. // 情况二
  7. function f(x){
  8.   return g(x) + 1;
  9. }
  10. // 情况三
  11. function f(x){
  12.   g(x);
  13. }

上面代码中，情况一是调用函数g之后，还有赋值操作，所以不属于尾调用，即使语义完全一样。情况二也属于调用后还有操作，即使写在一行内。情况三等同于下面的代码。

  1. function f(x){
  2.   g(x);
  3.   return undefined;
  4. }

尾调用不一定出现在函数尾部，只要是最后一步操作即可。

  1. function f(x) {
  2.   if (x > 0) {
  3.     return m(x)
  4.   }
  5.   return n(x);
  6. }

上面代码中，函数m和n都属于尾调用，因为它们都是函数f的最后一步操作。

尾调用优化

尾调用之所以与其他调用不同，就在于它的特殊的调用位置。

我们知道，函数调用会在内存形成一个“调用记录”，又称“调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧。等到B运行结束，将结果返回到A，B的调用帧才会消失。如果函数B内部还调用函数C，那就还有一个C的调用帧，以此类推。所有的调用帧，就形成一个“调用栈”（call stack）。
image.png
尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了。

  1. function f() {
  2.   let m = 1;
  3.   let n = 2;
  4.   return g(m + n);
  5. }
  6. f();
  7. // 等同于
  8. function f() {
  9.   return g(3);
  10. }
  11. f();
  12. // 等同于
  13. g(3);

上面代码中，如果函数g不是尾调用，函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后，函数f就结束了，所以执行到最后一步，完全可以删除f(x)的调用帧，只保留g(3)的调用帧。
这就叫做“尾调用优化”（Tail call optimization），即只保留内层函数的调用帧。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用帧只有一项，这将大大节省内存。这就是“尾调用优化”的意义。
注意，只有不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则就无法进行“尾调用优化”。

  1. function addOne(a){
  2.   var one = 1;
  3.   function inner(b){
  4.     return b + one;
  5.   }
  6.   return inner(a);
  7. }

上面的函数不会进行尾调用优化，因为内层函数inner用到了外层函数addOne的内部变量one。
注意，目前只有 Safari 浏览器支持尾调用优化，Chrome 和 Firefox 都不支持, VScode的debugger也不支持。

尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。
递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。

  1. function factorial(n) {
  2.   if (n === 1) return 1;
  3.   return n * factorial(n - 1);
  4. }
  5. factorial(5) // 120

上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度 O(n) 。
如果改写成尾递归，只保留一个调用记录，复杂度 O(1) 。

  1. function factorial(n, total) {
  2.   if (n === 1) return total;
  3.   return factorial(n - 1, n * total);
  4. }
  5. factorial(5, 1) // 120

还有一个比较著名的例子，就是计算 Fibonacci 数列，也能充分说明尾递归优化的重要性。

  1.  console.time('fibonacci');
  2.     function fibonacci(n) {
  3.       if (n <= 1) {
  4.         return 1
  5.       }
  6.       return fibonacci(n - 1) + fibonacci(n - 2)
  7.     }
  8.     fibonacci(30)
  9.     console.timeEnd('fibonacci');
  11.     console.time('fibonacci2');
  12.     function fibonacci2(n, ac1 = 1, ac2 = 1) {
  13.       if (n <= 1) {
  14.         return ac2
  15.       };
  16.       return fibonacci2(n - 1, ac2, ac1 + ac2);
  17.     }
  18.     fibonacci2(30)
  19.     console.timeEnd('fibonacci2');

这个fibonacci2很好理解，用循环很容易做出一个
就是后一个数是前两个数之和

  1.   function fibonacci3(n) {
  2.       let ac1 = 1, ac2 = 1;
  3.       for (let i = 2; i <= n; i++) {
  4.         [ac1, ac2] = [ac2, ac1 + ac2];
  5.       }
  6.       return ac2;
  7.     }

image.png

image.png

应该影响的主要是空间复杂度，速度差异主要是fibonacci1递归了两个fibonacci1

在chrome中尾调用还没有支持，所以说现在尾调用优化还没有卵用
image.png