# 递归

  • 递归是一种应用非常广泛的算法(或者编程技巧)
  • 一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”。基本上,所有的递归问题都可以用递推公式来表示
  • 递归一种计算过程,如果其中每一步都要用到前一步或前几步的结果,称为递归
  • 函数调用自身

递归条件

  • 在每一次调用自己时,必须是(在某种意义上)更接近于解,递归关系式
  • 必须有一个终止处理或计算的准则(递归出口),就是可以直接看出结果,不需要进一步分析

# 递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
  3. 存在递归终止条件

# 如何编写递归代码?

  1. 写出递推公式
  2. 找到终止条件

写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码

注意:

  1. 试图想搞清楚计算机每一步都是怎么执行的,这样就很容易被绕进去
  2. 对于递归代码,这种试图想清楚整个递和归过程的做法,实际上是进入了一个思维误区
  3. 如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险
  4. 递归代码要警惕重复计算

屏蔽掉递归细节

编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤

递归有利有弊,利是递归代码的表达力很强,写起来非常简洁;而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题

  • 所有递归都能改写成迭代循环

# 递归调试

  • log递归值
  • 使用条件断点,对特定值进行调试

# 汉诺塔递归题

汉诺塔

  • 把a中的所有元素移动到c中
  • 一次只能移动一个元素,从塔的上方移除,且只能移动最上层元素
  • 大元素必须在小元素之下,b为辅助使用

代码实现

// 定义初始塔元素,数组下标越小表示越处于塔的上方,10为塔底
const A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
// 定义辅助塔,空数组
const B = []
// 定义最终放置的塔,空数组
const C = []
// 递归函数,i为当前需要移动的块
function move(a, b, c, i = a.length - 1) {
  // a,b塔都没有元素,说明移动完成
  if (!(a.length || b.length)) return c
  // 只有一个
  if (!i) { // 拐点
    // 从a移动最底部块到c
    c.unshift(a.shift())
  } else { // 不止一块则继续递归,寻找出口
    // 第i-1块,从a通过c移动到b
    move(a, c, b, i - 1)
    // 从a移动非最底部块
    c.unshift(a.shift())
    // 第i-1块,从b通过a移动到c
    move(b, a, c, i - 1)
  }
}
move(A, B, C) // 执行移动
console.log(A, B, C) // [],[],[1,2,3,4,5,6,7,8,9,10]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
上次更新: 2020-8-17 23:04:11