javascript 递归

邱秋9月前 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

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

早期版本的 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();

再例如这道题目:计算12345*....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)

警告:在严格模式下,第5版 ECMAScript (ES5) 禁止使用 arguments.callee()。当一个函数必须调用自身的时候, 避免使用 arguments.callee(), 通过要么给函数表达式一个名字,要么使用一个函数声明.

没有替代方案的 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

[完]

本文于9月前 10:20发布在code分类下,当前已被围观727次

相关标签:javascript,

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

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

匿名用户