文档章节

JavaScript中的递归

Fundebug
 Fundebug
发布于 2017/06/20 15:09
字数 1822
阅读 14
收藏 0

译者按: 程序员应该知道递归,但是你真的知道是怎么回事么?

原文: All About Recursion, PTC, TCO and STC in JavaScript

译者: Fundebug

为了保证可读性,本文采用意译而非直译。

递归简介

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

我们来举个例子,我们可以用4的阶乘乘以4来定义5的阶乘,3的阶乘乘以4来定义4的阶乘,以此类推。

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) = factorial(0) * 1 * 2 * 3 * 4 * 5
factorial(5) = 1 * 1 * 2 * 3 * 4 * 5

用Haskell的Pattern matching 可以很直观的定义factorial函数:

factorial n = factorial (n-1)  * n
factorial 0 = 1

在递归的例子中,从第一个调用factorial(5)开始,一直递归调用factorial函数自身直到参数的值为0。下面是一个形象的图例:

递归的调用栈

为了理解调用栈,我们回到factorial函数的例子。

function factorial(n) {
    if (n === 0) {
        return 1
    }

    return n * factorial(n - 1)
}

如果我们传入参数3,将会递归调用factorial(2)factorial(1)factorial(0),因此会额外再调用factorial三次。

每次函数调用都会压入调用栈,整个调用栈如下:

factorial(0) // 0的阶乘为1 
factorial(1) // 该调用依赖factorial(0)
factorial(2) // 该调用依赖factorial(1)
factorial(3) // 该掉用依赖factorial(2)

现在我们修改代码,插入console.trace()来查看每一次当前的调用栈的状态:

function factorial(n) {
    console.trace()
    if (n === 0) {
        return 1
    }

    return n * factorial(n - 1)
}

factorial(3)

接下来我们看看调用栈是怎样的。 第一个:

Trace
    at factorial (repl:2:9)
    at repl:1:1 // 请忽略以下底层实现细节代码
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)
    at emitOne (events.js:101:20)

你会发现,该调用栈包含一个对factorial函数的调用,这里是factorial(3)。接下来就更加有趣了,我们来看第二次打印出来的调用栈:

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at repl:1:1 // 请忽略以下底层实现细节代码
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)

现在我们有两个对factorial函数的调用。

第三次:

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)

第四次:

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)

设想,如果传入的参数值特别大,那么这个调用栈将会非常之大,最终可能超出调用栈的缓存大小而崩溃导致程序执行失败。那么如何解决这个问题呢?使用尾递归。

尾递归

尾递归是一种递归的写法,可以避免不断的将函数压栈最终导致堆栈溢出。通过设置一个累加参数,并且每一次都将当前的值累加上去,然后递归调用。

我们来看如何改写之前定义factorial函数为尾递归:

function factorial(n, total = 1) {
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)的执行步骤如下:

factorial(3, 1) 
factorial(2, 3) 
factorial(1, 6) 
factorial(0, 6) 

调用栈不再需要多次对factorial进行压栈处理,因为每一个递归调用都不在依赖于上一个递归调用的值。因此,空间的复杂度为o(1)而不是0(n)。

接下来,通过console.trace()函数将调用栈打印出来。

function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)

很惊讶的发现,依然有很多压栈!

// ...
// 下面是最后两次对factorial的调用
Trace
    at factorial (repl:2:9) // 3次压栈
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // 请忽略以下底层实现细节代码
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
Trace
    at factorial (repl:2:9) // 最后第一调用再次压栈
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // 请忽略以下底层实现细节代码
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)

这是为什么呢? 在Nodejs下面,我们可以通过开启strict mode, 并且使用--harmony_tailcalls来开启尾递归(proper tail call)。

'use strict'

function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)

使用如下命令:

node --harmony_tailcalls factorial.js

调用栈信息如下:

Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)

你会发现,不会在每次调用的时候压栈,只有一个factorial

注意:尾递归不一定会将你的代码执行速度提高;相反,可能会变慢。不过,尾递归可以让你使用更少的内存,使你的递归函数更加安全 (前提是你要开启harmony模式)。

那么,博主这里就疑问了:为什么尾递归一定要开启harmony模式才可以呢? 欢迎各位入群讨论。

欢迎加入我们Fundebug全栈BUG监控交流群: 622902485

版权声明: 转载时请注明作者Fundebug以及本文地址: https://blog.fundebug.com/2017/06/14/all-about-recursions/

您的用户遇到BUG了吗?

体验Demo 免费使用

© 著作权归作者所有

Fundebug
粉丝 10
博文 260
码字总数 300763
作品 0
厦门
私信 提问
JavaScript专题之递归

JavaScript 专题系列第十八篇,讲解递归和尾递归 定义 程序调用自身的编程技巧称为递归(recursion)。 阶乘 以阶乘为例: 示意图(图片来自 wwww.penjee.com): 斐波那契数列 在《JavaScript专...

冴羽
2017/09/13
0
0
每个JavaScript工程师都应懂的33个概念

摘要: 基础很重要啊! 原文:33 concepts every JavaScript developer should know 译文:每个 JavaScript 工程师都应懂的33个概念 作者:stephentian Fundebug经授权转载,版权归原作者所有...

Fundebug
2018/10/30
0
0
JavaScript开发者应懂的33个概念

简介 这个项目是为了帮助开发者掌握 JavaScript 概念而创立的。它不是必备,但在未来学习(JavaScript)中,可以作为一篇指南。 本篇文章是参照 @leonardomso 创立,英文版项目地址在这里。 ...

大灰狼的小绵羊哥哥
2018/10/22
0
0
解读 JavaScript 之引擎、运行时和堆栈调用

随着 JavaScript 变得越来越流行,很多团队在他们的堆栈中实现诸多层级的支持 - 前端、后端、混合应用程序、嵌入式设备等等。 本文是该系列文章的第一篇,旨在深入研究 JavaScript 及其实际工...

oschina
2017/12/13
3.6K
0
用 JavaScript 的方式理解递归

原文地址 1. 递归是啥? 递归概念很简单,“自己调用自己”(下面以函数为例)。 在分析递归之前,需要了解下 JavaScript 中“压栈”() 概念。 2. 压栈与出栈 栈是什么?可以理解是在内存中...

hankzhuo
2018/10/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Python爬虫也能用手机进行抓包?没错!这个技巧我只告诉你

今天要说说怎么在我们的手机抓包 我们知道了 HTTP 的请求方式 以及在 Chrome 中摸清了一些套路 但是 除了对数据进行解析之外 有时候我们想 对请求的数据或者响应的数据进行篡改 怎么做呢? ...

计算机编程
11分钟前
0
0
趣图:听说996工作可以获得巨大成长

听说996工作可以获得巨大成长 。 。 。 这成长也忒快了吧 扩展阅读 趣图:菜鸟程序员的工作状态… 趣图:当计算机可以更新的时候 趣图:什么?需求文档又改了

Java面经
14分钟前
2
0
influxdb 学习

InfluxDB 学习 安装 brew install influxdb 启动 influxd -config /usr/local/etc/influxdb.conf 入门 $ influx -precision rfc3339Connected to http://localhost:8086 version 1.2.xI......

solate
20分钟前
1
0
快速掌握mongoDB(三)——mongoDB的索引详解

  1 mongoDB索引的管理      2 mongoDB中常用的索引类型      1 单键索引      2 复合索引      3 多键索引      4 哈希索引      3 mongoDB中常用的索引属性   ...

SEOwhywhy
21分钟前
0
0
JackJson中自定义JsonSerializer的使用

最近在做一个需求,一个时间字段,数据库类型为timestamp,默认值为'1970-01-01 08:00:01',产品要求这种情况展示为“-1”,实体类中的属性类型为Date,我也不能把Date属性值设置为“-1”,又...

Coder顾
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部