递归简介

递归算法 : 英语：（recursion algorithm）

递归指函数体中直接或间接调用自身的一种方法

在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

递归的两个要素

• 调用自身

• 能跳出循环

递归的问题

1. 由于递归是调用函数自身，而函数调用需要消耗时间和空间：每次调用都要在内存栈中分配空间以存储参数、临时变量、返回地址等，往栈中压入和弹出数据都需要消耗时间。这势必导致执行效率大打折扣。

2. 递归中的计算大都是重复的。本质是把一个问题拆解成多个小问题，他们之间存在互相重叠的部分，这些重复计算也会导致效率降低。

3. 调用栈可能会溢出。栈是有容量限制的，当调用层次过多，就会超出栈的容量限制，从而导致栈溢出！

解决栈溢出的方法一般有尾递归，循环方式，事件循环方式

尾递归的问题

1. 尾递归是一个隐式行为，如果代码存在死循环尾递归调用，爆栈后难以被开发者察觉；堆栈信息会丢失，造成调试困难。

2. 目前各大浏览器厂商对尾递归的支持和兼容性不太好。所以在尾递归目前还不被各大浏览器支持的情况下，可以对递归的一些重复内容做优化

递归的优化策略

1. 时间优化策略：记忆化

解决问题：重复计算

记忆化 是一种优化技术，主要用于加快计算机程序的速度，方法是存储昂贵的函数调用的结果，并在相同的输入再次出现时返回缓存的结果。 (来源: 维基百科)

回到斐波那契函数 ​F(n)​。 我们可以使用哈希表来跟踪每个以 ​n​ 为键的 ​F(n)​ 的结果。 散列表作为一个缓存，可以避免重复计算。 记忆化技术是一个很好的例子，它演示了如何通过增加额外的空间以减少计算时间。

通过记忆化技术，我们保存每个索引 ​n​ 对应的的斐波那契数的结果。我们确信每个斐波那契数的计算只会发生一次。而从递推关系来看，斐波纳契数 ​f(n)​ 将取决于其所有 ​n-1​ 个先验斐波纳契数。结果，计算 ​f(n)​ 的递归将被调用 ​n-1​ 次以计算它所依赖的所有先验数字。

2. 空间优化策略：尾递归

解决问题：递归调用在系统调用栈上会产生额外空间，如果递归调用层级很深，程序执行过程中很可能导致栈溢出。

尾递归函数是递归函数的一种，其中递归调用是递归函数中的最后一条指令。并且在函数中应该只有一次递归调用。

尾递归的好处是，它可以避免递归调用期间栈空间开销的累积，因为系统可以为每个递归调用重用栈中的固定空间。可以理解为，在程序执行到递归函数最后一条递归调用指令时回收了当前的栈空间（其实是复用了当前的栈空间），爽歪歪。

尾递归

尾递归 = 尾调用 + 递归

递归：函数调用自身，称为递归

尾调用：函数最后是调用另一个函数（当一个函数执行时的最后一个步骤是返回另一个函数的调用）

尾递归：一个函数在其内部最后一步调用其自身

尾递归的本质就是不需返回，直接不断向下计算，将每一步计算结果传入下一层，这样最后一层就包含了前面所有层的结果，最后一层的结果就是需要的输出。

非尾递归，下一个函数结束以后此函数还有后续，所以必须保存本身的环境以供处理返回值

递归实例问题

1. 深拷贝

2. 数组扁平化

具有以下特征的问题可考虑递归求解：

1. 当问题和子问题具有递推关系，比如杨辉三角、计算阶乘（后文讨论）。

2. 具有递归性质的数据结构，比如链表、树、图。

3. 反向性问题，比如取反。

阶乘

n! = n*(n-1)

6! = 6 _ 5 _ 4 _ 3 _ 2 *1

n 的阶乘就是从 n 开始依次递减值的积

递归解法：

function factorial(number) {
  if (number === 1) {
    return number;
  } else {
    return number * factorial(number - 1);
  }
}

尾递归解法：

function factorial(number, total) {
  if (number === 1) {
    return total;
  } else {
    return factorial(number - 1, number * total);
  }
}

斐波那契数列

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 求第 n 个数是多少

规律：后一项是前两项的和

function fibonacci(number) {
  if (number <= 2) {
    return 1;
  }
  return fibonacci(number - 1) + fibonacci(number - 2);
}

优化：

// 优化后的递归方式
let mapData = new Map();
function fib(n) {
  if (n == 0 || n == 1) return 1;
  if (mapData.get(n)) {
    //这一步就避免了重复计算
    return mapData.get(n);
  }
  let value = fib(n - 1) + fib(n - 2);
  mapData.set(n, value);
  return value;
}