一、递归函数
何为递归
- 函数的一种应用方式
- 递:一层一层的进去
- 归:一层一层的回来
- 把一个事件分成若干个事情来做
- 递归就是一个自己调用自己的手段
- 递归函数:一个函数内部,调用了自己,循环往复
递归终点
- 当达到设置的终点的时候
- 再归回来,归使用 return
- 当不设置的终点的时候
- 就会陷入死循环
- 注意:写递归先写停 return
//下面这个代码就是一个最简单的递归函数
//在函数内部调用了自己,函数一执行,就调用自己一次,在调用再执行,循环往复,没有止尽
function fn(){
fn();
}
fn();
注意:递归慎用,能用循环解决的事情,尽量别用递归
二、递归案例
1. 递归求和
- 需求: 求 1 至 5 的和(15)
1. 先算 1 + 2 得 3
2. 再算 3 + 3 得 6
3. 再算 6 + 4 得 10
4. 再算 10 + 5 得 15
5. 结束
写递归函数先要写结束条件(为了避免出现 “死递归”)
- 设置终点结束条件
function sum(n){
//传递进来的是1
//当n==1的时候结束
if(n==1){
return 1;
}
}
console.log(add(1)); // 1
- 再写不满足条件的时候我们的递归处理
function add(n){
//传递进来的是1
//当n==5的时候结束
if(n==5){
return 5;
}else{
//不满足条件的时候,就是当前数字 + 比自己大 1 的数字
return n + add(n + 1);
}
}
console.log(add(1)); // 15
- 还可以这样写
function add(n){
//传递进来的是5
//当n==1的时候结束
if(n==1){
return 1;
}else{
//不满足条件的时候,就是当前数字 + 比自己小 1 的数字
return n + add(n - 1);
}
}
console.log(add(5)); // 15
2. 递归求阶乘
一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且 0 的阶乘为 1 。自然数 n 的阶乘写作 n! 。
- 例子:求 3 的阶乘(3*2*1)
3 的阶乘 =
=> 3 * 2 的阶乘
=> 2 * 1 的阶乘
=> 1 的阶乘就是 1
从上往下就是 递 的过程
从下往上就是 归 的过程
function fn(n){
// n 就是你要求的终点
if(n===1){
// 设置终点位置
return 1;
}
// 当 n 不是 1 的时候
// 就递进去
return n * fn(n-1);
}
fn(3); // 6
- 代码分析
第一次:
n = 3 , if(n===1)不成立
return 3 * fn(2)
fn(3) = 3 * fn(2)
第二次:
n = 2 , if(n===1)不成立
return 2 * fn(1)
fn(3) = 3 * fn(2)
= 3 * 2 * fn(1)
第三次:
n = 1 , if(n===1) 成立
return 1
fn(3) = 3 * fn(2)
= 3 * 2 * fn(1)
= 3 * 2 * 1 = 6
3. 递归求最大公约数
最大公约数:指两个或多个整数共有约数中最大的一个
如果数a
能被数b
整除,a 就叫做 b 的倍数,b 就叫做 a 的约数。
约数和倍数都表示一个整数与另一个整数的关系,不能单独存在。如只能说16是某数的倍数,2是某数的约数,而不能孤立地说16是倍数,2是约数。
- 需求分析
求最大公约数会用到辗转相除法
先确定终点:
=> a % b ===0
=> b 就是最大公约数
未到终点时:
=> 计算相对小的数字,和两个数字的余数
- 书写代码
function fn(a,b){
// 保证 a > b
if(a < b){
var tmp = a;
a = b;
b = tmp;
}
// 设置终点
if(a % b === 0){
return b;
}
// 未到终点
return fn(b,a % b);
}
console.log(fn(2,4)); // 2
- 代码分析
第一次:
a = 2 , b = 4 , if(a < b)成立
a = 4 , b = 2 , if(a % b === 0)成立
return b (b = 2) 返回结果,结束递归
4. 递归求斐波那契数列
斐波那契数列指的是这样一个数列:
1 1 2 3 5 8 13 21 34 55 …
这个数列从第3项开始,每一项都等于前两项之和
- 需求分析
=> 第一位和第二位是固定的 1
=> 第三位开始依次是前两位的和
=> 确定终点
=> n 是你要求第几位
=> 当 n 等于 1 或者 2 的时候,表示你要求第一位或者第二位
=> 没到终点之前
=> 你要求第 n 位,实际上就是 n-1 和 n-2 位的和
- 书写代码
function fn(n){
// n 就是要求的第 n 位
// 设置终点
if(n===1 || n===2){
return 1;
}
// 未到终点
return fn(n-1) + fn(n-2);
}
console.log(fn(10)); // 55
今天的文章【JS】递归函数_递归和迭代的区别及关系分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/77542.html