lodash-chain、递归-PTC、TCO和STC

language_js algorithm summary_2018/12

1、lodash-chain

1.1、 lodash 的链式调用

• _:Creates a lodash object which wraps value to enable implicit method chain sequences.(隐式)
• _.chain:Creates a lodash wrapper instance that wraps value with explicit method chain sequences enabled. (显式，需要通过value获取结果)

1.2、 使用

const _ = require('lodash')
let list = [1, 2, 3, 4, 5]
// _.chain
const res = _
  .chain(list)
  .filter(n => n % 2 === 0)
  .sum()
// wrap value
//console.log(res)
// 6
console.log(res.value())
list.push(8)
// 14 (The execution of chained methods is lazy),不会立即执行而是调用的时候再执行，比如等待资源加载完成
console.log(res.value())
let list1 = [1, 2, 3, 4, 5]
// _
const res1 = _(list1)
  .filter(n => n % 2 === 0)
// [ 2, 4 ]
console.log(res1.value())
// wrap:filter is chainable
console.log(res1)
// 14  sum：not chainable
console.log(res1.sum())

1.3、 结论

• 对于显示调用：需要使用调用value获取最后的结果。而隐式调用：使用value可以获取wrap value的值，或使用not chainable的func时会返回结果。
• 关于lazy execute：Lazy evaluation allows several methods to support shortcut fusion. Shortcut fusion is an optimization to merge iteratee calls; this avoids the creation of intermediate arrays and can greatly reduce the number of iteratee executions.

2、递归-PTC、TCO和STC

2.1、递归和调用栈

• 递归：对于大家而言也许都很熟悉，在我的理解中是不断的向下计算，到达根节点后又向上运行。以计算阶乘为例：

function factorial(n) {
  if (n === 1) {
    return 1
   }
   return n*factorial(n - 1)
}
// 计算过程
factorial(5) = factorial(4) * 5
factorial(5) = factorial(3) * 4 * 5
factorial(5) = factorial(2) * 3 * 4 * 5
factorial(5) = factorial(1) * 2 * 3 * 4 * 5
factorial(5) = 1 * 2 * 3 * 4 * 5

• 调用栈
  
  • 对函数的每一次调用都会调用栈，进行递归调用时，会进行压栈，直到再弹出。但过多的递归调用会导致栈溢出。

// example
function factorial(n) {
  // log stack information
  console.trace()
  if (n === 1) {
    return 1
  }
  return n * factorial(n - 1)
}
factorial(3)
// log 进行了3次压栈调用
Trace
    at factorial (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:32:14)
    at factorial (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:32:14)
    at factorial (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:32:14)
    at Object.<anonymous> (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:35:1)
    at Module._compile (module.js:652:30)
    at Object.Module._extensions..js (module.js:663:10)
    at Module.load (module.js:565:32)
    at tryModuleLoad (module.js:505:12)
    at Function.Module._load (module.js:497:3)

2.2、适当的尾调用（PTC、Proper Tail Call）

• 为了减少压栈，防止栈溢出，但实际上大多数运行速度并不会提高。
• 尾调用：即最后一步调用另一个函数。尾调用不会导致栈无限增大，即通过把当前函数的返回值传递给调用的函数，从而不再对当前函数有依赖，可以销毁栈。

// example
function factorial(n, total = 1) {
    if (n === 0) {
        return total
    }
    return factorial(n - 1, n * total)
}
// 过程factorial（3, 1）
factorial（3, 1）
factorial（2, 3）
factorial（1, 6）
在每一步运行中，上一个函数的结果会传到下一次调用的函数中。从而只保证只有一个栈在调用。
Tips：node移除了对尾递归的优化。

2.3、尾调用优化（TCO、Tail Call Optimization）

• 尾调用优化是编译器使用的技术，通过把递归转换为循环。
• 与适当的尾调用不同，尾调用优化是为了优化自身性能，减少压栈等等操作。即把尾递归转化为一个循环，比如对上面的递归进行优化：

function factorial (n, total = 1) {
  while (true) {
    if (n === 0) {
      return total
    }
    total = n * total
    n = n - 1
  }
}

2.4、尾调用优化及适当的尾调用的弊端

• 尾调用优化及适当的尾调用意味着不会在栈里“保存”调用函数的历史。结果查看栈追踪信息就很难定位到问题，因为它并不包含所有调用信息。

2.5、语法级尾调用（STC）

• 语法级尾调用是一种告诉编译器是否使用适当的尾调用、或者尾调用的方式，尊重开发者自己的选择，自己控制栈的复杂度。

2.6、参考资料

• JavaScript中的递归、PTC、TCO和STC