递归 Recursion

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

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

概述

递归便是程序 函数自己 调用自己。递归需求有边界条件、递归前进段和递归回来段。当边界条件不满意时，递归前进；当边界条件满意时，递归回来。

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

JavaScript中递归

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

能产生递归的条件

  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 中封装组件
  • 尾递归及其优化、递归打开

参阅

  • 简单介绍递归算法以及运用场景
  • 递归运用场景
  • 递归算法
  • Javascript 中递归的运用方法
  • 尾调用优化
  • 面试官：说一说递归怎么优化-尾递归优化
  • 尾递归为啥能优化？
  • 怎么写递归