# 第 9 章：递归（下）

## 栈、堆

```function isOdd(v) {
if (v === 0) return false;
return isEven( Math.abs( v ) - 1 );
}

function isEven(v) {
if (v === 0) return true;
return isOdd( Math.abs( v ) - 1 );
}```

`isOdd( 33333 );         // RangeError: Maximum call stack size exceeded`

```function foo() {
var z = "foo!";
}

function bar() {
var y = "bar!";
foo();
}

function baz() {
var x = "baz!";
bar();
}

baz();```

### 正确的尾调用 (PTC)

`return foo( .. );`

```foo();
return;

// 或

var x = foo( .. );
return x;

// 或

return 1 + foo( .. );```

`foo(..)` 运行结束之后 `1+` 这部分才开始执行，所以此时的堆栈帧依然存在。

`return x ? foo( .. ) : bar( .. );`

`x` 进行条件判断之后，或执行 `foo(..)`，或执行 `bar(..)`，不论执行哪个，返回结果都会被 `return` 返回掉。这个例子符合 PTC 规范。

## 重构递归

### 更换堆栈

```function sum(num1,...nums) {
if (nums.length == 0) return num1;
return num1 + sum( ...nums );
}```

```function sum(result,num1,...nums) {
// ..
}```

```"use strict";

function sum(result,num1,...nums) {
result = result + num1;
if (nums.length == 0) return result;
return sum( result, ...nums );
}```

`sum( /*initialResult=*/0, 3, 1, 17, 94, 8 );        // 123`

```"use strict";

function sumRec(result,num1,...nums) {
result = result + num1;
if (nums.length == 0) return result;
return sumRec( result, ...nums );
}

function sum(...nums) {
return sumRec( /*initialResult=*/0, ...nums );
}

sum( 3, 1, 17, 94, 8 );                             // 123```

```"use strict";

function sum(...nums) {
return sumRec( /*initialResult=*/0, ...nums );

function sumRec(result,num1,...nums) {
result = result + num1;
if (nums.length == 0) return result;
return sumRec( result, ...nums );
}
}

sum( 3, 1, 17, 94, 8 );                             // 123```

```"use strict";

var sum = (function IIFE(){

return function sum(...nums) {
return sumRec( /*initialResult=*/0, ...nums );
}

function sumRec(result,num1,...nums) {
result = result + num1;
if (nums.length == 0) return result;
return sumRec( result, ...nums );
}

})();

sum( 3, 1, 17, 94, 8 );                             // 123```

```"use strict";

function sum(result,num1,...nums) {
result = result + num1;
if (nums.length == 0) return result;
return sum( result, ...nums );
}

sum( /*initialResult=*/0, 3, 1, 17, 94, 8 );        // 123```

```"use strict";

function sum(num1,num2,...nums) {
num1 = num1 + num2;
if (nums.length == 0) return num1;
return sum( num1, ...nums );
}

sum( 3, 1, 17, 94, 8 );                             // 123```

1. 首先对前两个参数 `num1``num2` 进行对比。
2. 如果 `num1` 是偶数，并且 `num1` 大于 `num2``num1` 保持不变。
3. 如果 `num2` 是偶数，把 `num2` 赋值给 `num1`
4. 否则的话，`num1` 等于 `undefined`
5. 如果除了这两个参数之外，还存在其它参数 `nums`，把它们与 `num1` 进行递归对比。
6. 最后，不管是什么值，只需返回 `num1`

```"use strict";

function maxEven(num1,num2,...nums) {
num1 =
(num1 % 2 == 0 && !(maxEven( num2 ) > num1)) ?
num1 :
(num2 % 2 == 0 ? num2 : undefined);

return nums.length == 0 ?
num1 :
maxEven( num1, ...nums )
}```

### 后继传递格式 （CPS）

`fib(..)` 做如下修改：

```"use strict";

function fib(n,cont = identity) {
if (n <= 1) return cont( n );
return fib(
n - 2,
n2 => fib(
n - 1,
n1 => cont( n2 + n1 )
)
);
}```

### 弹簧床

```function trampoline(fn) {
return function trampolined(...args) {
var result = fn( ...args );

while (typeof result == "function") {
result = result();
}

return result;
};
}```

```var sum = trampoline(
function sum(num1,num2,...nums) {
num1 = num1 + num2;
if (nums.length == 0) return num1;
return () => sum( num1, ...nums );
}
);

var xs = [];
for (let i=0; i<20000; i++) {
xs.push( i );
}

sum( ...xs );                   // 199990000```

## 总结

0 条评论

• ### 全本 | iKcamp翻译 | 《JavaScript 轻量级函数式编程》|《你不知道的JS》姊妹篇

本书主要探索函数式编程(FP)的核心思想。在此过程中，作者不会执着于使用大量复杂的概念来进行诠释，这也是本书的特别之处。我们在 JavaScript 中应用的仅...

• ### iKcamp｜基于Koa2搭建Node.js实战（含视频）☞ 解析JSON

视频地址：https://www.cctalk.com/v/15114923886141 JSON 数据 我颠倒了整个世界，只为摆正你的倒影。 前面的文章中，...

• ### 15 个简单、有趣而实用的 单行 HTTP Server

不少语言或服务开发框架都内置了简单的 Web Server 供我们方便的调试使用。比如有时候我们需要调试单个 PHP 页面而不想搭建一套完整的 PHP 环境，亦...

• ### 机器学习并不难

在这篇文章中，我们将讨论一般情况下的机器学习的方法以及其与数据库之间的交互途径。如果你是一个不知从何开始学起的初学者，有兴趣知道到底为何我们需要机器学习，并且疑...

• ### 腾讯云上线游戏语音SDK，完美兼容所有主流游戏引擎

在网络游戏中，无论是大逃杀、棋牌类、电子竞技类还是娱乐休闲类小游戏，玩家和玩家之间的互动、语音聊天是一个必不可少的环节。这是一个通用的需求，如果由游戏厂商自己从...

• ### 我是如何刷 LeetCode 的？

虽然我是软件工程专业毕业的，但是由于大学的时候一门心思在应用开发身上，「算法与数据结构」这门课重要的课程我并没有学好。所以开始刷 LeetCode 的时候我完全...

• ### 本土杂志Genes & Diseases：去年才被SCI收录，今年影响因子要破5

Genes & Diseases杂志是一本全英文期刊，2014年9月创刊，由重庆医科大学和Elsevier合作出版。它是国内第一本分子医学与转化医学相结合的期刊...

• ### 漫话：如何给女朋友解释什么是分布式和集群？

某天，下班较早，我正在玩吃鸡，已经到决赛圈了，这时候，女朋友满脸求知欲的朝我走过来。

• ### AAAI2019《图表示学习》Tutorial, 180 页 PPT 带你从入门到精通（下载）

图表示学习，是 2018 年火爆全球的一个深度学习方向，从以 Line, meta-path 等为首的节点表示学习，到以 GCN，GraphSAGE，为首的图卷...