JavaScript 中递归

递归 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 实现
export default function fibonacci(n) {
 if (n < 0) throw new Error("输入的数字不能小于 0");
 if (n === 1 || n === 2) {
 return 1;
 }
 return fibonacci(n - 2) + fibonacci(n - 1);
}
const fi = fibonacci(7);
console.log(fi);
  • 经典的 Fibonacci Rust 实现(含测试)
fn main() {
 println!("Hello, world!");
 let f1 = fibonacci(1);
 println!("{}", f1);
 let f2 = fibonacci(2);
 println!("{}", f2);
 let f3 = fibonacci(3);
 println!("{}", f3);
 let f4 = fibonacci(4);
 println!("{}", f4);
}
pub fn fibonacci(n: i32) -> u32 {
 if n < 0 {
 panic!("输入的数字不能小于 0")
 };
 if n == 1 || n == 2 {
 return 1
 }
 fibonacci(n - 2) + fibonacci(n - 1)
}
#[cfg(test)]
mod tests {
 use crate::fibonacci;
 #[test]
 fn fibonacci1() {
 let result = fibonacci(1);
 assert_eq!(result, 1);
 }
 #[test]
 fn fibonacci2() {
 let result = fibonacci(2);
 assert_eq!(result, 1);
 }
 #[test]
 fn fibonacci3() {
 let result = fibonacci(3);
 assert_eq!(result, 2);
 }
}

从求和到递归

// 循环
var sum = 0;
for (var i = 1; i <= 10; i++) {
 sum += i;
}
console.log(sum);
// 递归
function sum(n) {
 if (n == 1) return 1;
 return sum(n - 1) + n;
}
var amount = sum(10);
console.log(amount);
fn main() {
 println!("Hello, world!");
 while_sum_fn();
}
fn while_sum_fn() {
 let mut sum = 0;
 let mut i = 0;
 while i <= 10 {
 sum += i;
 i += 1;
 println!("sum: {}", sum);
 }
 println!("{sum}")
}

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

基础深拷贝

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

function deepClone(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') {
 let clone = 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

// 递归函数
const rotuerViews = (routerItems) => {
 if (routerItems && routerItems.length) {
 return routerItems.map(({ path, Component, children, redirect }) => {
 return children && children.length ? (
 <Route
 path={path}
 key={path}
 element={
 <Suspense fallback={<Loading />}>
 <Component />
 </Suspense>
 }
 >
 {rotuerViews(children)} // 递归遍历子路由
 {redirect ? (
 <Route path={path} element={<Navigate to={redirect} />}></Route>
 ) : (
 <Route
 path={path}
 element={<Navigate to={children[0].path} />}
 ></Route>
 )}
 </Route>
 ) : (
 <Route
 key={path}
 path={path}
 element={
 <Suspense fallback={<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)。
  • 一个实例
function tailFactorial(n, total) {
 if (n === 1) return total;
 return tailFactorial(n - 1, n * total);
}
function factorial(n) {
 return tailFactorial(n, 1);
}
factorial(5); // 120

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

尾部递归有哪些问题?

空间优化策略:尾递归

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

如何优化尾部递归?

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

递归展开

还是以阶乘为例:

function fact(n) {
 if (n <= 0) {
 return 1;
 } 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 中封装组件
  • 尾递归及其优化、递归展开

参考

  • 简单介绍递归算法以及应用场景[0]
  • 递归使用场景[1]
  • 递归算法[2]
  • Javascript 中递归的使用方法[3]
  • 尾调用优化[4]
  • 面试官:说一说递归如何优化-尾递归优化[5]
  • 尾递归为啥能优化?[6]
  • 如何写递归[7]

引用

1.https://www.cnblogs.com/hands...
2.https://www.cnblogs.com/Shine...
3.https://zhuanlan.zhihu.com/p/...
4.https://developer.aliyun.com/...
5.http://ruanyifeng.com/blog/20...
6.https://cloud.tencent.com/dev...
7.https://zhuanlan.zhihu.com/p/...
8.https://leetcode.cn/circle/ar...

作者:magnesium原文地址:https://segmentfault.com/a/1190000043395498

%s 个评论

要回复文章请先登录注册