递归算法及其简单的举例
一、递归算法的基本知识
1.理解什么是递归
简单的从字面意思来，就是既有传递又有回归的算法，就叫做递归。比如：你在电影院看电影，凑巧的是你来迟了，一懵，发现自己的座位号找不到，你就开始问旁边的人，你是第几号，然后旁边的人又不知道，又问旁边的人，那个人又不知道，之后他又问旁边的人，依次类推，等到你问到最前面的时候，那个人知道自己的座位号，就告诉他旁边的人，然后他们一个又一个的把消息传递回来，直到你知道自己的作为在哪里。这就是所谓的递归；平常生活中，我们会碰到很多这样的例子。这类似于我们平常听到的一个故事，从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事，然后又是从前有座山……，这个例子很像递归，但它却不是递归，而是循环，就像那种永远跳不出的循环，死循环。
2.递归的条件
a. 必须要有终止条件，否则会报内存溢出的错误
b. 递归必须有去有回
3.递归与循环的区别
递归是有去有回，而循环是只有去，没有回。
二、举例
1.用递归算阶乘 5的阶乘
【分析】 5! == 5 * 4!
4! == 4 * 3!
3! == 3 * 2!
2! == 2 * 1!
fn(5);
return 5 * fn(4);
fn(4)
return 4 * fn(3)
fn(3)
return 3 * fn(2)
fn(2)
return 2 * fn(1)
…..
代码：
function fn(n) {
if (n == 1) return 1;
return n * fn(n – 1);
}
console.log(fn(5));
2.利用递归求1 – 100的和
function fn(n) {
if (n <= 1) return 1;
else
return n + fn(n – 1);
}
console.log(fn(5));
3.兔子 3 个月成年 -> 繁殖 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987
function fn(n) {
if(n==1|| n==2) return 1;
return fn(n-1)+fn(n-2);
}
console.log(fn(10));
4. 求最大公约数
function fn(m, n) {
var r;
r = m % n;
m = n;
n = r;
if (r != 0) {
return fn(m, n);
} else {
return m;
}
}
console.log(fn(14, 24));
5.算1！+2！+3！+……+n!
function fn(n) {
if (n <= 1) return 1;
return n * fn(n – 1);
}
function fn1(n) {
var sum = 0;
for (i = 1; i <= n; i++) {
sum += fn(i);
}
return sum;
}
console.log(fn1(4));
版权声明：本文为lxz123原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。