Javascript(笔记05) - 函数 - 递归

先看一个试题： 求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      

经过以上演练，我们可以归纳一下。

递归

如果在函数中存在着调用函数本身的情况，这种现象就叫递归。