Factorialize a Number

number.png

这是一道阶乘的算法题，很有意思；但我最先想到的不是采用递归函数，而是for循环解决；虽然也能实现效果，但和这道题的考点相去甚远，先将我的写法写出来，再分析网上另外两种写法。

首先要说明的是，负数没有阶乘，0和1的阶乘都是1；

  1. function factorialize(num) {
  2.   var a = 1;
  3.   if(num < 0){
  4.       return "请输入有效数字";
  5.   }else if(num === 0 || num === 1){
  6.       return 1;
  7.     }else{
  8.       for(var i = 1; i <= num; i++){
  9.         a *= i;
  10.       }
  11.   }
  12.   // 请把你的代码写在这里
  13.   return a;
  14. }
  16. factorialize(5);

下面说一下另外两种方法，第一种就是用递归函数来实现。先解释一下什么是递归函数，百度百科上对递归函数的定义是：一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的；
知道原理后再来梳理一下思路：

  1. 5! = 1 * 2 * 3 * 4 * 5 = 5 * 24 = 120
  2. 4! = 1 * 2 * 3 * 4     = 4 * 6  = 24
  3. 3! = 1 * 2 * 3         = 3 * 2  = 6
  4. 2! = 1 * 2             = 2 * 1  = 2
  5. 1!                     = 1
  6. 0!                     = 1

从上面可以找到一下规律：

  1. factorialize(0) = 1;
  2. factorialize(1) = 1;
  3. factorialize(num) = num * factorialize(num - 1);

用代码组织起来如下：

function factorialize(num){
      if(num < 0){
        return "请输入有效数字";
      }else if(num === 0 || num === 1){
        return 1;
      }else{
        return (num * factorialize(num -1));
        /*
         *当 num = 5 传进来时，调用函数： 5 * factorialize(5 - 1),
         *然后判断函数里面(5 - 1)是否等于1，
         *如果等于1，return 1;
         *如果不等于1，则继续调用num * factorialize(num -1)
         *用伪代码表示就是：
         *               num = 5    num * factorialize(num -1)
         *第一次调用： 当 num = 5    5 * factorialize(5 - 1) => 5 * factorialize(4)
         *第二次调用:  当 num = 4    4 * factorialize(4 - 1) => 4 * factorialize(3)
         *第三次调用： 当 num = 3    3 * factorialize(3 - 1) => 3 * factorialize(2)
         *第四次调用： 当 num = 2    2 * factorialize(2 - 1) => 2 * factorialize(1)
         *第五次调用： 当 num = 1    (num - 1) = 0, return 1;
         *
         * 函数是一层一层往里面调用，值是一层一层向外返回：
         * 第五次调用返回值: 1 * 1                => 1
         * 第四次调用返回值: 2 * 第五次调用返回值   => 2 * 1
         * 第三次调用返回值: 3 * 第四次调用返回值   => 3 * 2 * 1
         * 第二次调用返回值: 4 * 第三次调用返回值   => 4 * 3 * 2 * 1
         * 第一次调用返回值: 5 * 第二次调用返回值   => 5 * 4 * 3 * 2 * 1
         * 当值返回到最上层，就会将所有返回的值相乘，然后return 出去：
         * return (5 * 4 * 3 * 2 * 1)
         */
      }
    }
  factorialize(5);

去掉伪代码如下：

function factorialize(num){
      if(num < 0){
        return "请输入有效数字";
      }else if(num === 0 || num === 1){
        return 1;
      }else{
        return (num * factorialize(num -1));
      }
    }
  factorialize(5);

第二种方法就是用while循环

function factorialize(num){
  //初始化num传进来的值
  var a = num;
  if(num < 0){
    return "请输入有效数字";
  }else if(num === 0 || num === 1){
    return 1;
  }else{
    //创建一个while循环，当num > 1时会一直循环下去
    while (num > 1) {
      /*
       * 每次传进来的num值都会减1,一直循环下去，直到num = 1，或 num < 1 时，循环结束；
       * 需要注意的是 num-- 和 --num 运行结果一样，但是两者语义不同
       * num-- 使用的是旧值，也就是num 传进来的初始值；要想使用num--的值，只有再次调用num的时候，值才会-1；
       * --num 使用的是新值，也就是在使用num之前，已经-1；
       * 由于num在后面再次调用了，所以，num-- 和 --num的运行结果是一样的；
       * 在这里，为了保持函数语义和逻辑的一致，还是使用 num--
       *
       *               传入num     num--     a(第一次循环的a是从外部初始化的值)      a *= num (num 使用的是 num--后的值，不是传入的值)
       *   第一次循环      5      5-- => 4               5                              a = 5 * 4 = 20 (此时，a=20;num=4)
       *   第二次循环      4      4-- => 3               20                             a = 20 * 3 = 60 (此时，a=60;num=3)
       *   第三次循环      3      3-- => 2               60                             a = 60 * 2 = 120 (此时，a=120;num=2)
       *   第四次循环      2      2-- => 1               120                            a = 120 * 1 = 120 (此时，a=120;num=1)
       *   num = 1; 不符合循环条件，跳出循环；结果为上一次符号条件的循环结果，此时 a = 120;
       *
       *如果还是不理解 num-- 和 --num ;我在下面写一个小例子，基本上就明白了：
       *var d = 10,
       *    e = 6;
       *var fun = (d--)*(e--) + (--d)/(--e);
       *
       *console.log("fun:" + fun);      //fun:62
       *console.log("d:" + d);         //d:8
       *console.log("e:" + e);         //e:4
       *
       * 解析：
       * fun = 10 * 6 + 8 / 4 = 62
       * d 值的变化：
       *     d--
       *     使用的是原值10，但值已经变为9
       *     --d
       *     使用的是8，值已经变为8
       * e 值的变化：
       *     e--
       *     使用的是原值6，但值已经变为5
       *     --e
       *     使用的是4，值已经变为4
       */
      num--;
      a *= num;
    }
  }
  return a;
}
factorialize(5);

去掉伪代码：

function factorialize(num){
    var a = num;
      if(num < 0){
        return "请输入有效数字";
      }else if(num === 0 || num === 1){
        return 1;
      }else{
        while (num > 1) {
          num--;
          a *= num;
        }
      }
      return a;
    }
  factorialize(5);

总的来说，这倒算法题并不难，但很有意思，值得细细思索一番。

版权声明：本文为博主原创文章，转载请附上原文出处链接和本声明。