在之前的文章中我们学习了几种常见的数据结构，接下来我们先了解一下递归思想，为我们后面学习树和图奠定一定的基础。
递归
理解递归
递归是一种解决问题的方法。通俗点来讲，其核心思想就是函数自己调用自己，或者间接调用自身。而如果一直调用自己的话，最终会导致栈溢出从而导致程序崩溃，这是程序员不想发生的问题之一。那么要使用递归，就必须遵循的他的一些注意点。首先要注意的是，每个递归函数都有基线条件，也就是不再发生递归的停止点。还有，既然传递值或者函数到栈空间，那么我们就有好习惯，将不用的或者需要的空间进行返回。也可以这样理解，递归其实就是传递和归还。下面一段简单的代码进行展示。
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);//continueunderstandRecursion(false);//continueunderstandRecursion(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);}总结
迭代版本比递归版本快很多，但是递归版本更容易理解，需要的代码通常更少。使用递归有些算法不用，因为尾调用优化会造成多余的内存消耗，甚至可能会被清除。