理解JavaScript递归

什么是递归

程序调用自身的编程技巧称为递归(recursion)

递归的基本思想是将一个复杂的问题分解成更小、更易于管理的子问题,这些子问题与原始问题相似,但规模更小。

递归的要素

  • 基本情况(Base Case):
    这是递归终止的条件,也就是说,当问题足够小,可以直接解决而不需要进一步递归时,就会返回一个直接的答案。

  • 递归步骤(Recursive Step):
    在这一步中,问题被分解成更小的子问题,并且递归地解决这些子问题。每个递归调用都向基本情况更进一步。

递归与循环的比较

递归和循环是实现重复操作的两种基本方法。它们在不同的场景下各有优势。

场景

  • 递归适合解决可以分解为逐渐缩小的子问题的问题。
  • 循环通常用于需要重复执行固定次数的操作,或者在满足特定条件之前重复执行。

性能

  • 递归由于每次调用都会占用新的栈空间,可能会导致栈溢出,特别是在深度递归时。此外,递归的执行效率通常低于循环,因为它涉及更多的函数调用开销。
  • 循环通常更高效,因为它避免了函数调用的开销,并且可以更直接地控制循环的次数。

限制

  • 递归需要有明确的终止条件,否则会导致无限递归。
  • 循环也需要有明确的终止条件,否则也可能导致无限循环。

阶乘

递归实现阶乘:

基本情况:
基本情况就是结束条件,这可以有很多,比如:
n = 1 时,返回 1

n = 2 时,返回 2 (1 * 2

n = 3 时,返回 6 (1 * 2 * 3

我们使用最简单的结束条件:
n = 1 时,返回 1

递归步骤:
每次递归调用时,都会将之前的结果乘以当前数字,然后返回结果。

实现:

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

console.log(factorial(5)); // 5 * 4 * 3 * 2 * 1 = 120

通过下图,可以看出这个递归函数的实现原理:

循环实现阶乘:

function factorial(n) {
  let result = 1; 

  for (let i = 2; i <= n; i++) {
    result *= i;
  }

  return result;
}

console.log(factorial(5)); // 输出: 120

斐波那契数列

斐波那契数列是一个特殊的数列,其中每个数都是前两个数的和。

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

下来我们实现一个函数,返回斐波那契数列的第 n 个数。

斐波那契数列的递归实现:

基本情况:

如果 n01 ,直接返回 n

递归步骤:

每次递归调用都返回前两个数的和。

实现:

function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 计算第6项斐波那契数
console.log(fibonacci(6)); // 输出: 8

斐波那契数列的循环实现:

function fibonacci(n) {
  // 初始化数组,包含前两项
  let fib = [1, 1];

  for (let i = 2; i < n; i++) {
    // 计算当前项,即前两项的和
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  return fib[n - 1];
}

// 计算第6项斐波那契数
console.log(fibonacci(6)); // 输出: 8

尾递归

我们看这个斐波那契数列的递归实现,他的函数调用次数要比循环次数多很多。我们打印出来看下。

let count = 0;
function fibonacci(n) {
  count++;
  if (n === 0) return 0;
  if (n === 1) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 计算第6项斐波那契数
console.log(fibonacci(6)); // 输出: 8
console.log(`调用 ${count}`); // 输出: 调用 25 次

函数执行一次,就会创建一个执行上下文,并且压入执行上下文栈,当函数执行完毕的时候,就会将函数的执行上下文从栈中弹出。我们这个递归函数,创建很多执行上下文压入执行上下文栈。

递归次数过多还会导致栈溢出。

chrome 浏览器的 Sources 面板中,我们通过 Call Stack 可以看到执行上下文的函数调用栈的具体情况

下来我们开始使用尾递归优化这个递归函数。

尾递归是指递归函数内部的最后一个动作是函数调用。该调用的返回值,直接返回给函数。
这样就可以避免创建新的栈帧。

我们直接将上一次的结果,作为参数传递给下一次的函数调用。

function fibonacci(n, ac1 = 1, ac2 = 1) {
  if (n == 1 || n == 2) {
    return ac2;
  }

  return fibonacci(n - 1, ac2, ac1 + ac2);
}

// 计算第6项斐波那契数
console.log(fibonacci(6)); // 输出: 8

注意:
上面的 fibonacci 函数虽然已经使用了尾递归优化,但还是可能出现栈溢出。

因为 JavaScript 引擎并不总是能够优化尾递归调用以避免栈溢出。这是因为尾递归优化( Tail Call Optimization , TCO )并不是 JavaScript 语言规范的一部分,也不是所有 JavaScript 引擎都实现了这一优化。

在没有 TCO 的环境中,每次递归调用仍然会占用新的栈空间,fibonacci 函数的每次调用都需要保留其执行上下文(包括参数和局部变量),直到该调用的返回值被使用。随着 n 的增加,递归调用的深度也会增加,这最终可能导致栈溢出。

递归应用的业务场景

数组转树

比如在做权限控制、级联选择组件的时候,后端返回的数据可能是数组,前端需要将其转换为树形结构。这时可以使用递归来解决。

JavaScript 实现扁平数组与树结构的相互转换

递归组件

在 Vue 中,递归组件是一种可以调用自身作为其子组件的组件。递归组件非常适合用来展示嵌套的或者树状的数据结构,例如文件系统、组织结构图、菜单列表等。

在做侧边栏可能有多个层级的时候,可以使用递归组件。

vue-element-admin 项目中的 SidebarItem 组件 就是使用了递归组件。

总结

使用递归解决问题,重点是如果把问题分解为更小的相同问题,确定递归终止条件,然后递归调用自身。
使用递归要注意栈溢出问题,可以考虑使用尾递归优化。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/615541.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

BIERv6测试解析— 如何使用仪表进行转发性能测试

什么是BIERv6 BIERv6&#xff08;Bit Index Explicit Replication IPv6 encapsulation&#xff09;是一种新型组播方案。 BIERv6使用比特串封装目的节点集合&#xff0c;无需建立组播分发树或保存流状态&#xff0c;简化了网络节点操作。它与SRv6无缝融合&#xff0c;高效承载…

靠谱的知识竞赛活动公司怎么去找

搞知识竞赛活动&#xff0c;找一家靠谱的知识竞赛活动公司来承办是重中之重&#xff0c;他直接决定了竞赛活动的成败和效果。那么&#xff0c;如何去找这样一家公司呢&#xff1f; 知识竞赛活动一般包括两大部分内容&#xff0c;一部分是舞台及其包装&#xff0c;另一部分是知识…

python实现九宫格图片切割

欢迎关注我👆,收藏下次不迷路┗|`O′|┛ 嗷~~ 目录 一.前言 二.代码 三.使用 四.分析 一.前言 朋友圈九宫格是一种在社交媒体上展示图片或内容的常见布局方式,特别是在微信朋友圈中非常流行。这种布局由九个相同大小的格子组成,通常用于展示一组相关的图片或内容。&…

ESP32-C3-MINI-1

https://www.espressif.com.cn/sites/default/files/documentation/esp32-c3-mini-1_datasheet_cn.pdf 芯片 https://files.seeedstudio.com/wiki/XIAO_WiFi/Resources/esp32-c3_datasheet.pdf 结果参考&#xff1a; https://blog.csdn.net/iamxxdd/article/details/12386419…

Html + Express 实现大文件分片上传、断点续传、秒传

在日常的网页开发中&#xff0c;文件上传是一项常见操作。通过文件上传技术&#xff0c;用户可以将本地文件方便地传输到Web服务器上。这种功能在许多场景下都是必不可少的&#xff0c;比如上传文件到网盘或上传用户头像等。 然而&#xff0c;当需要上传大型文件时&#xff0c;…

人工智能的未来:Sam Altman 揭穿搜索引擎谣言,调侃 ChatGPT 和 GPT-4 的“神奇”更新

人工智能的未来&#xff1a;Sam Altman 揭穿搜索引擎谣言&#xff0c;调侃 ChatGPT 和 GPT-4 的“神奇”更新 概述 科技界充斥着有关人工智能研究先驱组织 OpenAI 将推出类似谷歌搜索引擎的传言。然而&#xff0c;首席执行官 Sam Altman 已经平息了这些谣言&#xff0c;并透露…

机器学习:葡萄酒品质预测

说明&#xff0c;此项目是我的期末大作业&#xff0c;包括了对数据集探索&#xff0c;预处理以及分类的各个详细过程与描述&#xff0c;代码简单&#xff0c;主要是一个分类项目的流程&#xff0c;并没有对模型进行深度研究&#xff0c;因此我写在这里。 目录 一、问题介绍 …

【Win10点击任务栏刷屏,卡死转圈(亲测有效)】

计算机疑难杂症001 Win10点击任务栏刷屏&#xff0c;卡死转圈(亲测有效)1、问题状况2、问题原因3、问题解决 Win10点击任务栏刷屏&#xff0c;卡死转圈(亲测有效) 1、问题状况 在偶然间&#xff0c;发现任务栏点不动了&#xff0c;点击无反应&#xff0c;再多点击几次&#x…

.[sqlback@memeware.net].2700勒索病毒如何防护和恢复数据?

.[sqlbackmemeware.net].2700介绍&#xff1a; .[sqlbackmemeware.net].2700 勒索病毒是一种恶意软件&#xff0c;它通过加密用户文件并索要赎金来实施勒索&#xff0c;快速恢复重要数据请添加技术服务号(safe130)。以下是关于这种勒索病毒的一些关键信息&#xff1a; 病毒性质…

通用人工智能AGI,究竟是一个哲学问题还是技术问题?

引言 在探索人工智能的未来方向中&#xff0c;人工通用智能&#xff08;AGI&#xff09;的概念逐渐成为科技领域和哲学探讨的焦点。AGI旨在创建可以执行任何智能任务的机器&#xff0c;甚至在某些方面超越人类的能力。然而&#xff0c;关于AGI的研究不仅仅是技术问题&#xff…

Rust读写CSV文件 一维Vec类型元素、二维Vec类型元素写入CSV文件

本文主要介绍Rust读写CSV文件方法&#xff0c; Vec类型元素基本操作方法&#xff0c;Rust把一维Vec类型元素、二维Vec类型元素写入CSV文件方法。 实例测试&#xff1a; 要求读“log.csv”文件数据&#xff0c;把“时间”列数据和“次数”列数据写入日志处理结果1.csv文件&…

C++相关概念和易错语法(12)(迭代器、string容量调整)

1.迭代器&#xff08;以string为例&#xff09; &#xff08;1&#xff09;基本理解&#xff1a;在我们刚接触迭代器的时候&#xff0c;我们可以将迭代器理解为改造过的“指针”&#xff0c;这是一个新的类型&#xff0c;指向对应容器中的各个元素。我们可以像指针那样对迭代器…

算法详解——回溯法

一、回溯法概述——问题背景 回溯法是一种解决约束满足问题的方法&#xff0c;特别适用于解决组合问题、搜索优化问题等。它通过逐步构建候选解决方案并且在这个解决方案不再可能满足约束或条件时进行剪枝和回溯。具体来说&#xff0c;回溯法可以应用于以下类型的问题&#xff…

Windows10搭建GPU版Darknet—yolov4—VS2022+CUDA+CUDNN(亲测有效)

1 VS2019安装 网址&#xff1a;Visual Studio: 面向软件开发人员和 Teams 的 IDE 和代码编辑器 下载完成之后双击.exe文件 步骤严格如下安装 默认语音包为中文&#xff08;简体&#xff09; 安装位置可以自行选择&#xff0c;完成以后就可以点击安装了。 安装完毕以后需要重启…

如何设置cPanel的自动备份

近期我们购买了Hostease美国VPS云主机产品&#xff0c;由于需要设置服务器的自动备份&#xff0c;我们向Hostease技术团队进行了咨询&#xff0c;他们提到VPS云主机的cPanel面板包含自动备份功能&#xff0c;下面我们就介绍如何进行自动备份的设置。 首先你需要登录到WHM面板&a…

暗区突围PC测试资格获取教程 人人可领100%获取方法

暗区突围PC测试资格获取教程 人人可领100%获取方法 暗区突围国际服的上线&#xff0c;近日在游戏圈内掀起了不小的浪花。而一个暗区突围国际服的测试资格更是成为了玩家们眼中炙手可热的宝物。许多玩家不知道该如何获取游戏的测试资格&#xff0c;今天小编就为大家带来详细的教…

电脑复制和粘贴的时候会出现Hello!

电脑不管是Microsoft Excel还是Microsoft Word复制之后粘贴过来就出现HELLO&#xff0c;当复制粘贴文件的时候就会出现WINFILE&#xff1b; 具体现象看下面两个图片&#xff1a; 这是因为winfile 文件病毒&#xff08;幽灵蠕虫病毒&#xff09;,每月的28号发作&#xff1b; 症状…

【深度学习】YOLO源码中的mAP计算代码的理解笔记(大部分代码逐行+基础解释)

提示&#xff1a;本篇博客是在阅读了YOLO源码中的mAP计算方法的代码后加上官方解释以及自己的debug调试理解每一步是怎么操作的。由于是大部分代码进行了逐行解释&#xff0c;所以篇幅过长。 文章目录 前言一、输入格式处理1.1 转换公式二、init&#xff1a;初始化2.1 iouv2.2 …

2024版本idea集成SpringBoot + Ai 手写一个chatgpt 【推荐】

题目&#xff1a;SpringBoot OpenAi 在这里获取key和url&#xff1a;获取免费key base-url为这两个&#xff1a; 话不多说直接来&#xff01; 一、简介 Spring AI 是 AI 工程的应用框架。其目标是将 Spring 生态系统设计原则&#xff08;如可移植性和模块化设计&#xff…

【CAD建模号】学习笔记(四):工作平面

工作平面介绍 CAD建模号右侧导航栏提供了很多便捷的工具&#xff0c;有测量工具、坐标系、模型和图层切换、视图切换等。 1. 测量工具组 测量工具可以测量图形的几何体积&#xff0c;长度&#xff0c;角度等。工具组包含如下&#xff1a; 测量几何&#xff1a;可以测量图形的面…