javascript 递归

邱秋1年前 10:20

概念

在程序中函数直接或间接调用自己,然后跳出结构,返回结果

递归的步骤(技巧)

  1. 假设递归函数已经写好
  2. 寻找递推关系
  3. 将递推关系的结构转换为递归体
  4. 将临界条件加入到递归体中

示例

求 1+2+3+3+...n 的和。
二逼青年:
首数加位数 ,乘以个数除以 2

function sum(n) {
  return ((1 + n) * n) / 2;
}
console.log(sum(100)); //5050

普通青年: 写个循环

function sum(n) {
  let result = n;
  while (n-- > 0) {
    result += n;
  }
  return result;
}
console.log(sum(100)); //5050

文艺青年: 有规律的序数运算,所以用递归

/***
 * 假设递归函数已经写好为sum,既sum(100),就是求1-100的和
 * 寻找递推关系: 就是 n 与 n-1 ,或 n-2 之间的关系,sum(n) == sum(n-1) + n, 前面的数字(n-1)之和和sun(n-1)加上本身n
 */
function sum(n) {
  return n == 1 ? 1 : sum(n - 1) + n; //n=1的时候跳出
}
console.log(sum(100)); //5050

求 1+3+5+7+9+...(2n-1)第 n 项的结果和前 n 项和
二逼青年:
用公式值为 n 的平方

function sum(n) {
  return n * n;
}
console.log(sum(5)); //25 =1+3+5+7+9

普通青年: 写个循环

function sum(n) {
  let result = 0;
  while (2 * n - 1 >= 1) {
    result += 2 * n - 1;
    n -= 1;
  }
  return result;
}
console.log(sum(5)); //25

文艺青年: 有规律的序数运算,所以用递归

/***
 * 假设递归函数已经写好为sum,既sum(100),就是求1-(2n-1)的和
 * 寻找递推关系: 就是 n 与 2n-1  之间的关系,sum(n) == sum(n-1) + (2n-1)
 */
function sum(n) {
  return n == 1 ? 1 : sum(n - 1) + (2 * n - 1); //n=1的时候跳出
}
console.log(sum(5)); //25

求 2+4+6+8+10+...2n 第 n 项的结果和前 n 项和
二逼青年:
用公式值为 n(n+1)

function sum(n) {
  return n * (n + 1);
}
console.log(sum(5)); //30 =2+4+6+8+10

普通青年: 写个循环

function sum(n) {
  let result = 0;
  while (2 * n > 0) {
    result += 2 * n;
    n -= 1;
  }
  return result;
}
console.log(sum(5)); //30

文艺青年: 有规律的序数运算,所以用递归

/***
 * 假设递归函数已经写好为sum,既sum(100),就是求1- 2n的和
 * 寻找递推关系: 就是 n 与 2n  之间的关系,sum(n) == sum(n-1) + 2n
 */
function sum(n) {
  return n == 0 ? 0 : sum(n - 1) + 2 * n; //n=0的时候跳出
}
console.log(sum(5)); //30

斐波拉契(Fibonacci)运算(兔子生兔子的故事)
一对兔子从出生后第 3 个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子对数为多少 产量分析:1, 1, 2, 3, 5, 8, 13, 21 ....n 第 n 个月的兔子总数 = 第 n-1 个月的兔子总数 + 第 n-2 个月的兔子总数 问题: 求任意月兔子的总数

二逼青年:
没公式,不会算,读书少,别骗我

普通青年: 循环大法好

var sum = function (n) {
  var a1 = 1,
    a2 = 1,
    a3 = 0;
  if (n <= 2) {
    return 1;
  }
  for (var i = 0; i < n - 1; i++) {
    a3 = a1 + a2;
    a1 = a2;
    a2 = a3;
  }
  return a3;
};
console.log(sum(5)); //8

文艺青年:看我的递归大法吧

有规律的序数运算,所以用递归

/***
 * 假设递归函数已经写好为sum,既sum(10),就是第10个月兔子的总数
 * 寻找递推关系: 倒数第3个数 = 倒数第二个数(n-1) + 倒数第一个数(n-2)
 */
function sum(n) {
  return n <= 2 ? 1 : sum(n - 1) + sum(n - 2); //n<=1的时候跳出
}
console.log(sum(5)); //8

mul 函数
实现一个函数mul,运算结果可以满足如下结果

1.mul(2)(3).valueOf()  //6
2.mul(3)(4)(5)(6).valueOf()  //360

二逼青年 & 普通青年
实现 mul(2)(3).valueOf() =>6

function mul(a) {
  return function (b) {
    let obj = {};
    obj.valueOf = function () {
      return a * b;
    };
    return obj;
  };
}
console.log(mul(2)(3).valueOf()); //6

实现 mul(3)(4)(5)(6).valueOf() =>360

function mul(a) {
  return function (b) {
    return function (c) {
      return function (d) {
        let obj = {};
        obj.valueOf = function () {
          return a * b * c * d;
        };
        return obj;
      };
    };
  };
}
console.log(mul(3)(4)(5)(6).valueOf()); //360

文艺青年:看你俩写的太 JB 累了。假如有无限级回调呢,比如 mul(3)(4)(5)(6)....(n).valueOf(), n 等于 100,你不累死啊。

二逼青年 & 普通青年:你就扯吧,有这样的需求吗?

文艺青年:呵呵,没有这样的需求,那就不抬杠了哈,用递归吧,更简单

function mul(x) {
  const result = (y) => mul(x * y);
  result.valueOf = () => x;
  return result;
}
console.log(mul(2)(3).valueOf()); //6
console.log(mul(3)(4)(5)(6).valueOf()); //360

可以看到,递归写法简单优美,省去考虑很多边界条件的时间。当然,递归算法会保存很多的临时数据,类似于堆栈的过程,如果栈深太深,就会造成内存用尽,程序崩溃的现象。Java 为每个线程分配了栈大小,如果栈大小溢出,就会报错,这时候还是选择递推好一点。

上面的例子都是些简单的例子,还需许多例子比如 汉诺塔,细胞分裂,爬楼梯等经典例子。我读书少,没做更深的钻研...

关于递归中的的 arguments.callee

calleearguments对象的一个属性。它可以用于引用该函数的函数体内当前正在执行的函数。这在函数的名称是未知时很有用,例如在没有名称的函数表达式 (也称为“匿名函数”)内。

早期版本的JavaScript不允许使用命名函数表达式,出于这样的原因, 你不能创建一个递归函数表达式

function factorial(n) {
  return !(n > 1) ? 1 : factorial(n - 1) * n;
}

[1, 2, 3, 4, 5].map(factorial);

但是

[1, 2, 3, 4, 5].map(function (n) {
  return !(n > 1) ? 1 : /* what goes here? */ (n - 1) * n;
});

这个不行。为了解决这个问题, arguments.callee 添加进来了。然后你可以这么做

[1, 2, 3, 4, 5].map(function (n) {
  return !(n > 1) ? 1 : arguments.callee(n - 1) * n;
});

然而,这实际上是一个非常糟糕的解决方案,因为这 (以及其它的arguments,callee, 和caller问题) 使得在通常的情况(你可以通过调试一些个别例子去实现它,但即使最好的代码是最理想的,你也没必要去检查调试它)不可能实现内联和尾递归。另外一个主要原因是递归调用会获取到一个不同的this值,例如:

var global = this;

var sillyFunction = function (recursed) {
  if (!recursed) {
    return arguments.callee(true);
  }
  if (this !== global) {
    //this居然不等于global
    console.log("This is: " + this);
  } else {
    alconsole.logert("This is the global");
  }
};

sillyFunction();

再例如这道题目:计算1*2*3*4*5\*....n的结果,就是阶乘函数

function factorial(num) {
  if (num <= 1) {
    return 1;
  } else {
    return num * factorial(num - 1);
  }
}

定义阶乘函数一般都要用到递归算法;如上面的代码所示,在函数有名字,而且名字以后也不会变的情况下,这样定义没有问题。 但问题是这个函数的执行与函数名factorial紧紧耦合在了一起。为了消除这种紧密耦合的现象,可以像下面这样使用arguments.callee

function factorial(num) {
  if (num <= 1) {
    return 1;
  } else {
    return num * arguments.callee(num - 1);
  }
}

在这个重写后的factorial()函数的函数体内,没有再引用函数名factorial。这样,无论引用函数时使用的是什么名字,都可以保证正常完成递归调用, 如下代码:

function factorial(num) {
  if (num <= 1) {
    return 1;
  } else {
    return num * arguments.callee(num - 1);
  }
}
var test = factorial;
console.log(test(5)); //120

factorial = function () {
  return 0;
};
console.log(test(5)); // 120 如果没有使用arguments.callee,将返回0,因为factorial 在外部被重新定义了

在此,变量trueFactorial获得了factorial的值,实际上是在另一个位置上保存了一个函数的指针。然后,我们又将一个简单地返回 0 的函数赋值给factorial变量。如果像原来的factorial()那样不使用arguments.callee,调用trueFactorial()就会返回 0。可是,在解除了函数体内的代码与函数名的耦合状态之后,trueFactorial()仍然能够正常地计算阶乘;至于factorial(),它现在只是一个返回 0 的函数。

现在已经不推荐使用arguments.callee()

原因:访问 arguments 是个很昂贵的操作,因为它是个很大的对象,每次递归调用时都需要重新创建。影响现代浏览器的性能,还会影响闭包。 那不能用咋办呢?记得有到面试题是这样的,接受参数 n=5,不用 for 循环输出数组【1,2,3,4,5】 这是用递归的思路,配合arguments.callee,代码如下

function print(n) {
  var arr = [];
  return (function () {
    arr.unshift(n);
    n--;
    if (n > 0) {
      arguments.callee();
    }
    return arr;
  })();
}

print(5); // [1,2,3,4,5]

用 setTimeout 实现 setInterval

function say() {
  //something
  setTimeout(say, 200);
}
setTimeout(say, 200);
// or
function say() {
  //something
  setTimeout(arguments.callee, 200);
}
setTimeout(say, 200);

没有替代方案的 arguments.callee

下面的例子是没有可以替代arguments.callee的方案的,因此弃用它时会产生一个BUG(参看bug 725398):

function createPerson(sIdentity) {
  var oPerson = new Function("alert(arguments.callee.identity);");
  oPerson.identity = sIdentity;
  return oPerson;
}

var john = createPerson("John Smith");

john();

利用命名函数表达式也可以实现上述例子的同样效果

function createPerson(identity) {
  function Person() {
    console.log(Person.identity);
  }
  Person.identity = identity;
  return Person;
}
var john = createPerson("John Smith");

john(); //John Smith

[完]

本文于1年前 10:20发布在[code]分类下,当前已被围观1153次

相关标签:javascript

永久地址:https://www.chuchur.com/article/js-recursion

版权声明:自由转载-署名-非商业性使用