递归算法

什么是递归方法：就是一个方法，自己调用自己

递归我的理解就是

方法或函数调用自己就称为递归

1.分解为：直接量+小规模问题

2.分级为：小规模问题

要想计算f（10），就需要知道f（9），算f（9）需要计算f（8）

特点：

1.自身调用自身

2.避免死循环

方法：

1.找重复（找更小规模的子问题（和原问题具有相同的形式）；求n的阶乘，先求n-1的阶乘。。。。）

2.找变化（哪些东西在变化，求n的阶乘，先求n-1的阶乘，。。。。将变化的量作为参数）

3.找边界（循环终止的条件，出口的判断，求n的阶乘，一直递归变为求1的阶乘，到1的时候，1的阶乘为1，返回）

求数组的和

1.找重复，将arr化为小的规模，将第一个划分出来，剩下的交给递归一直这样重复

2.找变化，数组的长度在变化，起点的不断变化，数组的区间在缩小，终点不变

3.找边界，就为数组的长度

 // 经典面试题：使用递归算法1-20之间所有数之和

        function calc(num){

            //这个if是退出递归的条件

            if(num===1) {

                return num

            }

            return num + calc(num-1)

        }

        console.log(calc(20));

计算sum（5）时，先sum（5）入栈，然后原问题sum（5）拆分为子问题sum（4），再入栈，直到终止条件sum（n=1）=1，就开始出栈。sum（1）出栈后，sum（2）开始出栈，接着sum（3）。最后呢,sum（1）就是后进先出，sum（5）是先进后出，因此递归过程可以理解为栈出入过程啦~