关键词：
第7章 递归
王二、张三和赵四一日无聊，决定玩击鼓传花讲冷笑话的游戏。王二和张三围成一圈传花，赵四负责击鼓。张三接连讲了几个诸如小菜、狐狸狡猾的笑话。花停在了王二的手中。
王二：这个笑话很短。你要保证听完后不生气我就说。
张三：你说吧。
王二：张三。
张三：怎么了？
王二：笑话说完了，就两个字。
张三欲发怒。
王二：欸，你刚才说好了不会生气的。
张三只好作罢。新一轮开始，花又停在王二的手中。
王二：张三不是个笑话。
张三再次欲发怒。
王二：别生气，我说的是冷笑话，就表示不好笑啊。
花又一次停在王二的手中。
王二：[张三不是个笑话]不是个笑话。
第四次花停在王二的手中。
王二：[[[张三不是个笑话]不是个笑话]不是个笑话]。
……
7.1 调用自身
7.1.1 递归的思路
7.1.2 带累积参数的递归函数
7.2 递归的数据结构
7.2.1 构建列表
7.2.2 树
7.3 递归与迭代
7.3.1 名称
7.3.2 理念和对比
7.3.3 迭代协议
7.3.4 递归协议
7.3.5 搜索树
7.4 尾部递归
7.4.1 调用堆栈
7.4.2 尾部调用优化
7.4.3 怎样算是尾部调用
7.4.4 尾部递归
7.5 递归的效率
我们来计算经典的斐波那契数列。菲波那契数列的通项公式为，当n=0和1时，A(n)=n；当n>=2时，A(n)=A(n-1)+A(n-2)。如果让一个数学不错又刚学习编程的高中生来写计算斐波那契项的函数，结果可能会是这样。
function fibonacci1(n)
const phi = (1 + Math.sqrt(5)) / 2;
if (n < 2)
return n;
return (Math.pow(phi, n) + Math.pow(1 - phi, n)) / (phi * (3 - phi));
f.log(fibonacci1(10))
//=> 55.007272246494842705
他的思路如下：将等式A(n)=A(n-1)+A(n-2)变形为A(n)+x*A(n-1)=(1+x)*[A(n-1)+1/(1+x)*A(n-2)]。令x=1/(1+x)，可得1元2次方程x^2+x-1=0，解出x=[-1+sqrt(5)]/2或[-1-sqrt(5)]/2。因为A(n)+x*A(n-1)构成一个等比数列，再加上初始两项的值，可求得A(n)+x*A(n-1)的值。再利用这个公式递归地消去A(n-1)，计算出通项A(n)的值。
这样的解法会让数学老师高兴，计算机老师难过。计算机被当成计算器来用。另外，由于运算中涉及到小数，计算结果与本应是整数的精确值相比有微小的误差，如上面的fibonacci1(10)精确值是55。
正常的计算方法可以采用迭代。
function fibonacci2(n)
if (n < 2)
return n;
let a = 0, b = 1, c;
for (let i = 2; i <= n; i++)
c = a + b;
a = b;
b = c;
return c;
f.log(fibonacci2(10))
//=> 55
也可以采用递归。
function fibonacci3(n)
if (n < 2)
return n;
return fibonacci3(n - 1) + fibonacci3(n - 2);
f.log(fibonacci3(10))
//=> 55
三个版本中，采用递归的版本最简短，它只是将斐波那契数列的数学定义用编程语言写出来。到现在为止，三个函数表现都还基本不错。但当我们求更大的斐波那契项时，情况开始有变化了。
f.log(fibonacci1(100))
//=> 354224848179261800000
f.log(fibonacci2(100))
//=> 354224848179261800000
f.log(fibonacci3(100))
//=> 一觉醒来还是没有结果
fibonacci1和fibonacci2都很快得出了一致的结果（因为数字太大，fibonacci1返回值中的小数被忽略了），而fibonacci3则永远都得不出结果。出了什么问题呢？
考察fibonacci3的计算过程，可以让我们找出原因。本章所有此前出现的递归函数有一个共同点，返回语句只包含一次递归调用，用数列的语言来说就是，当前项的值只依赖于前一项。而fibonacci3的递归算法在求第n项A(n)时，不仅要利用前一项A(n-1)，还要依赖更前一项A(n-2)，这导致对此前项的大量重复计算，项数越小，重复的次数越多。令B(i)为第i项被计算的次数，则有
B(i) = 1; i = n, n - 1
B(i) = B(i + 1) + B(i + 2); i < n - 1
这样，B(i)形成了一个有趣的逆的斐波那契数列。求A(n)时有：
B(i) = A(n + 1 - i)
换一个角度来看，令C(i)为求A(i)时需要做的加法的次数，则有
C(i) = 0; i = 0, 1
C(i) = 1 + C(i - 1) + C(i - 2); i > 1
令D(i) = C(i) + 1，有
D(i) = 1; i = 0, 1
D(i) = D(i - 1) + D(i - 2)
所以D(i)又形成一个斐波那契数列。并可因此得出：
C(n) = A(n + 1) - 1
A(n)是以几何级数增长，所以fibonacci3在n较大时所做的重复计算量会变得十分惊人。与它相对应的采用迭代的程序fibonacci2，有
B(n) = 1; n为任意值
C(n) = 0; n = 0, 1
C(n) = n - 1; n > 1
因而当n增长时，一直能保持很快的速度。
聪明的读者也许已经想到了解决的方法，本书之前介绍的“记忆化”模式的功用正是避免以同样的参数多次调用函数时的重复计算。记忆化普通函数很简单，只需将其传递给memoize函数，返回的就是记忆化的版本。这种方法对递归函数却不适用，因为递归函数体内有对自身的调用，无法利用记忆化的版本，要想记住对某个参数的计算结果，只有用memoize函数类似的写法，修改递归函数。
const fibonacci4 = function ()
const memory = new Map();
return function fibonacci4(n)
if (m.has(n, memory))
return m.get(n, memory);
if (n < 2)
m.set(n, n, memory);
else
m.set(n, fibonacci4(n - 1) + fibonacci4(n - 2), memory);
return m.get(n, memory);
();
因为这里的参数限定为非负整数，所以用于记忆计算结果的Map，可以换成数组，这样函数可以改写得更简洁，运行速度也更快。
const fibonacci5 = function ()
const memory = [0, 1];
return function fibonacci5(n)
if (memory.length <= n)
memory[n] = fibonacci5(n - 1) + fibonacci5(n - 2);
return memory[n];
();
在这两个版本的递归算法中，虽然形式上在计算第n项时，仍然包含两次递归调用，但实际上对于每个n，函数都只计算了一次，其他对第n项的引用，都是从记忆中读取的，所以求第n项过程中进行的加法运算次数与迭代算法相同，具有同样的可伸缩性。
仔细的读者会发现，迄今为止的三个递归版本，都不算是尾部调用。所以当n很大时，还是会出现调用堆栈耗尽的问题。
fibonacci5(10**8)
//=> Maximum call stack size exceeded
上一节已经介绍了，可以利用累积参数将函数转换成尾部递归。在返回语句只包含一次递归调用的情况下，转换的方法是一目了然的。而对fibonacci3这样返回语句包含两次递归调用的函数，以前的方法就无效了。思路的突破口是，一次递归调用需要一个参数来累积，多次递归调用时，每次调用都需要一个参数来累积。这样就得到fibonacci3尾部递归的版本。
function fibonacci6(n)
return _fibonacci(n, 0, 1);
function _fibonacci(n, a, b)
if (n === 0)
return a;
return _fibonacci(n - 1, b, a + b);
最后，我们来比试一下各种版本算法的速度。
export function doUnto(...args)
return function (fn)
return fn(...args);
const cTookTime = f.unary(f.curry(f.tookTime, 2));
let fns = f.map(cTookTime, [fibonacci1, fibonacci2, fibonacci4, fibonacci4,
fibonacci5, fibonacci5, fibonacci6]);
fibonacci5,fibonacci6]);
f.forEach(f.doUnto(1000), fns);
//=> 4.346655768693734e+208
//=> fibonacci1(1000): 1.828857421875ms
//=> 4.346655768693743e+208
//=> fibonacci2(1000): 0.243896484375ms
//=> 4.346655768693743e+208
//=> fibonacci4(1000): 3.918212890625ms
//=> 4.346655768693743e+208
//=> fibonacci4(1000): 0.126953125ms
//=> 4.346655768693743e+208
//=> fibonacci5(1000): 0.372802734375ms
//=> 4.346655768693743e+208
//=> fibonacci5(1000): 0.156005859375ms
//=> 4.346655768693743e+208
//=> fibonacci6(1000): 0.223876953125ms
多次测试，每个函数花费的时间会有波动，但总体上的排名没有多少出入。从这个结果能读出很多有趣的信息。fibonacci1直接根据斐波那契数列项的公式来计算，因为涉及开方和小数的乘方等运算，并不算快。fibonacci2的迭代算法，名列前茅。fibonacci3没有参赛资格。fibonacci4用映射数据结构作缓存，第一次计算时速度最慢，再次计算时读取缓存，速度最快。fibonacci5用数组作缓存，第一次计算时，速度已经和不需缓存的最快算法在一个数量级上；第二次计算时，依靠读取缓存，速度和fibonacci4差不多。fibonacci6的尾部递归算法，与迭代算法不相上下。
7.6 小结
更多内容，请参看拙著：
《javascript函数式编程思想》——从面向对象到函数式编程
...假如本书的写作时间倒退回十年前，书名可能会变成JavaScript面向对象编程思想。自上世纪90年代兴起的面向对象编程思想随Java的繁荣达于顶点，在JavaScript从一门只被用来编写零星的简单的表单验证代码的玩具语言变成日... 查看详情
《javascript函数式编程思想》
自序伴随着Web技术的普及，JavaScript已成为应用最广泛的编程语言之一。由于其在Web前端编程中的统治地位、语言本身的表现力、灵活性、开源的本质和ECMAScript标准近年来的快速发展，JavaScript向各个领域渗透的势头仍然... 查看详情
《javascript函数式编程思想》
自序伴随着Web技术的普及，JavaScript已成为应用最广泛的编程语言之一。由于其在Web前端编程中的统治地位、语言本身的表现力、灵活性、开源的本质和ECMAScript标准近年来的快速发展，JavaScript向各个领域渗透的势头仍然... 查看详情
《javascript函数式编程思想》——部分应用和复合
第5章 部分应用和复合一等值的函数，是函数式编程的基石。部分应用和复合，则是函数式编程的重要特征。采用命令式编程时，每当我们感觉需要抽象出一个新的功能时，就会定义一个函数。在函数式编程中... 查看详情
《javascript函数式编程思想》——函数是一等值
第4章 函数是一等值在函数式编程的标准或特点中，“函数是一等值”是最基本和重要的，也是最为人所知的，所有介绍函数式编程的书籍和文章都会优先介绍这一点，以至于“一等值”几乎成为函数的专属头衔&... 查看详情
《javascript函数式编程思想》——名称
第1章 名称一般对函数式编程的介绍都会从一等值和纯函数等概念开始，本书却准备在那之前先花些篇章讨论两个通常未得到足够重视的主题：名称和类型系统。前者包括名称绑定、作用域和闭包等内容，后者包括类... 查看详情
《javascript函数式编程思想》——类型系统
第2章 类型系统为什么在许多编程语言中整数和浮点数是两种类型？结构体、数组、列表、映射……这些类型有什么关系？用户自定义的各种类型与它们又有什么关系？函数也是类型吗？强类型和弱类型意味着什... 查看详情
《javascript函数式编程思想》——副作用和不变性
第6章 副作用和不变性6.1 副作用6.2 纯函数6.2.1 外部变量6.2.2 实现6.2.3 函数内部的副作用6.2.4 闭包6.3 不变性6.3.1 哲学上的不变性与身份6.3.2 简单类型和复合类型6.3.3 值类型和引用类型6.3.4 可变类型和不可变类型6.3.5 可变... 查看详情
玩转javascript面试：何为函数式编程？(代码片段)
函数式编程在JavaScript领域着实已经成为一个热门话题。就在几年前，很多JavaScript程序员甚至都不知道啥是函数式编程，但是就在近三年里我看到过的每一个大型应用的代码库中都包含了函数式编程思想的大规模使用。函数式编... 查看详情
函数式编程 - 非常强调递归，为啥？
】函数式编程-非常强调递归，为啥？【英文标题】：FunctionalProgramming-Lotsofemphasisonrecursion,why?函数式编程-非常强调递归，为什么？【发布时间】：2012-09-2111:51:11【问题描述】：我开始了解函数式编程[FP]（使用Scala）。从我最初的... 查看详情
函数式编程思想
对于函数式编程来说，其只关心，定义输入数据和输出数据相关的关系，数学表达式里面其实是在做一种映射（mapping），输入的数据和输出的数据关系是什么样的，是用函数来定义的。http://www.yxtvg.com/toutiao/5413179/20180212a04ro500.ht... 查看详情
函数响应式编程（frp）思想
...让你的代码像数学一样简洁，业务像流水一样清晰流畅。函数响应式编程响应式编程思想为体，函数式编程思想为用。响应式编程例如，在命令式编程环境中，a:=b+c表示将表达式的结果赋给a，而之后改变b或c的值不会影响a。但... 查看详情
11.高阶函数（匿名/*递归/函数式）对象编程基础
高阶函数匿名函数匿名函数存在的情况：内置函数函数式编程递归函数式编程面向对象的程序设计类：实例：OOP类的名称空间/对象的名称空间高阶函数匿名函数lambdax:x+y#returnx+y定义标志/参数（形式类似函数传参）/跟表达式（返... 查看详情
kotlin函数式编程思想fpinkotlin
Kotlin函数式编程思想:FPinKotlin函数式编程特性闭包和高阶函数函数编程支持函数作为第一类对象，有时称为闭包或者仿函数(functor)对象。实质上，闭包是起函数的作用并可以像对象一样操作的对象。与此类似，FP语言... 查看详情
Javascript中具有递归的高阶函数
】Javascript中具有递归的高阶函数【英文标题】：Higher-orderfunctionwithrecursioninJavascript【发布时间】：2021-11-0107:09:08【问题描述】：这里是新手...我试图掌握Javascript中函数式编程的概念，但我卡住了。我正在尝试通过递归（高阶函... 查看详情
day03-递归函数函数式编程
1、递归函数在函数内部，可以调用其他函数。但是一个函数在内部调用自身，这个函数被称为递归函数。1defcalc(n):2print(n)3ifint(n/2)==0:#结束符4returnn5returncalc(int(n/2))#调用函数自身67m=calc(10)8print(‘----->‘,m)#输出结果10521-----&... 查看详情
javascriptes6函数式编程：柯里化偏应用组合管道(代码片段)
上一篇介绍了闭包和高阶函数，这是函数式编程的基础核心。这一篇来看看高阶函数的实战场景。首先强调两点：注意闭包的生成位置，清楚作用域链，知道闭包生成后缓存了哪些变量高阶函数思想：以变量作用域作为根基，以... 查看详情
javascript函数式编程
第1章JavaScript函数式编程简介11.1JavaScript案例11.2开始函数式编程41.2.1为什么函数式编程很重要41.2.2以函数为抽象单元71.2.3封装和隐藏91.2.4以函数为行为单位101.2.5数据抽象141.2.6函数式JavaScript初试171.2.7加速191.3Underscore示例221.4总结2... 查看详情