当前位置: 首页 > news >正文

【面试题】JavaScript中递归的理解

大厂面试题分享 面试题库

后端面试题库 (面试必备) 推荐:★★★★★

地址:前端面试题库

递归 Recursion

To iterate is human, to recurse, divine. 理解迭代,神理解递归。

本文会以 JavaScript为主、有部分 Rust 举例说明。

概述


递归就是程序 函数自己 调用自己。递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

帕斯卡三角: 从递推开始理解


在中国 帕斯卡三角 叫杨辉三角,因为在中国 杨辉三角 的记录比欧洲 帕斯卡三角记录早了几百年。

能产生递归的条件


  1. 调用自身:以最小的函数处理问题,产生的新问题与原问题有着相同的形式。

  1. 递归出口:递归考虑有限的问题,出口就是递归调用最后一次调用的出口

递归与循环的区别


循环是满足一定条件,重复执行同一段代码片段。而递归是函数,不断调用自己的行为。常见有 for-in/for-of 循环,而递归常见的有数学问题:fibonacci 函数。

缺点


  • 耗内存,可以使用尾回调

回溯(Backtrack)


一个递归调用的过程,就是回溯。

回溯是一种算法思想,它是用递归实现的。

用一个比较通俗的说法来解释递归和回溯: 我们在路上走着,前面是一个多岔路口,因为我们并不知道应该走哪条路,所以我们需要尝试。尝试的过程就是一个函数。 我们选择了一个方向,后来发现又有一个多岔路口,这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上,再做一次尝试,即在函数内部再调用一次函数,这就是递归的过程。 这样重复了若干次之后,发现这次选择的这条路走不通,这时候我们知道我们上一个路口选错了,所以我们要回到上一个路口重新选择其他路,这就是回溯的思想。

递归算法 (recursive algorithm)


在递归问题中,使用 JavaScript/Rust 做为示例,有几个经典的问题

  • 数组求和

  • fibonacci 函数

  • JavaScript 中使用递归实现深拷贝

  • React-Router 递归实现配置 routes

  • Vue 中递归组件

经典的 fibonacci 函数示例

  • 经典的 Fibonacci JavaScript 实现

exportdefaultfunctionfibonacci(n) {if (n < 0) thrownewError("输入的数字不能小于 0");if (n === 1 || n === 2) {return1;}returnfibonacci(n - 2) + fibonacci(n - 1);
}const fi = fibonacci(7);
console.log(fi);
复制代码
  • 经典的 Fibonacci Rust 实现(含测试)

fnmain() {println!("Hello, world!");letf1 = fibonacci(1);println!("{}", f1);letf2 = fibonacci(2);println!("{}", f2);letf3 = fibonacci(3);println!("{}", f3);letf4 = fibonacci(4);println!("{}", f4);
}pubfnfibonacci(n: i32) ->u32 {if n < 0 {panic!("输入的数字不能小于 0")};if n == 1 || n == 2 {return1}fibonacci(n - 2) + fibonacci(n - 1)
}#[cfg(test)]mod tests {use crate::fibonacci;#[test]fnfibonacci1() {letresult = fibonacci(1);assert_eq!(result, 1);}#[test]fnfibonacci2() {letresult = fibonacci(2);assert_eq!(result, 1);}#[test]fnfibonacci3() {letresult = fibonacci(3);assert_eq!(result, 2);}
}
复制代码

从求和到递归

// 循环var sum = 0;
for (var i = 1; i <= 10; i++) {sum += i;
}
console.log(sum);// 递归functionsum(n) {if (n == 1) return1;returnsum(n - 1) + n;
}var amount = sum(10);
console.log(amount);
复制代码
fnmain() {println!("Hello, world!");while_sum_fn();
}fnwhile_sum_fn() {letmut sum = 0;letmut i = 0;while i <= 10 {sum += i;i += 1;println!("sum: {}", sum);}println!("{sum}")
}
复制代码

Rust for 循环与 js 中循环有很大的区别,此处 rust 使用 while 语句代替 JavaScript 中的 for 语句。

基础深拷贝

考虑:原始数据类型+引用数据类型

functiondeepClone(target) {const targetType = typeof target;if (targetType === "object" || targetType === "function") {let clone = Array.isArray(target) ? [] : {};for (const key in target) {clone[key] = deepClone(target[key]);}return clone;}return target;
}
复制代码

问题:循环引用(通过内置 weakMap)

function deepClone(target, map = new Map()) {const targetType = typeof target;if (targetType === 'object' || targetType === 'function') {letclone = Array.isArray(target)?[]:{};if (map.get(target)) {return map.get(target);}map.set(target, clone);if(Object.prototype.toString.call(target) === '[object Date]'){clone = new Date(target)}if(Object.prototype.toString.call(target) === '[object Object]' ||Object.prototype.toString.call(target) === '[object Array]'){for (const key in target) {clone[key] = deepClone(target[key],map)}}return clone;}return target;
}
复制代码

然后深拷贝需要考虑众多的 js 的数据类型(包括 es5+ 中新增的数据类型)。深拷贝缺点也非常明显,对于大对象,可能非常占用计算机资源。基于这个特点,React 社区针对 React 和 JavaScript 的诞生了不可变数据库:

  • immer

  • immutable.js

不可变数据,每次修改之后,会得到一个新的数据(但是尽可能的复用了原来的数据),这样弥补了深拷贝的数据时的性能问题。

react router 递归实现配置 route

// 递归函数constrotuerViews = (routerItems) => {if (routerItems && routerItems.length) {return routerItems.map(({ path, Component, children, redirect }) => {return children && children.length ? (<Routepath={path}key={path}element={<Suspensefallback={<Loading />}><Component /></Suspense>}>{rotuerViews(children)} // 递归遍历子路由{redirect ? (<Routepath={path}element={<Navigateto={redirect} />}></Route>) : (<Routepath={path}element={<Navigateto={children[0].path} />}></Route>)}</Route>) : (<Routekey={path}path={path}element={<Suspensefallback={<Loading />}><Component /></Suspense>}></Route>);});}
};
复制代码

vue 中实现 tree 组件的递归(组件中如何使用自己)

<template><ul><li v-for="(item, index) in data" :key="index">{{ item.name }}<template v-if="item.children"><tree :data="item.children"></tree></template></li></ul>
</template><script>
export default {name: "tree",props: {data: {type: Array,default() {return [];},},},
};
</script>
复制代码

扩展:尾部递归(Tail Recursion)


尾递归,首先要搞明白什么是尾部调用? 其实就是发生函数调用后,最后执行的语句是函数调用。尾递归,就是在函数最后(Tail)发生了函数的调用(但是调用的自己,就是尾部递归)。

尾递归在普通尾调用的基础上,多出了2个特征:

  1. 在尾部调用的是函数自身 (Self-called);

  1. 可通过优化,使得计算仅占用常量栈空间 (Stack Space)。

  • 一个实例

functiontailFactorial(n, total) {if (n === 1) return total;returntailFactorial(n - 1, n * total);
}functionfactorial(n) {returntailFactorial(n, 1);
}factorial(5); // 120复制代码

递归非常耗费内存,因为需要同时保存成千上百个调用记录,很容易发生"栈溢出"错误(stack overflow)。但对于尾递归来说,由于只存在一个调用记录,所以永远不会发生"栈溢出"错误。

尾部递归有哪些问题?

空间优化策略:尾递归

递归调用的缺点就是保存的调用栈(call frame),

如何优化尾部递归?

函数发生尾部递归的时候,返回的结果相差不大,保存在栈里面毫无意义。没有意义我们就应该不需要发生这些东西。所以计算机就可以省出一些内容。

递归展开

还是以阶乘为例:

functionfact(n) {if (n <= 0) {return1;} else {return n * fact(n - 1);}
}
复制代码
6 * fact(5)
6 * (5 * fact(4))
6 * (5 * (4 * fact(3))))
6 * (5 * (4 * (3 * (2 * (1 * 1)))))) // <= 最终的展开复制代码

展开的特点是:函数并没有真正的运行,需要较大的内存空间用于展开,如果内容过大就容易爆栈。

尾递归函数依然还是递归函数,如果不优化依然跟普通递归函数一样会爆栈,该展开多少层依旧是展开多少层。不会爆栈是因为语言的编译器或者解释器所做了“尾递归优化”,才让它不会爆栈的。

小结


  • 什么是递归

  • 从杨辉三角可是递推,到递归

  • 递归与循环的区别

  • 递归与回溯

  • 递归算法常见的经典问题以及在前端 ReactRouter/Vue-Tree 中封装组件

  • 尾递归及其优化、递归展开

大厂面试题分享 面试题库

后端面试题库 (面试必备) 推荐:★★★★★

地址:前端面试题库

相关文章:

【面试题】JavaScript中递归的理解

大厂面试题分享 面试题库后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★地址&#xff1a;前端面试题库递归 RecursionTo iterate is human, to recurse, divine. 理解迭代&#xff0c;神理解递归。本文会以 JavaScript为主、有部分 Rust 举例说明。…...

PyTorch学习笔记

PyTorch学习笔记&#xff08;一&#xff09;&#xff1a;PyTorch环境安装 往期学习资料推荐&#xff1a; 1.Pytorch实战笔记_GoAI的博客-CSDN博客 2.Pytorch入门教程_GoAI的博客-CSDN博客 安装参考&#xff1a; 1.视频教程&#xff1a;3分钟深度学习【环境搭建】CUDA Anacon…...

SpringBoot2知识点记录

SpringBoot2知识点记录1.SpringBoot2基础入门1.1 环境要求1.1.1 maven设置1.2 第一个程序 HelloWorld1.2.1 创建maven工程1.2.2 引入依赖1.2.3 创建主程序1.2.4 编写业务1.2.5 测试1.2.6 简化配置1.2.7 简化部署1.3 自动装配1.3.1 SpringBoot特点1.3.1.1 依赖管理1.3.1.2 自动装…...

Mysql

1 Sql编写 count(*) //是对行数目进行计数 count(column_name) //是对列中不为空的行进行计数 SELECT COUNT( DISTINCT id ) FROM tablename; //计算表中id不同的记录有多少条 SELECT DISTINCT id, type FROM tablename; //返回表中id与type同时不同的结果 X.1 连表子查询 sel…...

Q4营收利润增长背后估值持续偏低,全球支付巨头PayPal前景如何?

作为国际版的“支付宝”&#xff0c;全球第三方支付巨头PayPal的业务横跨欧美市场&#xff0c;覆盖了全球200多个国家和地区。同时&#xff0c;PayPal也是首家进军中国支付市场的外资机构&#xff0c;实力强劲。然而&#xff0c;近两年&#xff0c;PayPal的市值一路从3000亿跌至…...

【自然语言处理】【大模型】BLOOM:一个176B参数且可开放获取的多语言模型

BLOOM&#xff1a;一个176B参数且可开放获取的多语言模型《BLOOM: A 176B-Parameter Open-Access Multilingual Language Model》论文地址&#xff1a;https://arxiv.org/pdf/2211.05100.pdf 相关博客 【自然语言处理】【大模型】用于大型Transformer的8-bit矩阵乘法介绍 【自然…...

小红书穿搭博主推广费用是多少?

小红书作为一个种草属性非常强的平台&#xff0c;商业价值是有目共睹的。很多爱美的女性都会在小红书上被种草某个商品&#xff0c;所以很多服装品牌都会在小红书上布局推广。 穿搭作为小红书的顶梁柱类目&#xff0c;刷小红书就能总是看到好看的穿搭博主分享美美的衣服&#…...

网络安全-PHPstudy环境搭建

网络安全-PHPstudy环境搭建 网络搭建我是专家&#xff0c;安全我懂的不多&#xff0c;所以可能很基础。。因为我自己都不懂&#xff0c;都是跟着课程学的 PHPstudy 这个东东是一个在windwos下可以快速部署的web开发环境&#xff0c;安装了就能用&#xff0c;也支持iis和ngin…...

operator的两种用法(重载和隐式类型转换)

文章目录重载隐式类型转换构造函数的隐式类型转换补充operator算子的隐式类型转换重载 略 隐式类型转换 构造函数的隐式类型转换 利用operator进行的隐式类型转换成为operator算子的隐式类型转换&#xff0c;讲这个之前先了解构造函数的隐式类型转换&#xff0c;请看以下代…...

vue常用指令

介绍 vue是以数据驱动和组件化开发为核心的前端框架&#xff0c;可以快速搭建前端应用 常用指令 指令&#xff1a;页面数据的操作&#xff08;以数据去驱动DOM&#xff09; <div v-xxx""></div>v-if&#xff1a;做元素的插入&#xff08;append&…...

MATLAB | 有关数值矩阵、颜色图及颜色列表的技巧整理

这是一篇有关数值矩阵、颜色矩阵、颜色列表的技巧整合&#xff0c;会以随笔的形式想到哪写到哪&#xff0c;可能思绪会比较飘逸请大家见谅&#xff0c;本文大体分为以下几个部分&#xff1a; 数值矩阵用颜色显示从颜色矩阵提取颜色从颜色矩阵中提取数据颜色列表相关函数颜色测…...

C++模板元编程详细教程(之九)

前序文章请看&#xff1a; C模板元编程详细教程&#xff08;之一&#xff09; C模板元编程详细教程&#xff08;之二&#xff09; C模板元编程详细教程&#xff08;之三&#xff09; C模板元编程详细教程&#xff08;之四&#xff09; C模板元编程详细教程&#xff08;之五&…...

PhysioNet2017分类的代码实现

PhysioNet2017数据集介绍可参考文章&#xff1a;https://wendy.blog.csdn.net/article/details/128686196。本文主要介绍利用PhysioNet2017数据集对其进行分类的代码实现。 目录一、数据集预处理二、训练2.1 导入数据集并进行数据裁剪2.2 划分训练集、验证集和测试集2.3 设置训…...

正大期货本周财经大事抢先看

美国1月CPI、Fed 等央行官员谈话 美国1月超强劲的非农就业人口&#xff0c;让投资人开始上修对这波升息循环利率顶点的预测&#xff0c;也使本周二 (14 日) 的美国 1月 CPI 格外受关注。 介绍正大国际期货主账户对比国内期货的优势 ​第一点&#xff1a;权限都在主账户 例如…...

html+css综合练习一

文章目录一、小米注册页面1、要求2、案例图3、实现效果3.1、index.html3.2、style.css二、下午茶页面1、要求2、案例图3、index.html4、style.css三、法国巴黎页面1、要求2、案例图3、index.html4、style.css一、小米注册页面 1、要求 阅读下列说明、效果图&#xff0c;进行静…...

安装jdk8

目录标题一、下载地址&#xff08;一&#xff09;Linux下载&#xff08;二&#xff09;Win下载二、安装&#xff08;一&#xff09;Linux&#xff08;二&#xff09;Win三、卸载&#xff08;一&#xff09;Linux&#xff08;二&#xff09;Win一、下载地址 jdk8最新版 jdk8其他…...

二分法心得

原教程见labuladong 首先&#xff0c;我们建议左右区间全部用闭区间。那么第一个搜索区间&#xff1a;left0; rightlen-1; 进入while循环&#xff0c;结束条件是right<left。 然后求mid&#xff0c;如果nums[mid]的值比target大&#xff0c;说明target在左边&#xff0c;…...

Linux安装Docker完整教程

背景最近接手了几个项目&#xff0c;发现项目的部署基本上都是基于Docker的&#xff0c;幸亏在几年前已经熟悉的Docker的基本使用&#xff0c;没有抓瞎。这两年随着云原生的发展&#xff0c;Docker在云原生中的作用使得它也蓬勃发展起来。今天这篇文章就带大家一起实现一下在Li…...

备份基础知识

备份策略可包括&#xff1a;– 整个数据库&#xff08;整个&#xff09;– 部分数据库&#xff08;部分&#xff09;• 备份类型可指示包含以下项&#xff1a;– 所选文件中的所有数据块&#xff08;完全备份&#xff09;– 只限自以前某次备份以来更改过的信息&#xff08;增量…...

C++学习记录——팔 内存管理

文章目录1、动态内存管理2、内存管理方式operator new operator delete3、new和delete的实现原理1、动态内存管理 C兼容C语言关于内存分配的语法&#xff0c;而添加了C独有的东西。 //int* p1 (int*)malloc(sizeof(int));int* p1 new int;new是一个操作符&#xff0c;C不再需…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...