函数式编程递归优化专题-TOC和Trampolines

递归

递归是FP中重要组成部分。递归的重点:

  • 基本条件,满足基本条件,递回停止,也可说是终止条件。
  • 若未满足,呼叫自己。
  • 每一次都逐渐往基本条件的方向收敛。

递归相较于迭代来说,代码更精简。递归是用代码去描述what,而迭代是用代码去描述how。例如对于斐波那契数列,两种写法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 递归解法
function fib(n) {
if (n <= 1) return n;
return fib( n - 2 ) + fib( n - 1 );
}

// 迭代解法
function fib (n) {
var r = 0, q = 1, p;

if (n <= 1) {
return n
} else {
for (let i = 2; i <= n; i++) {
p = r + q
r = q
q = p
}
return p
}
}

从JS引擎优化

递归调用可以不在本次宏任务中执行,而是放在下次宏任务/微任务中运行。可以考虑使用setTimeout或者Nodejs的nextTick

如何通过WebWorker与时间分片优化JS长任务? 也有参考意义,但是在generator函数中使用递归的效果还有待实验验证!

Tail Calls Optimizations(尾递归调用优化)

为什么会出现「爆栈」?

当递归层度增加,就可能会遇到「爆栈」的情况。为什么会出现「爆栈」的情况呢?

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

Untitled.png

当递归函数一直自我调用或者相互调用时,由于要保存回来的信息(调用帧),所以调用栈越来越大,当超过语言引擎的限制,就会抛出错误。

TCO实现流程

这时就需要使用尾递归进行优化,又简称TCO。尾递归调用是指函数最后返回的是函数的调用。这样就不需要保存调用位置、内部信息等调用帧。

对于阶乘函数来说,一个错误的TCO是:

1
2
3
4
5
6
7
function factorial (n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
// 错误原因:返回的有 n* ,那么就得用调用帧去记录这个信息,方便函数返回后,计算结果,因此无法进行tco

对于阶乘函数来说,一个正确的TCO是:

1
2
3
4
5
6
7
8
9
10
"use strict"; // es6 严格模式下才有尾递归调用优化
function factorial(n, partialFactorial = 1) {
// partialFactorial含义:之前乘积的值
if (n === 0) {
return partialFactorial
}
return factorial(n - 1, n * partialFactorial);
}
// 正确原因:只保留了一个调用记录,复杂度是O(1)。
// 底层引擎在解析+运行代码时,发现这里没有前面错误写法的 n* ,那么就不需要特殊保存调用帧。

Trampolines

TCO,为什么会称作优化呢?因为我当前的递回执行结束后,就不需要再回来,所以可以将stack frame移走,避免堆叠更多stack frame。

那如果引擎不支援TCO呢?有另外一种技巧叫做Trampolines,适合在没有TCO的环境使用。就是将递归转换为迭代。

Trampoline 是一个函数,具体是这样工作的:

  • 接受一个函数fn 当参数
  • call fn
  • 如果返回值是函数,就再call 得到返回值
  • 如果返回值不是函数,就直接返回

在这篇文章中,讲到了一个特别好的例子。可以根据这个例子,将一些符合TCO要求的递归函数,改写成迭代形式。

实现流程

step1:封装trampoline函数

1
2
3
4
5
6
7
8
9
10
function trampoline(fn) {
return function trampolined(...args){
var result = fn( ...args )
// 檢查返回結果的類型,當返回一個函數時,loop 繼續
while (typeof result === "function") {
result = result()
}
return result
}
}

step1:改写他们,让他们不再返回值,而是返回一个lazy模式的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
function toSteven(n) {
if (n === 0)
return 'boom!'
else
return () => toJob(Math.abs(n) - 1);
}

function toJob(n) {
if (n === 0)
return undefined
else
return () => toSteven(Math.abs(n) - 1);
}

两个没有经过TCO优化的互相递归调用函数(参数太大会爆栈):

1
2
3
4
5
6
7
8
9
10
11
12
13
function toSteven(n) {
if (n === 0)
return 'boom!'
else
return toJob(Math.abs(n) - 1);
}

function toJob(n) {
if (n === 0)
return undefined
else
return toSteven(Math.abs(n) - 1);
}

step3: 配合trampoline

1
2
var trampolined_toSteven = trampoline(toSteven)
var trampolined_toJob = trampoline(toJob)

step4: 见证效果

1
2
console.log(trampolined_toSteven(200000))// "boom!"
console.log(trampolined_toJob(3333333))// "boom!"

再举一个计算阶乘的例子:

1
2
3
4
5
6
function factorial(n, partialFactorial = 1) {
if (n === 0) {
return partialFactorial
}
return () => factorial(n - 1, n * partialFactorial);
}

参考

bookmark

bookmark

bookmark