尾叫优化递归函数

Question

这是一个深扁平数组的函数。

const deepFlatten = (input) => {
  let result = [];
  input.forEach((val, index) => {
    if (Array.isArray(val)) {
      result.push(...deepFlatten(val));
    } else {
      result.push(val);
    }
  });
  return result;
};

在一次讨论中，我被告知内存效率不高，因为它可能会导致堆栈溢出。

我在http://2ality.com/2015/06/tail-call-optimization.html上读到，我可能会重写它，以便它是TCO编辑的。

这看起来会是什么样子，我如何测量它的内存使用情况？

Answer 1

当递归调用在forEach中时，您无法优化它，因为为了应用TCO，编译器需要检查是否保存了前一个调用的“状态”。对于forEach，您确实保存了当前位置的“状态”。

为了用TCO实现它，您可以重写要用递归调用实现的foreach，它看起来如下所示：

​

function deepFlattenTCO(input) {
  const helper = (first, rest, result) => {
    if (!Array.isArray(first)) {
      result.push(first);
      if (rest.length > 0) {
        return helper(rest, [], result);
      } else {
        return result;
      }
    } else {
      const [newFirst, ...newRest] = first.concat(rest);

      return helper(newFirst, newRest, result);
    }
  };

  return helper(input, [], []);
}

console.log(deepFlattenTCO([
  [1], 2, [3], 4, [5, 6, [7]]
]));

​

您可以看到，在每个return中，执行的唯一操作是递归调用，因此不保存递归调用之间的“状态”，因此编译器将应用优化。

Answer 2

一般的尾调用()

我已经得到了共享另一种在JavaScript中扁平数组的功能方法；我认为这个答案显示了解决这个特定问题的更好的方法，但是并不是所有的函数都可以很好地分解。这个答案将集中于递归函数中的尾调用，以及一般的尾调用。

通常，要将循环调用移动到尾位置，将创建一个辅助函数(以下为aux)，其中函数的参数保持完成计算步骤所需的所有状态。

​

const flattenDeep = arr =>
  {
    const aux = (acc, [x,...xs]) =>
      x === undefined
        ? acc
        : Array.isArray (x)
          ? aux (acc, x.concat (xs))
          : aux (acc.concat (x), xs)
    return aux ([], arr)
  }
        
const data = 
  [0, [1, [2, 3, 4], 5, 6], [7, 8, [9]]]
  
console.log (flattenDeep (data))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

​

js实际上没有尾部调用消除

但是，大多数JavaScript实现仍然不支持尾调用--如果您想在程序中使用递归而不担心引发堆栈- 这也是我已经写了很多的东西，则必须以不同的方式处理这个问题。

我目前使用的是clojure样式的loop/recur对，因为它在提供堆栈安全性的同时，还提供了使用漂亮的纯表达式编写程序的功能。

​

const recur = (...values) =>
  ({ type: recur, values })
  
const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.values)
    return acc
  }
  
const flattenDeep = arr =>
  loop ((acc = [], [x,...xs] = arr) =>
    x === undefined
      ? acc
      : Array.isArray (x)
        ? recur (acc, x.concat (xs))
        : recur (acc.concat (x), xs))
        
let data = []
for (let i = 2e4; i>0; i--)
  data = [i, data]

// data is nested 20,000 levels deep
// data = [1, [2, [3, [4, ... [20000, []]]]]] ...

// stack-safe !
console.log (flattenDeep (data))
// [ 1, 2, 3, 4, ... 20000 ]

​

一个重要的职位

为什么尾巴位置这么重要？你想过那个return关键字吗？这就是函数的出路；在像JavaScript这样经过严格评估的语言中，return <expr>意味着在发送结果之前，expr中的所有内容都需要计算。

如果expr包含一个带有不位于尾位置的函数调用的子表达式，这些调用将引入一个新框架，计算一个中间值，然后将其返回到尾调用的调用框架--这就是为什么如果无法确定何时可以安全地删除堆栈帧，堆栈就会溢出。

无论如何，很难谈论编程，所以希望这个小草图有助于识别一些常见函数中的调用位置

​

const add = (x,y) =>
  // + is in tail position
  x + y

const sq = x =>
  // * is in tail position
  x * x
  
const sqrt = x =>
  // Math.sqrt is in tail position
  Math.sqrt (x)

const pythag = (a,b) =>
  // sqrt is in tail position
  // sq(a) and sq(b) must *return* to compute add
  // add must *return* to compute sqrt
  sqrt (add (sq (a), sq (b)))

// console.log displays the correct value becaust pythag *returns* it
console.log (pythag (3,4)) // 5

​

现在假设没有返回值，因为函数无法将值发送回调用方，当然，我们可以很容易地推断，在对函数进行评估之后，所有帧都可以立即丢弃。

// instead of
const add = (x,y) =>
  { return x + y }

// no return value
const add = (x,y) =>
  { x + y }

// but then how do we get the computed result?
add (1,2) // => undefined

延拓传递样式

输入延拓传递方式 -通过向每个函数添加一个连续参数，就好像我们发明了我们自己的返回机制

不要被下面的例子弄得不知所措--大多数人已经看到了连续传递风格，这种形式被误解为回调。

// jQuery "callback"
$('a').click (event => console.log ('click event', event))

// node.js style "callback"
fs.readFile ('entries.txt', (err, text) =>
  err
    ? console.error (err)
    : console.log (text))

这就是处理计算结果的方法--将其传递给一个延续

​

// add one parameter, k, to each function
// k makes *return* into a normal function
// note {}'s are used to suppress the implicit return value of JS arrow functions
const add = (x,y,k) =>
  { k (x + y) }

const sq = (x,k) =>
  { k (x * x) }
  
const sqrt = (x,k) =>
  { k (Math.sqrt (x)) }

const pythag = (a,b,k) =>
  // sq(a) is computed, $a is the result
  sq (a, $a => {
    // sq(b) is computed, $b is the result
    sq (b, $b => {
      // add($a,$b) is computed, $sum is the result
      add ($a, $b, $sum => {
        // sqrt ($sum) is computed, conintuation k is passed thru
        sqrt ($sum, k) }) }) })
  
// here the final continuation is to log the result
// no *return* value was used !
// no reason to keep frames in the stack !
pythag (3, 4, $c => { console.log ('pythag', $c) })

​

如何得到一个值？

这个著名问题：让数以百万计的程序员感到困惑--只是，它实际上与“异步调用”无关，与延续有关，也与那些延续是否返回任何内容有关。

  // nothing can save us...
  // unless pythag *returns*
  var result = pythag (3,4, ...)
  console.log (result) // undefined

如果没有返回值，则必须使用连续值将值移动到计算的下一步--这不可能是我尝试过的第一种方法：^^

，但一切都在尾部!

我知道很难通过查看它来判断，但是每个函数都有一个位于尾位置的函数调用--如果我们在函数中恢复返回功能，调用1的值就是调用2的值，调用3的值等等--在这种情况下没有必要为后续调用引入一个新的堆栈框架--相反，调用1的帧可以重新使用--用于调用2，然后再用于调用3；我们仍然可以保留返回值！

​

// restore *return* behaviour
const add = (x,y,k) =>
  k (x + y)

const sq = (x,k) =>
  k (x * x)
  
const sqrt = (x,k) =>
  k (Math.sqrt (x))

const pythag = (a,b,k) =>
  sq (a, $a =>
    sq (b, $b =>
      add ($a, $b, $sum =>
        sqrt ($sum, k))))
  
// notice the continuation returns a value now: $c
// in an environment that optimises tail calls, this would only use 1 frame to compute pythag
const result =
  pythag (3, 4, $c => { console.log ('pythag', $c); return $c })
  
// sadly, the environment you're running this in likely took almost a dozen
// but hey, it works !
console.log (result) // 5

​

一般情况下尾调用；同样地，

这种将“正常”函数转换为连续传递式函数的过程可以是一个机械的过程，并自动完成--但是把所有东西放到尾部位置的真正意义是什么呢？

如果我们知道框架1的值是框架2的值，也就是框架3的值，那么我们可以使用while循环手动折叠堆栈帧，其中计算的结果在每次迭代过程中都会就地更新--使用这种技术的函数称为蹦床。

当然，在编写递归函数时，蹦床最常被提及，因为递归函数可能多次“弹出”(产生另一个函数调用)，甚至是无限期的--但这并不意味着我们不能在pythag函数上演示只会产生几个call的蹦床。

​

const add = (x,y,k) =>
  k (x + y)

const sq = (x,k) =>
  k (x * x)
  
const sqrt = (x,k) =>
  k (Math.sqrt (x))

// pythag now returns a "call"
// of course each of them are in tail position ^^
const pythag = (a,b,k) =>
  call (sq, a, $a =>
    call (sq, b, $b =>
      call (add, $a, $b, $sum =>
        call (sqrt, $sum, k))))
  

const call = (f, ...values) =>
  ({ type: call, f, values })
  
const trampoline = acc =>
  {
    // while the return value is a "call"
    while (acc && acc.type === call)
      // update the return value with the value of the next call
      // this is equivalent to "collapsing" a stack frame
      acc = acc.f (...acc.values)
    // return the final value
    return acc
  }

// pythag now returns a type that must be passed to trampoline
// the call to trampoline actually runs the computation
const result =
  trampoline (pythag (3, 4, $c => { console.log ('pythag', $c); return $c }))

// result still works
console.log (result) // 5

​

，你为什么要给我看这些？

因此，即使是我们的环境也不支持堆栈安全递归，只要我们将一切保持在尾部位置并使用我们的call助手，我们现在就可以将任何堆栈调用转换为一个循环。

// doesn't matter if we have 4 calls, or 1 million ... 
trampoline (call (... call (... call (...))))

在第一个代码示例中，我展示了如何使用auxiliary循环，但我也使用了一个非常聪明(尽管效率很低)的循环，它不需要在数据结构中进行深度循环--有时这并不总是可能的；例如，有时递归函数可能会产生2或3个重复调用--然后怎么办？

下面我将向您展示flatten作为一个天真的、无尾递归过程--这里需要注意的是，有条件的一个分支导致了对flatten的两个重复调用--这个类似树的递归过程一开始可能很难平缓成一个迭代循环，但是仔细、机械地转换到连续传递样式将表明这种技术几乎可以在任何(如果不是全部)场景中工作。

草稿

// naive, stack-UNSAFE
const flatten = ([x,...xs]) =>
  x === undefined
    ? []
    : Array.isArray (x)
      // two recurring calls
      ? flatten (x) .concat (flatten (xs))
      // one recurring call
      : [x] .concat (flatten (xs))

延拓传递方式

// continuation passing style
const flattenk = ([x,...xs], k) =>
  x === undefined
    ? k ([])
    : Array.isArray (x)
      ? flattenk (x, $x =>
          flattenk (xs, $xs =>
            k ($x.concat ($xs))))
      : flattenk (xs, $xs =>
          k ([x].concat ($xs)))

连续式蹦床传球方式

​

const call = (f, ...values) =>
  ({ type: call, f, values })
      
const trampoline = acc =>
  {
    while (acc && acc.type === call)
      acc = acc.f (...acc.values)
    return acc
  }

const flattenk = ([x,...xs], k) =>
  x === undefined
    ? call (k, [])
    : Array.isArray (x)
      ? call (flattenk, x, $x =>
          call (flattenk, xs, $xs =>
            call (k, $x.concat ($xs))))
      : call (flattenk, xs, $xs =>
          call (k, ([x].concat ($xs))))

const flatten = xs =>
  trampoline (flattenk (xs, $xs => $xs))

let data = []
for (let i = 2e4; i>0; i--)
  data = [i, data];

console.log (flatten (data))

​

唤醒，你不小心发现了单簧管

草稿

​

// yours truly, the continuation monad
const cont = x =>
  k => k (x)

// back to functions with return values
// notice we don't need the additional `k` parameter
// but this time wrap the return value in a continuation, `cont`
// ie, `cont` replaces *return*
const add = (x,y) =>
  cont (x + y)

const sq = x =>
  cont (x * x)
  
const sqrt = x =>
  cont (Math.sqrt (x))

const pythag = (a,b) =>
  // sq(a) is computed, $a is the result
  sq (a) ($a =>
    // sq(b) is computed, $b is the result
    sq (b) ($b =>
      // add($a,$b) is computed, $sum is the result
      add ($a, $b) ($sum =>
        // sqrt ($sum) is computed, a conintuation is returned 
        sqrt ($sum))))
  
// here the continuation just returns whatever it was given
const $c =
  pythag (3, 4) ($c => $c)
  
console.log ($c)
// => 5

​

分隔的延续

草稿

​

const identity = x =>
  x

const cont = x =>
  k => k (x)

// reset
const reset = m =>
  k => m (k)

// shift
const shift = f =>
  k => f (x => k (x) (identity))

const concatMap = f => ([x,...xs]) =>
  x === undefined
    ? [ ]
    : f (x) .concat (concatMap (f) (xs))

// because shift returns a continuation, we can specialise it in meaningful ways
const amb = xs =>
  shift (k => cont (concatMap (k) (xs)))

const pythag = (a,b) =>
  Math.sqrt (Math.pow (a, 2) + Math.pow (b, 2))

const pythagTriples = numbers =>
  reset (amb (numbers) ($x =>
          amb (numbers) ($y =>
            amb (numbers) ($z =>
              // if x,y,z are a pythag triple
              pythag ($x, $y) === $z
                // then continue with the triple
                ? cont ([[ $x, $y, $z ]])
                // else continue with nothing
                : cont ([ ])))))
        (identity)
        
console.log (pythagTriples ([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]))
// [ [ 3, 4, 5 ], [ 4, 3, 5 ], [ 6, 8, 10 ], [ 8, 6, 10 ] ]      

​

Answer 3

递归函数表达得很好，而尾部递归优化甚至可以防止它们吹过堆栈。

但是，任何递归函数都可以转换为基于更丑的迭代器的解决方案，这可能只在内存消耗和性能方面很漂亮，尽管不需要考虑。

请参阅：Javascript中处理n个嵌套数组的迭代解法

也许是对不同方法的测试：https://jsperf.com/iterative-array-flatten/2