b2科目四模拟试题多少题驾考考爆了怎么补救
b2科目四模拟试题多少题 驾考考爆了怎么补救
首页 > 操作系统 >

JavaScript中的递归

电脑杂谈　 发布时间：2020-05-09 23:02:02　 来源：网络整理

c函数的递归调用_递归调用_递归 2次调用

译者注: 程序员应该知道递归，但是您真的知道发生了什么吗？

为确保可读性，本文使用免费翻译而非文字翻译.

过程或函数具有在其定义或描述中直接或间接调用自身的方法. 它通常将一个大而复杂的问题转换为一个较小的问题，类似于要解决的原始问题. 递归策略只需要少量程序来描述解决该问题所需的重复计算，从而大大减少了代码量. 程序.

让我们举个例子. 我们可以使用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的模式匹配可以直观地定义阶乘函数:

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

在递归示例中，从第一次调用阶乘（5）递归 2次调用，递归调用阶乘函数本身，直到参数值为0. 以下是图像的图例:

为了理解调用堆栈递归 2次调用，我们返回阶乘函数的示例.

c函数的递归调用_递归 2次调用_递归调用

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

如果传入参数3，则将递归调用阶乘（2），阶乘（1）和阶乘（0），因此将再次调用阶乘3次.

每个函数调用将被推入调用堆栈，整个调用堆栈如下:

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)

您会发现调用堆栈包含对阶乘函数的调用，在本例中为阶乘（3）. 接下来更有趣，让我们来看第二遍打印的调用堆栈:

递归调用_c函数的递归调用_递归 2次调用

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)

现在我们有两个对阶乘函数的调用.

第三次:

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)

想象一下，如果传入的参数值特别大，则调用栈将非常大，并且最终可能会超出调用栈缓存的大小并崩溃，从而导致程序执行失败. 那么如何解决这个问题呢？使用尾递归.

尾部递归是一种递归编写方式，可以避免在栈上连续推入函数并最终导致栈溢出. 通过设置累加参数并每次累加当前值，然后递归调用它.

让我们看看如何在重写之前重写定义为尾递归的阶乘函数:

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

c函数的递归调用_递归 2次调用_递归调用

阶乘（3）的执行步骤如下:

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

调用堆栈不再需要多次推送阶乘，因为每个递归调用都不依赖于先前递归调用的值. 因此，空间的复杂度是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)

这是为什么？

在Node.js下，我们可以启用严格模式，并使用--harmony_tailcalls启用尾部递归.

'use strict'
function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }
    return factorial(n - 1, n * total)
}
factorial(3)

递归 2次调用_c函数的递归调用_递归调用

使用以下命令:

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)

您会发现只有一个阶乘，而不是在每次调用时都压入堆栈.

注意: 尾递归并不一定会提高代码执行速度. 反之 ，. 但是，尾部递归允许您使用更少的内存，并使递归函数更安全（前提是您启用了和声模式）.

因此，博客作者在这里有一个问题: 为什么必须在和声模式下启用尾递归？

Fundebug专注于JavaScript，微信小程序，微信小游戏，支付宝小程序，React Native，Node.js和Java实时BUG监视. 自2016年“双十一”正式推出以来，Fundebug总共处理了7亿多个错误事件，并得到了Google，360，金山词霸和People.com等许多知名用户的认可. 欢迎免费试用！

转载时，请注明作者Fundebug和本文的地址:


本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-204593-1.html

    相关阅读
      发表评论　　请自觉遵守互联网相关的政策法规，严禁发布、暴力、反动的言论

      • 李姣
        李姣

        一头黑发特别有神

        2026年06月03日 回复 顶 转发
      • 马祺
        马祺

        何来公信力

        2026年06月03日 回复 顶 转发
      • 巨梦迪
        巨梦迪

        显然一个统一的中华民族必然比目前的分裂状态下的内耗更好

        2026年06月03日 回复 顶 转发
      每日福利
      无评论费无评论费 关于JAVA Applet中数字安全证书的实现关于JAVA Applet中数字安全证书的实现 2008年2月编程语言排名2008年2月编程语言排名 win7系统只有一个磁盘没有其他硬盘的解决办法win7系统只有一个磁盘没有其他硬盘的解决办法
      热点图片
      拼命载入中...
      热点排行