【笔记05】Javascript - 基本概念 - （函数递归）

先看一个试题： 求n的阶乘

通常，我们会写：

function fac(num){
  var res = 1;
  for(var i = 1; i <= num; i++){
    res *= i;
  }
  return res;
}

观察阶乘可以发现两个特点：

特点一：有规律

5！ = 5 * 4 * 3 * 2 * 1

发现 5 的阶乘等于 5 乘以 4 的阶乘，同理，4 的阶乘是 4 乘以 3 的阶乘。

5！ = 5 * 4！
4！ = 4 * 3！
3！ = 3 * 2！
... ...

特点二：有出口

出口是已知的，就是 1 的阶乘等于 1.

1！ = 1

根据这两个特点，可以把函数改一下；

function fac(num){
  if(num == 1){                  // 出口条件
    return 1;                   // 出口的值已知
  }
  return num * fac(num -1);     // 抽象出规律
}

可以再推倒一遍：

fac(5);

fac(5) ==> 5 * fac(4);  // 想知道 5 的结果，就得需要先知道 4 的结果
fac(4) ==> 4 * fac(3);  // 想知道 4 的结果，还得先知道 3 的结果
fac(3) ==> 3 * fac(2);  // 想知道 3 的结果，得先知道 2 的结果
fac(2) ==> 2 * fac(1);  // 想知道 2 的结果，得先知道 1 的结果
fac(1) ==> 1 已知       //  1 的结果已知，往上反推回去

fac(2) = 2 * 1; 
fac(3) = 3 * 2; 
fac(4) = 4 * 6;
fac(5) = 5 * 24;        //  120

这就是用递归的方法来解决。

递归比较符合人的思维，找到规律和出口，就可以使用递归的思想来写代码。

所以，按这个思路，再把 N 的阶乘，再理一遍。

// 1. 找规律
// 2. 找出口

// 规律：  n! = n * (n - 1)!

根据规律，直接写函数：

function fac(num){
  
  return num * fac(num - 1);    // 直接 return 规律公式
}

然后进行推倒，比如 3 的阶乘；

fac(3) ==> 3 * fac(2)
fac(2) ==> 2 * fac(1);
fac(1) ==> 1 * fac(0); 

这时，必须要找个出口，不然函数成了无限死循环。

已知条件： 1 的阶乘是 1。

function fac(num){
  if(num == 1){             // 设置一个出口
    return 1;               // 出口值为1
  }
  return num * fac(num - 1); 
}

但这是没有办法求 0 的阶乘，而 0 的阶乘等于 1，所以给他补上。

function fac(num){
  if(num == 1 || num == 0){
    return 1; 
  }
  return num * fac(num - 1); 
}

fac(5);   // 120

递归的时间复杂度比较大，所以效率低下。

根据递归的思路，再来写一个斐波那契数列的递归函数。

// 1. 找规律
// 2. 找出口

// 第N位的值等于第(n-1)和第(n-2)位的和
// 规律：  fib(n) = fib(n - 1) + fib(n - 2)

function fib(n){

  return fib(n - 1) + fib(n - 2);     // 根据规律，直接写return
}

推倒一下：

fib(5) ==> fib(4) + fac(3);
fib(4) ==> fib(3) + fac(2);
fib(3) ==> fib(2) + fac(1); 

这时，找出口。 我们已知 fib(1) 和 fib(2) 的结果是1，所以直接把出口条件写在函数里。

function fib(n){
  if(n == 1 || n == 2){     // 设置出口条件
    return 1;               // 出口值
  }
  return fib(n - 1) + fib(n - 2);
}

fib(8);   // 21