关于javascript:JavaScript-中递归

40次阅读

共计 5042 个字符，预计需要花费 13 分钟才能阅读完成。

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

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

递归就是程序 函数本人 调用本人。递归须要 有边界条件 、 递归后退段 和递归返回段。当边界条件不满足时，递归后退；当边界条件满足时，递归返回。

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

调用本身：以最小的函数解决问题，产生的新问题与原问题有着雷同的模式。
递归进口：递归思考无限的问题，进口就是递归调用最初一次调用的进口

循环是满足肯定条件，反复执行同一段代码片段。而递归是函数，一直调用本人的行为。常见有 for-in/for-of 循环，而递归常见的有数学问题：fibonacci 函数。

耗内存，能够应用尾回调

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

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

用一个比拟艰深的说法来解释递归和回溯：
咱们在路上走着，后面是一个多岔路口，因为咱们并不知道应该走哪条路，所以咱们须要尝试。尝试的过程就是一个函数。
咱们抉择了一个方向，起初发现又有一个多岔路口，这时候又须要进行一次抉择。所以咱们须要在上一次尝试后果的根底上，再做一次尝试，即在函数外部再调用一次函数，这就是递归的过程。
这样反复了若干次之后，发现这次抉择的这条路走不通，这时候咱们晓得咱们上一个路口选错了，所以咱们要回到上一个路口从新抉择其余路，这就是回溯的思维。

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

数组 求和
fibonacci 函数
JavaScript 中应用递归实现 深拷贝
React-Router 递归实现配置 routes
Vue 中递归组件

经典的 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

不可变数据，每次批改之后，会失去一个新的数据（然而尽可能的复用了原来的数据），这样补救了深拷贝的数据时的性能问题。

// 递归函数
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>
      );
    });
  }
};

<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）产生了函数的调用（然而调用的本人，就是尾部递归）。

尾递归在一般尾调用的根底上，多出了 2 个特色：

在尾部调用的是函数本身 (Self-called)；
可通过优化，使得计算仅占用常量栈空间 (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…

正文完

javascript

发表至： javascript

2023-02-07

0

String的所有方法，属性总结

React关于父组件传prop值给子组件的state时子组件state无法实时更新的解决方案

Web技术的前世今生（三）

关于javascript:大前端进阶flow类型检查

关于api:什么三体海报可以自己画

关于javascript:JavaScript-中递归

递归 Recursion

概述

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

能产生递归的条件

递归与循环的区别

毛病

回溯（Backtrack）

递归算法（recursive algorithm）

经典的 fibonacci 函数示例

从求和到递归

根底深拷贝

react router 递归实现配置 route

vue 中实现 tree 组件的递归（组件中如何应用本人）

扩大：尾部递归(Tail Recursion)

尾部递归有哪些问题？

如何优化尾部递归？

递归开展

小结

参考

援用

Just My Socks（注册教程内含优惠码）

关于javascript:JavaScript-中递归

递归 Recursion

概述

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

能产生递归的条件

递归与循环的区别

毛病

回溯（Backtrack）

递归算法（recursive algorithm）

经典的 fibonacci 函数示例

从求和到递归

根底深拷贝

react router 递归实现配置 route

vue 中实现 tree 组件的递归（组件中如何应用本人）

扩大：尾部递归(Tail Recursion)

尾部递归有哪些问题？

如何优化尾部递归？

递归开展

小结

参考

援用

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）