JavaScript数据结构与算法（八）递归

arashicage 发布于2019-08-26 14:04 / 2944人阅读

摘要：在之前的文章中我们学习了几种常见的数据结构，接下来我们先了解一下递归思想，为我们后面学习树和图奠定一定的基础。而如果一直调用自己的话，最终会导致栈溢出从而导致程序崩溃，这是程序员不想发生的问题之一。

在之前的文章中我们学习了几种常见的数据结构，接下来我们先了解一下递归思想，为我们后面学习树和图奠定一定的基础。

递归 理解递归

递归是一种解决问题的方法。通俗点来讲，其核心思想就是函数自己调用自己，或者间接调用自身。而如果一直调用自己的话，最终会导致栈溢出从而导致程序崩溃，这是程序员不想发生的问题之一。那么要使用递归，就必须遵循的他的一些注意点。首先要注意的是，每个递归函数都有基线条件，也就是不再发生递归的停止点。还有，既然传递值或者函数到栈空间，那么我们就有好习惯，将不用的或者需要的空间进行返回。也可以这样理解，递归其实就是传递和归还。下面一段简单的代码进行展示。

function understandRecursion(doIunderstandRecursion) {
  const recursionAnswer = confirm("Do you understand recursion?"); // function logic
  if (recursionAnswer === true) { // base case or stop point
    return true;
  }
  understandRecursion(recursionAnswer); // recursive call
}

understandRecursion(false);//continue
understandRecursion(false);//continue
understandRecursion(true);//stop

一些经典递归算法 阶乘

普通迭代实现

function factorialIterative(number) {
  if (number < 0) {
    return undefined;
  }
  let total = 1;
  for (let n = number; n > 1; n--) {
    total  = total * n;
  }
  return total;
}

递归实现

function factorial(n) {
    // console.trace();
    if (n === 1 || n === 0) {
      return 1;
    }
  return n * factorial(n - 1);
}

值得注意的是，由于操作系统和浏览器的不同，提供的栈空间不同，也就是栈溢出发生时函数的执行次数不同，并且在ES6中提供的是尾调用优化，函数内最后一个操作是调用函数时，会通过跳转指令jump而不是子程序调用，导致程序可以一直进行。所以在这里，基线条件是万万不能忘了添加的。

斐波那契数列

迭代实现

function fibonacciIterative(n){
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) { // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

递归实现

function fibonacciIterative(n){
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) { // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

记忆化斐波那契数列

function fibonacciMemoization(n) {
  const memo = [0, 1];
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n];
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  };
  return fibonacci(n);
}

总结

迭代版本比递归版本快很多，但是递归版本更容易理解，需要的代码通常更少。使用递归有些算法不用，因为尾调用优化会造成多余的内存消耗，甚至可能会被清除。

GPU云服务器云服务器最大值算法递归 java递归算法树 java 树递归算法背包算法 c语言递归

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109980.html

数据结构与算法之精讲「递归系列」

摘要：终止条件递推公式递归的分类通过做大量的题，根据递归解决不同的问题，引申出来的几种解决和思考的方式。我们通过层与层之间的计算关系用递推公式表达出来做计算，经过层层的递归，最终得到结果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言几个月之前就想写这样一篇文章分享给大家，由于自己有心而力不足，没有把真...

zhichangterry 2019-08-26 13:50 评论0 收藏0
排序算法 JavaScript

摘要：一冒泡排序算法介绍比较相邻的两个元素如果前一个比后一个大，则交换位置。它与冒泡排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。一、冒泡排序算法介绍：比较相邻的两个元素,如果前一个比后一个大，则交换位置。第一轮把最大的元素放到了最后面。由于每次排序最后一个都是最大的，...

Charlie_Jade 2019-08-23 15:18 评论0 收藏0
八皇后，回溯与递归（Python实现）

摘要：八皇后问题是十九世纪著名的数学家高斯年提出。同时可以扩展为九皇后，十皇后问题。解决方案回溯与递归。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。八皇后问题是十九世纪著名的数学家高斯1850年提出。以下为python语言的八皇后代码，摘自《Python基础教程》，代码相对于其他语言，来得短小且一次性可以打印出92种结果。...

TZLLOG 2019-07-31 10:07 评论0 收藏0
动态规划法（八）最大子数组问题（maximum subarray problem）

摘要：动态规划法用表示最大子数组的结束下标为的情形，则对于，有这样就有了一个子结构，对于初始情形，遍历就能得到这个数组，其最大者即可最大子数组的和。动态规划法想法巧妙，运行效率也高，但是没有普遍的适用性。问题简介本文将介绍计算机算法中的经典问题——最大子数组问题（maximum subarray problem）。所谓的最大子数组问题，指的是：给定一个数组A，寻找A的和最大的非空连续...

jzman 2019-07-30 16:46 评论0 收藏0
算法思想

摘要：基础算法思想类别递推枚举递归分治贪婪回溯试探模拟递推递推分类顺推法从已知条件出发，逐步推算出要解决问题的方法。贪心算法的局限不能保证最后的解是最优的不能求最大最小解问题只能求满足某些约束条件的可行解范围。基础算法思想类别递推枚举递归分治贪婪回溯（试探）模拟递推递推分类顺推法：从已知条件出发，逐步推算出要解决问题的方法。逆推法：从已知结果出发，用迭代表达式...

sshe 2019-08-15 17:50 评论0 收藏0