乐趣区

关于javascript:尾调用

jiezi

一、尾调用

1、概念

在函数的最初一个调用其余函数，则是尾调用

function a(x) {return b(x)
}

2、辨别尾调用

// 这两种状况不属于尾调用
// return 语句不能蕴含表达式
function a(x) {return b(x) + 1
}

function a(x) {let y = b(x)
    return y
}
function a(x) {b(x)
    // return undefined
}

// 尾调用也不肯定是在函数尾部，次要是函数最初一步操作就可
function a(x) {if (x > 1) {return m(x)
    }
    return n(x)
}

3、尾调用优化

函数调用会有一个“调用记录”，也称为 “调用帧”，用于保留调用地位和外部变量等信息。
如函数 A 里调用了函数 B，则 A 的调用记录上会记录 B 的调用记录，期待 B 执行结束后将后果给 A，B 才会隐没。如果函数 B 调用了函数 C，也会生成一个 C 的调用记录，以此类推，所有的记录就造成了“调用栈”。

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

// 等同于
function f() {return g(3);
}
f();

// 等同于
g(3);

下面代码中，如果函数 g 不是尾调用，函数 f 就须要保留外部变量 m 和 n 的值、g 的调用地位等信息。但因为调用 g 之后，函数 f 就完结了，所以执行到最初一步，齐全能够删除 f() 的调用记录，只保留 g(3) 的调用记录。

只有不再用到外层函数的外部变量，内层函数的调用帧才会取代外层函数的调用帧，否则就无奈进行“尾调用优化”。

这就叫做 ” 尾调用优化 ”（Tail call optimization），即只保留内层函数的调用记录。如果所有函数都是尾调用，那么齐全能够做到每次执行时，调用记录只有一项，这将大大节俭内存。这就是 ” 尾调用优化 ” 的意义。

留神，目前只有 Safari 浏览器反对尾调用优化，Chrome 和 Firefox 都不反对

二、尾递归

1、一般递归

概念：函数外部调用本身
解决的问题：
① 数据的定义是按递归进行的（阶乘）
② 问题的解法按递归实现（回溯）
③ 数据的构造依照递归定义的（树形构造、二叉树）

毛病：运行效率低、容易造成栈溢出

2、尾递归

概念：尾调用本身，就称为尾递归

递归很耗内存，每次调用都会保留所有的调用记录，容易产生栈溢出谬误。但对于尾调用来说
每次都只存在一个调用记录，就不会产生栈溢出，绝对节俭内存，优化了性能。

（1）实现阶乘

递归实现：

function factorial(n) {if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

调用模式：factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
...
// 计算阶乘的时候，须要保留 n 个调用记录，复杂度为 O（n）// 执行多层时会呈现栈溢出

尾调用递归实现：

function factorial(n, total) {if (n === 1) return total;
  return factorial(n-1, n*total);
}

factorial(5, 1) // 120

调用模式：factorial(5, 1)
factorial(4, 5)
factorial(3, 20)
...
// 尾递归则保留一个记录，复杂度为 O（1）

执行阶乘函数 factorial(5, 1)时，当调用栈次数过多，调用堆栈会始终增长，直到达到限度：浏览器硬编码堆栈大小或内存耗尽。会产生 超出最大调用堆栈大小“Maximum call stack size exceeded”，

还可通过斐波那契数列，能够体现到尾递归的重要性

（2）斐波那契数列

一般递归：

function feibonaqi(n) {if (n <= 1) return 1;
     return feibonaqi(n-1) + feibonaqi(n-2);
}

feibonaqi(10)  //89
feibonaqi(20)  // 报错

尾递归：

function feibonaqi(n, a1 = 1, a2 = 1) {if (n <= 1) return a2;
     return feibonaqi(n-1, a2, a1+a2);
}

feibonaqi(10)  //89
feibonaqi(20) // 10946

3、函数递归的改写

尾递归的实现，须要改写递归函数，确保是函数最初一步调用本身。须要把用到的外部变量变成函数的参数。

下面例子中，阶乘函数 factorial 应用了一个两头变量 total，在进行阶乘时将 total 作为函数的参数。在初始时，传入了 5 和 1 两个参数，可能第一次不太直观看懂

有两种办法能够解决

办法一：
在尾递归函数之外，在提供另一个函数

function tailFactorial(n, total) {if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

function factorial(n) {return tailFactorial(n, 1);
}

factorial(5) // 120

函数式编程有一个办法 --“函数式柯里化”，将多参函数转成单参函数

尾递归之所以须要优化，起因是调用栈太多，造成溢出，那么只有缩小调用栈，就不会溢出。

办法二：
应用 ES6 函数默认值

function tailFactorial(n, total = 1) {if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

factorial(5) // 120

三、函数柯里化

函数柯里化就是把一个多参函数转成单参函数

// 柯里化前 - 一般相加函数
function sum(x, y) {return x + y;}

factorial(2，3) // 5

// 柯里化
function sum(x) {return function(y) {return x + y;}
}

// 箭头函数
const add = a => b => a + b;

sun(2)(3)

// const f = sum(1)
// f(2)

尾递归阶乘函数应用柯里化，将多参转成单参函数

function currying(fn, n) {return function (m) {return fn.call(this, m, n);// 绑定 this
  };
}

function tailFactorial(n, total) {if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

四、严格模式

ES6 的尾调用优化只在严格模式下开启，失常模式是有效的。

这是因为在失常模式下，函数外部有两个变量，能够跟踪函数的调用栈。

arguments：返回调用时函数的参数。
func.caller：返回调用以后函数的那个函数。

尾调用优化产生时，函数的调用栈会改写，因而下面两个变量就会失真。严格模式禁用这两个变量，所以尾调用模式仅在严格模式下失效。

退出移动版