递归

常见的算法思维：

1. 分治法
2. 迭代法
3. 枚举法
4. 回溯法
5. 贪心算法
6. 动态规划

递归是典型的分治的思想。

🙋什么是递归？

回答：一种特殊形式的调用形式，指的是函数自己调用自己的形式。

递归代码示例：

function a() {
  a()
}
a()

上面的代码就是一个递归的例子，只不过该例子是一个死递归。

为什么觉得难☹️

因为递归属于函数式编程，函数式编程是另外一种编程范式。大家平时习惯的是命令式编程。

因为编程范式不一样，有些核心的思想都不同了。例如在函数式编程里面，常见概念：纯函数（没有副作用的函数）、高阶函数、不可变数据、递归…

书写递归诀窍

1. 委托的思想：一个递归函数，告诉你是什么功能，你就不要想内部怎么实现的，反正委托给它，它就能给你正确的结果。
2. 设计出口：什么时候是递归的终点，一旦没有设计出口，就会变成死递归。

求 n 的阶乘：n _ (n - 1) _ (n-2) _ … _ 1

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

5! ---> 5 * 4!
4! ---> 4 * 3!
3! ---> 3 * 2!
2! ---> 2 * 1!
1! ---> 1(出口)

f(n) // 返回 n 的阶乘

function f(n) {
  // 出口非常重要，不会再继续往下调用了。
  if (n === 1) {
    return 1
  }
  return n * f(n - 1)
}

课堂练习

1. 斐波那契数列

0 1 1 2 3 5 8 13 21...

// 求出指定位数的斐波那契数
f(1) ---> 0
f(5) ---> 3
f(位数) ---> 对应位数的斐波那契数

function f(n) {
  // 设计出口
  if (n === 1) {
    return 0
  } else if (n === 2) {
    return 1
  } else {
    return f(n - 1) + f(n - 2)
  }
}

2. 实现一个 sum 函数，该函数接收 2 个参数，返回从第一个参数加到第二个参数的和。

sum(1, 100) ---> 1 + 2 + 3 + 4 + ... + 99 + 100
sum(1, 99) ---> 返回从 1 加到 99 的和

• 委托的思想：假设传入的是 1 和 100，计算从 1 加到 100，从 1 加到 100 等价于 100 + 1 加到 99 的和，从 1 加到 99 等价于 99 + 从1 加到 98
• 设计出口：出口就是两个数相等的时候，例如从 1 加到 1，返回的就是 1；从 50 加到 50，返回的就是 50

function sum(m, n) {
  if (m === n) {
    return m
  }
  return n + sum(m, n - 1)
}

-EOF-