递归的概念
- 在程序中函数直接或间接调用自己
- 直接调用自己
- 间接调用自己
- 跳出结构,有了跳出才有结果
递归的思想
- 递归的调用,最终还是要转换为自己这个函数
- 如果有个函数foo,如果他是递归函数,到最后问题还是转换为函数foo的形式
- 递归的思想就是将一个未知问题转换为一个已解决的问题来实现
function foo(){
...foo(...)...
}
递归的步骤
- 假设递归函数已经写好
- 寻找递推关系
- 将递推关系的结构转换为递归体
- 将临界条件加入到递归体中
经典案例 1： 求和
求 1-100 的和
function sum(n) {
if (n == 1) return 1
return sum(n - 1) + n
}
复制代码
经典案例 2： 斐波拉契数列
1,1,2,3,5,8,13,21,34,55,89...求第 n 项
// 递归方法
function fib(n) {
if (n === 1 || n === 2) return n - 1
return fib(n - 1) + fib(n - 2)
}
console.log(fib(10)) // 34
//非递归方法 //
function fib(n) {
let a = 0
let b = 1
let c = a + b
for (let i = 3; i < n; i++) {
a = b
b = c
c = a + b
}
return c
}
console.log(fib(10)) // 34
复制代码
经典案例 3： 爬楼梯
JS 递归 假如楼梯有 n 个台阶，每次可以走 1 个或 2 个台阶，请问走完这 n 个台阶有几种走法
function climbStairs(n) {
if (n == 1) return 1
if (n == 2) return 2
return climbStairs(n - 1) + climbStairs(n - 2)
}
复制代码
经典案例 4： 深拷贝
原理: clone(o) = new Object; 返回一个对象
function clone(o) {
var temp = {}
for (var key in o) {
if (typeof o[key] == 'object') {
temp[key] = clone(o[key])
} else {
temp[key] = o[key]
}
}
return temp
}
复制代码
经典案例 5：vue中使用递归组件
- 递归组件: 组件在它的模板内可以递归的调用自己，只要给组件设置 name 组件就可以了。
- 不过需要注意的是，必须给一个条件来限制数量，否则会抛出错误: max stack size exceeded
- 组件递归用来开发一些具体有未知层级关系的独立组件。比如：联级选择器和树形控件
<template>
<div v-for="(item,index) in treeArr"> {{index}} <br/>
<tree :item="item.arr" v-if="item.flag"></tree>
</div>
</template>
<script>
export default {
// 必须定义name，组件内部才能递归调用
name: 'tree',
data(){
return {}
},
// 接收外部传入的值
props: {
item: {
type:Array,
default: ()=>[]
}
}
}
</script>
最后总结：
1、很多时候可以用递归代替循环，可以理解为递归是一种特殊的循环，但通常情况下不推荐这样做。
2、递归一般是在函数里面把函数自己给调用一遍，通过每次调用改变条件，来结束循环。
3、递归在数据格式一致，在数据层级未知的情况下，比普通的遍历更有优势。
4、递归在异步的时候，更容易理解，且更容易实现，因为可以在异步的回调里面，调用自己来实现每次都能拿到异步的结果再进行其他操作。
5、递归实现的快速排序比普通遍历实现的排序效率更好。
