[关闭]
@JunQiu 2018-12-10T13:46:33.000000Z 字数 2807 阅读 666

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

language_js algorithm summary_2018/12


1、lodash-chain
1.1、 lodash 的链式调用
1.2、 使用
  1. const _ = require('lodash')
  2. let list = [1, 2, 3, 4, 5]
  3. // _.chain
  4. const res = _
  5. .chain(list)
  6. .filter(n => n % 2 === 0)
  7. .sum()
  8. // wrap value
  9. //console.log(res)
  10. // 6
  11. console.log(res.value())
  12. list.push(8)
  13. // 14 (The execution of chained methods is lazy),不会立即执行而是调用的时候再执行,比如等待资源加载完成
  14. console.log(res.value())
  15. let list1 = [1, 2, 3, 4, 5]
  16. // _
  17. const res1 = _(list1)
  18. .filter(n => n % 2 === 0)
  19. // [ 2, 4 ]
  20. console.log(res1.value())
  21. // wrap:filter is chainable
  22. console.log(res1)
  23. // 14 sum:not chainable
  24. console.log(res1.sum())
1.3、 结论

2、递归-PTC、TCO和STC
2.1、递归和调用栈
  1. function factorial(n) {
  2. if (n === 1) {
  3. return 1
  4. }
  5. return n*factorial(n - 1)
  6. }
  7. // 计算过程
  8. factorial(5) = factorial(4) * 5
  9. factorial(5) = factorial(3) * 4 * 5
  10. factorial(5) = factorial(2) * 3 * 4 * 5
  11. factorial(5) = factorial(1) * 2 * 3 * 4 * 5
  12. factorial(5) = 1 * 2 * 3 * 4 * 5

  1. // example
  2. function factorial(n) {
  3. // log stack information
  4. console.trace()
  5. if (n === 1) {
  6. return 1
  7. }
  8. return n * factorial(n - 1)
  9. }
  10. factorial(3)
  11. // log 进行了3次压栈调用
  12. Trace
  13. at factorial (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:32:14)
  14. at factorial (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:32:14)
  15. at factorial (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:32:14)
  16. at Object.<anonymous> (/Users/qiujun/WebstormProjects/sad-e015/level-1-upgrade-ads-strategy/test.js:35:1)
  17. at Module._compile (module.js:652:30)
  18. at Object.Module._extensions..js (module.js:663:10)
  19. at Module.load (module.js:565:32)
  20. at tryModuleLoad (module.js:505:12)
  21. at Function.Module._load (module.js:497:3)
2.2、适当的尾调用(PTC、Proper Tail Call)
  1. // example
  2. function factorial(n, total = 1) {
  3. if (n === 0) {
  4. return total
  5. }
  6. return factorial(n - 1, n * total)
  7. }
  8. // 过程factorial(3, 1)
  9. factorial3, 1
  10. factorial2, 3
  11. factorial1, 6
  12. 在每一步运行中,上一个函数的结果会传到下一次调用的函数中。从而只保证只有一个栈在调用。
  13. Tipsnode移除了对尾递归的优化。
2.3、尾调用优化(TCO、Tail Call Optimization)
  1. function factorial (n, total = 1) {
  2. while (true) {
  3. if (n === 0) {
  4. return total
  5. }
  6. total = n * total
  7. n = n - 1
  8. }
  9. }
2.4、尾调用优化及适当的尾调用的弊端
2.5、语法级尾调用(STC)
2.6、参考资料
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注