资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/JavaScript中的递归

JavaScript中的递归

Jacendfeng / 3010人阅读

摘要：第三次第四次设想，如果传入的参数值特别大，那么这个调用栈将会非常之大，最终可能超出调用栈的缓存大小而崩溃导致程序执行失败。注意尾递归不一定会将你的代码执行速度提高相反，可能会变慢。

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

原文: 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. (/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. (/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. (/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. (/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

Fundebug专注于JavaScript、微信小程序、微信小游戏、支付宝小程序、React Native、Node.js和Java线上应用实时BUG监控。 自从2016年双十一正式上线，Fundebug累计处理了9亿+错误事件，付费客户有Google、360、金山软件、百姓网等众多品牌企业。欢迎大家免费试用！

版权声明

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

云服务器 GPU云服务器 python中的递归 javascript中的 javaScript中的this javascript中的函数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/83572.html

相关文章

  • javascript中的递归

    摘要：二项目中用到的几个经典的递归求的和分析假设递归函数已经写好为，即，就是求的和。递归函数实现每天凌晨定时启动定时器执行代码分析假设递归函数已经写好了。 一、递归的概念 在程序中函数直接或者间接调用自身的一种方法，就叫做递归。它通常把一个大型复杂的问题转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程中所需要的多次重复计算，大大减少了程序的代码了。 二、...

    acrazing 评论0 收藏0

  • JavaScript专题之递归

    摘要：专题系列第十八篇，讲解递归和尾递归定义程序调用自身的编程技巧称为递归。然而非尾调用函数，就会创建多个执行上下文压入执行上下文栈。所以我们只用把阶乘函数改造成一个尾递归形式，就可以避免创建那么多的执行上下文。 JavaScript 专题系列第十八篇，讲解递归和尾递归 定义 程序调用自身的编程技巧称为递归(recursion)。 阶乘 以阶乘为例： function factorial(n...

    asoren 评论0 收藏0

  • ES6函数与Lambda演算

    摘要：高阶函数函数式编程中，接受函数作为参数，或者返回一个函数作为结果的函数通常就被称为高阶函数。均属于高阶函数，高阶函数并不神秘，我们日常编程也会用到。参考演算函数式编程指南入门康托尔哥德尔图灵永恒的金色对角线原文函数与演算 缘起 造了一个轮子，根据GitHub项目地址，生成项目目录树，直观的展现项目结构，以便于介绍项目。欢迎Star。 repository-tree 技术栈： ES6 ...

    fasss 评论0 收藏0

  • 翻译连载 | 第 9 章：递归（上）－《JavaScript轻量级函数式编程》 |《你不知道的JS》

    摘要：一旦我们满足了基本条件值为，我们将不再调用递归函数，只是有效地执行了。递归深谙函数式编程之精髓，最被广泛引证的原因是，在调用栈中，递归把大部分显式状态跟踪换为了隐式状态。 原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者 关于译者：这是一个流淌着沪江血液的纯粹工程：认真，是 HTML 最坚实的梁柱；...

    MasonEast 评论0 收藏0

  • 数据结构和算法类面试题javascript代码实现

    摘要：正文面试题重建二叉树题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。前序遍历序列为，中序遍历序列，。确定了左右子树后递归处理。方法方法面试题在时间删除链表结点。 写在前面 本文的题目均来自于剑指offer中的题目，题目序号保持了书中的题目序号，由于某些题目并不适合于javascript这种语言，所以这些题目就没有写在本篇博客中，因此会出现题目序号的中断。 正文 面试题6：...

    Dean 评论0 收藏0

发表评论

登陆后可评论

0条评论

Jacendfeng

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<