递归函数

递归函数定义

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。

---

要点

1. 函数直接或间接调用本身；
2. 循环调用结束时机（只有达到了结束时机，才会有最终的结果）；

---

递归的逻辑梳理

1. 基本功能函数
2. 递推逻辑转化
3. 临界条件（基本功能函数调用结束的条件）

---

示例分析

需求：求出1-100之间，所有整数的和；代码如下：

    function sum(n){
        if(n===1){
            return 1
        }else{
            return sum(n-1) + n
        }
    }
    console.log(sum(100)); //输出结果5050

基本功能函数

    function sum(n){
        return sum(n-1) + n;
    }

解释：求n+(n-1)的和；

递归逻辑转化

求100的和转化为求99的和；
求99的和转化为求98的和；
求98的和转化为求97的和；
......
求1的和转化为求1的和；（临界条件就是n=1）

---

常见的递归函数

• Fibonacci数列(斐波那契数列)

 function fib(n){
   if(n == 0 || n ==1) return 1;
   return fib(n-1) + fib(n-2);
 }

• 阶乘

    function foo(n){
        if( n == 1) return 1;
        return foo(n - 1) * n;
    }