你的位置:首页 > Java教程

[Java教程]递归调用与尾调用


 

// 普通递归函数的调用 时间复杂度为 O(n)

function fn(num){
  if(num === 1) return 1;
    return num * fn (num -1);
}
// 等同于 该函数耦合性更小
function fn(num){
  if(num === 1) return 1;
  return num * arguments.callee(num - 1);
}

console.log(fn(50)) // 120

// 尾调用函数 优化了递归调用 事件复杂度为O(1)
function ofn (num, sum){
  if(num === 1) return sum;
  return ofn(num - 1, num * sum);
}
console.log(ofn(5, 1)); // 120

// 当然为了优化尾调用函数,我们可以多加一个函数调用的步骤
function ofn1(num){
  return ofn(num, 1);
}
console.log(ofn1(5)); // 120

得出的结果都是一样的,这样优化了前面函数的调用参数值不直观的优化。
不太明白的伙伴们会问,为什么递归调用还需要传入第二个参数,所以ofn1函数就是对上一个函数的优化。
这样我们就可以递归调用传入一个参数从而得到递归后的值!

当然了,看了《javascript高级程序设计(第三版)》这一本书中有讲到“柯里化”的概念,

  它的主要的优点就是:1.参数复用,2.加载一次多次运行,3.延迟运行,等

例如:
柯里化函数参数转换:
var currying = function(fn) {
  // 从第二个传入的参数开始截取,隔离第一个参数
  var args1 = [].slice.call(arguments, 1);
  // 返回一个函数(此处的函数为一个内部函数)外部调用的时候,只是会以函数表达式的形式展现出来
  return function() {
    var args2 = args1.concat([].slice.call(arguments));
    return fn.apply(null, args2);
  };
};
/* 注释 */
// alert(currying) // 指的是当前整个函数currying
// alert(currying()) // 指的是内部返回的匿名函数 function(){}

 

// "被代理函数"
function proxied ([ ... options ]) {// do something...}

// 在此出我把这一层理解为“代理层(对函数默认参数的传定)”(如有理解误区,望大牛指点)
var proxy = currying (proxied, [ ... ]); // 参数传入 默认传参项,

// 最终只需要调用代理函数传入部分,或则最终的参数
proxy([ ... ]);

返回函数的优点:在程序第一次执行的时候,就把返回的函数给确定,当再次加载该函数的时候,
    就不需要再次去判断什么的,直接到内存中抓取并使用。这样做的目的主要是优化性能。(在此处可能并没有得到多大的体现)
    但是在此处返回一个带参数的函数,中间就多出来一层函数的调用,中间层就可以做“代理”的用途了


言归正传:
  我们的例如就是将多个参数化为一个参数的形式就行传参,将其他的参数在另一个域中进行初始化了!
正真的例如来了:
// 按照柯里化的概念设计一个柯里化函数。

// 函数表达式一:①
function currying (func) {
var args1 = [].slice.call(arguments, 1);
  return function() {
    var args2 = args.concat([].slice.call(arguments));
    /*
    *
将传入进来的参数进行倒叙,但是有个问题,
    * 在柯里化的函数里最好不要修改原型 可以从下面调用的函数进行想办法
    */
    // return func.apply(null, args2.reverse());
    return func.apply(null, args2); // 保留原型
  };
};


/**函数表达式二:②
* 本来打算这种形式进行尾处理优化,因为更具柯里化currying函数的规则,
* 我们需要把函数的参数的位置进行更改一下(该函数不能与上面柯里化函数并用,需要调用下面一个更改后的函数)
*/
function ofn (num, sum){
  if(num === 1) return sum;
  return ofn(num - 1, num * sum);
}

 

/**函数表达式三:③
* 修改之后的函数表达式,
*/
function ofn(sum, num) {
  if (num === 1) return sum;
  return ofn(num * sum, num - 1);
}


// 函数表达式三:④
// 调用currying函数,进行传入默认的参数
var final = currying(ofn, 1);


// 函数表达式三:⑤
// 最终调用的形式
final(5); // 120

组合表达式:①+③+④+⑤

或利用简单一点的柯里化表达式:
// 函数表达式三:⑥
function currying (proxyFn, second){
  return function (another) {
    return proxyFn.call(this, another, second);
  }
}

组合:⑥+②+④+⑤

当然了还有更简单的方法来实现,就是ECMAScript6标准,部分浏览器实现了一些ES6的特性
function recu (num, sum = 1) {
  if (num === 1) {
    return sum;
  }
  return recu (num - 1, num * sum);
}
函数调用: recu (5) // 120

 

 参考资料:

        ECMAScript 6

        js中的柯里化