大厂面试题分享 面试题库

后端面试题库 （面试必备） 推荐：★★★★★

地址：前端面试题库

递归 Recursion

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

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

概述

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

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

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

能产生递归的条件

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

2. 递归出口：递归考虑有限的问题，出口就是递归调用最后一次调用的出口

递归与循环的区别

循环是满足一定条件，重复执行同一段代码片段。而递归是函数，不断调用自己的行为。常见有 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)；

2. 可通过优化，使得计算仅占用常量栈空间 (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 中封装组件

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

大厂面试题分享 面试题库

后端面试题库 （面试必备） 推荐：★★★★★

地址：前端面试题库