1
2
|
“要理解递归，首先要理解递归。”
——佚名
|
递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。递归通常涉及函数调用自身。
概念就这么简单，那么直接上手实战试试。
数 n 的阶乘，定义为 n!，表示从1到n的整数的乘积。
5 的阶乘表示为 5!，和 5 × 4 × 3 × 2 × 1 相等，结果是 120。
1
2
3
4
5
6
7
8
9
|
function factorialIterative(number) {
if (number < 0) return undefined;
let total = 1;
for (let n = number; n > 1; n--) {
total = total * n;
}
return total;
}
console.log(factorialIterative(5));
|
斐波那契数列#
斐波那契数列是另一个可以用递归解决的问题。它是一个由 0、1、1、2、3、5、8、13、21、34 等数组成的序列。数 2 由 1 + 1 得到，数 3 由 1 + 2 得到，数 5 由 2 + 3 得到，以此类推。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
function fibonacciIterative(n) {
if (n < 1) return 0;
if (n <= 2) return 1;
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;
}
|
会了吗？不，还完全不会#
函数自己调自己只是递归的一个特征而已，这一步只要是学会了基本语法都能写出来，但是在递归中有很多细节是没有能够注意到。
- 什么情况下用递归
- 开始递归的位置在哪里
- 结束的条件的什么
- 递->归之间的值应该传递什么
- 递<-归之间的值应该传递什么
- …
不信可以看个难一点的问题
汉诺塔（Tower of Hanoi）#
1
2
3
4
5
6
|
是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。
|
根据上面两个例子的经验，在这个问题就毫无思路了
每日一个排序算法写到了归并排序后就没写快速排序的原因就是因为快排需要深刻得递归理解才能理解其精华。
