js递归算法

提示：以下是本篇文章正文内容，下面案例可供参考

一、递归是什么？

二、步骤

1.递归的目的

说到递归，最经典的就是斐波那契数列（Fibonacci sequence）：
斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

从中可以提取出这个数列的规则：当前位数的数字等于前两位的和。

我们现在的需求是想通过传一个坐标就能获取当前坐标位的值，
效果为:

function rabbit(num){
        //各种方法
    }
    rabbit(6);//返回8

那么需要包装出这种效果的函数，就需要先看这个数列的规则，也就是“当前位数的数字等于前两位的和”；

思路：

既然这个数列的当前位等于前两位的和，那么计算当前位的值必定需要知道前两位的值，前两位的值则由更前面的数字来决定，
也就是说不管传入的位数是多少，除非是1或者2，否则我们都需要算到数列的开始，也就是第一位的“1”和第二位的“1”，由此来一步步计算到当前位

加一点细节以后，现在代码如下：

function rabbit(num){ //num：参数   代表需要获取数字的位数
        if(num<3)return 1  //如果位数小于3，则代表是第一位或者第二位，返回1
        return rabbit(num-1)+rabbit(num-2) //当前位数的数字等于前两位的和
    }

首先我们需要明白这个函数的目的：“传一个坐标就能获取当前坐标位的值”。
也就是说首先需要使第一位和第二位都为1，这已经通过第一行实现，接下来就到了最关键的时候，怎么计算后面的位数？
刚刚我们分析出计算这个数列的思路后得到一个线索“需要算到数列的开始”，由于此数列的特性，获取后面位数的数值需要知道此位数之前所有的值，那么也就是说需要从头算起，我们可以先用一个简单的方法来实现

function rabbit(num){
        if(num<3)return 1    
        let newArr = [1,1];
        for(let i=2; i<num; i++){
        	//效果为当前位的值 = 前两位的值相加
            newArr[i] = newArr[i-1]+newArr[i-2]
        }
        console.log(newArr);//更清晰的看到过程
        return newArr[num-1]
    }

第一行不变，在已知位数1,2都为1时，我们可以创建一个数组（有下标，方便操作），第一位和第二位都为1。
然后开始通过之前的思路写出for循环，最后返回需求的值。
这个方法的思路是：从开始算到结束（第num位）

而递归算法则更加简洁，且逻辑清晰

2.递归示意图

如下：
ps：线指向接下来要执行的函数

想搞懂递归首先要明白递归函数是怎么进行运算的，如图所示：
首先假设我们给函数传入一个6，本函数的目的是计算出当前传入位数的值，那么rabbit(6)就代表着数列第六位的值，

接着进行if判断，判断为false，然后本函数返回值为rabbit(5)+rabbit(4)：第五位的值+第四位的值。

此时rabbit（6）因为返回的函数未执行，所以并未停止

然后计算机就理所当然的开始计算rabbit(5)和rabbit(4)，不断重复上面的步骤，此时每个rabbit函数都在等待其他rabbit返回一个值让它计算（图中所有的rabbit(3,4,5,6)），能够不依靠其他rabbit（）函数就可以返回值的只有rabbit（1）和（2）
这就是所谓的“出口”。

每个rabbit函数都将提供自己处理过的参数“递”给另一个自己，直到函数碰到出口，将返回值“归”回来，

最底层的函数结束后，函数将会一层层的结束自己的运算，并将结果“归”还（返回），从而得到需要的结果（返回值）。

这就是递归

	function rabbit(num){
	    if(num<3)return 1
	    return rabbit(num-1)+rabbit(num-2)
	}

现在来看这个函数，是不是清晰了许多呢，如果想学会怎么写递归，那就要先掌握for循环实现正向算法，然后通过逆向思维来倒推出递归算法即可。

总结

递归需要知道正确的逻辑，需要一个出口，需要将处理过的参数传递给自己，
正确使用递归将会很大程度压缩代码，以及增加函数的可读性