javascript递归,tco和trampoline

Javascript 的递归问题

对于经典递归问题-求 n 的阶乘,实现如下:

function fact(n) {
  if (n == 0) return 1;
  return n * fact(n - 1);
}
console.log(fact(100000));

在 nodejs 里运行,其结果是–报错 Maximum call stack size exceeded。栈溢出了!

真是弱爆了,这样就不行了。然而实际上,往往需要解决递归带来的这种问题。怎么办?

Tail Call Optimization(TOC 尾调用优化)

尾调用优化是指编译器将尾递归优化为循环(后面 Trampoline 会讲到)。

什么是尾递归?

尾递归,简而言之,是最后一个操作一定是调用自己的递归。

function fact(n, acc) {
  if (n == 0) return acc;
  //最后一个操作是调用自身
  return fact(n - 1, acc * n);
}

TOC 的问题

这样就解决了问题吗?—— 没有! 因为 TOC 实现的问题。

TOC 是 ES6 的一部分但是完全没实现

这里看,node8 之前是支持 TOC 的,要通过(–harmony node > 6.6.0 , –harmony_tailcalls node < 6.6.0 ),但是 node8 反而不支持了。

Trampoline

既然 TOC 不靠谱,最好还是靠自己动手。理论上,递归都可以转换为循环,术语 Trampoline(原意蹦床) 就是以这样的思路来解决问题。让人高兴的是,javascript 的语言特性完全支持此实现。

其解决方法是递归函数返回要么是个值,要么是个函数,避免实际执行代码不断增加调用栈。这样,持续调用递归函数的话,会不断的得到函数,调用它,代码是一个循环结构而不是递归结构直至获得值。

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);

    //循环结构
    while (result) {
      if (typeof result === 'function') {
        //调用递归函数,如果返回的事函数,下次继续执行
        result = result();
      } else {
        //如果是值则结束并返回
        break;
      }
    }

    return result;
  };
}

// 使用
// 递归函数
function fact3(n, acc = 1) {
  // 返回要么是值要么是函数
  return n > 0 ? () => fact3(n - 1, n * acc) : acc;
}

//
const funcTramp = trampoline(fact3);
//执行成功,可调试看到调用栈固定<20
const result = funcTramp(100000);

改进

Trampoline 的最终目的是将递归转为循环,改成循环的诀窍是,代码不马上执行,而是返回函数。那么 promise 也可以达到相同的目的。

export function trampoline(fn) {
  //加async,返回的是promise
  return async function(...args) {
    let result = fn(...args);

    while (result) {
      if (typeof result.then === 'function') {
        // 如果递归函数返回的是promise,则执行promise
        result = await result;
      } else if (typeof result === 'function') {
        result = result();
      } else {
        break;
      }
    }

    return result;
  };
}

async function fact4(n, acc = 1) {
  // 返回async函数(promise)或者值
  return n > 0 ? async () => await fact4(n - 1, n * acc) : acc;
}

//调用
const funcTramp2 = trampoline(fact4);
const result2 = await funcTramp2(number);
//promise适用于websocket重连等场景。

完整代码示例参见 github


Total views.

© 2013 - 2019. All rights reserved.

Powered by Hydejack v6.6.1