JavaScript递归详解什么是递归？递归设计（递归三要素）切蛋糕思维以上例子总结多分支递归-递推公式/等价转换递归经典问题-汉诺塔游戏总结

59 阅读 0 评论 39 点赞

我是靠谱客的博主爱听歌可乐，最近开发中收集的这篇文章主要介绍JavaScript递归详解什么是递归？递归设计（递归三要素）切蛋糕思维以上例子总结多分支递归-递推公式/等价转换递归经典问题-汉诺塔游戏总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

什么是递归？

一个方法或函数内部调用了自己，这就叫递归。如下。

<script>
    function fn(n){
        if(n == 0) return
        fn(n - 1);
    }
    fn(3);
</script>

递归设计（递归三要素）

1.找重复（子问题）

-找到更小规模的子问题

-如上代码，（n-1）是原问题的重复（规模更小）—— 子问题

2.找重复中的变化量➡参数

-变化的量应该作为参数

-如上代码，变化的量为n

3.找参数变化趋势➡设计出口

-找到递归的边界（出口）

-如上代码，n越来越小，当n等于0时，结束递归

递归三要素缺一不可，不然就会导致栈溢出

栈溢出：

1.没有使问题规模更小

function fn(n){
    if(n == 0) return 
    fn(n);
}
fn(3)

2.没有用变化的量作为参数

function fn(n){
    if(n == 0) return 
    fn(2);
}
fn(3)

3.递归没有边界

function fn(n){
    fn(n-1);
}
fn(3)

切蛋糕思维

1.求n的阶乘

/*
1.找重复：n * (n - 1)的阶乘，求(n - 1)的阶乘就是原问题的重复——子问题
2.找变化：n
3.找边界：出口，n = 1
*/
function fn(n){
    if(n == 1) return 1
        return n * fn(n - 1);
    }
console.log(fn(3));//6

2.数组求和

/*
1.找重复：arr[begin] + arr[begin + 1]的值，arr[begin + 1]的值就是原问题的重复——子问题
2.找变化：begin
3.找边界：出口，begin == arr.length - 1
*/
var arr = [1, 2, 3, 4, 5]
function fn(arr, begin) {
    if (begin == arr.length - 1) return arr[begin]
    return arr[begin] + fn(arr, begin + 1);
}
 console.log(fn(arr, 0));//15

以上例子总结

在重复中找变化，在变化中找重复

多分支递归-递推公式/等价转换

1.斐波那契序列

function fn(n) {
    if (n == 1 || n == 2) return 1
    return fn(n - 1) + fn(n - 2)
}
console.log(fn(5));//5

2.最大公约数

function fn(m,n) {
    if (n == 0) return m
    return fn(n,m % n)
}
console.log(fn(10,8));//2

递归经典问题-汉诺塔游戏

规则：将所有盘子从A柱移动到B柱，移动过程中一次只能移动一个，并且在任何时候一定是小盘子在大盘子上面。

图中A为原柱，B为目标柱，C为辅助柱。

思路：

除最大的盘子外不管多少个盘子都看成1个盘子（设最大盘子为N，大盘子上面的盘子为1到N-1）

把1到N移动到B，C为辅助：等价转换

（1）1到N-1移动到C，B为辅助

（2）把N从A移动到B

（3）把1到N-1从C移动到B，A为辅助

代码：

function fn(n,from,to,help) {
    if (n == 1) {
        console.log('move ' + n + ' from ' + from + ' to ' + to)
    }else {
        fn(n - 1,from,help,to)
        console.log('move ' + n + ' from ' + from + ' to ' + to)
        fn(n - 1,help,to,from)
    }         
}
fn(3,'A','B','C')