尾递归与函数柯里化

一、尾递归

在介绍尾递归之前，先介绍一些其他概念，方便理解为啥需要尾递归。

1.JS函数调用栈

1).是什么？

调用栈是js引擎追踪函数执行流程的一种机制，当执行环境中调用了多个函数时，可以通过这种机制追踪到哪个函数正在执行，执行的函数体又调用了哪个函数。

2).图例说明

来个简单的例子

function sum(a, b){
   return a + b;
}
function avarage(a, b){
   return sum(a, b) / 2;
}

const aver = avarage(5, 9);
console.log(aver);

上面的一点代码执行流程如下，调用栈，即调用的时候才有，所以函数声明期间是没有调用栈的；

在实际的开发中，调用栈是要比这个复杂的多的。比如常见的递归函数，如果递归层级比较深的时候，函数不停的入栈，而没有出栈动作，就会导致栈溢出。

2.尾调用

1).尾调用是什么？

某个函数的最后一步是调用另外一个函数。

function f(x){
    return g(x) + 1;
}

上面代码中，调用完还有别的操作，所以并不属于尾调用。

2).尾调用优化

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。 这就叫做尾调用优化，即只保留内层函数的调用记录。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存。

3.尾递归

递归就是函数调用自己，如果尾调用自己，称为尾递归。对递归方法进行尾递归优化，把内部变量写成函数的参数，可以起到节省内存的作用，防止栈溢出。

1).尾递归改写

来两个例子，对递归进行尾递归优化

• n的阶乘

  最常见的n的阶乘问题，一般递归实现

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

  尾递归：

  function factorial(n, total = 1) {
     if(n===1) {
        return total;
     } else {
        return factorial(n-1, total * n);
     }
  }
  

• 爬楼梯问题

  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶100层呢？

  一般递归实现

  function fn(n){
    if(n === 1) {
       return 1;
    }
    if(n===2) {
     return 2;
    }
    return fn(n-1) + fn(n-2);
  }
  

  尾递归优化：

   function fn(n, n1 = 1, n2 = 2){
    if(n === 1) {
       return n1;
    }
    if(n===2) {
     return n2;
    }
    return fn(n-1, n2, n1 + n2);
  }
  

二、函数柯里化

1.柯里化是什么？

是把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数。

2.例子

来个例子简单说明：

function sum(a, b){
   return a + b;
}

//柯里化以后
function sum(a){
   return function(b){
       return a + b;
   }
}

上面的例子，简单来说，就是将sum方法变为先用一个函数接受a参数，然后返回一个参数接受b参数。

3.柯里化的作用

1).参数复用，减少传递部分不变的参数

2).提前确认，避免每次重复判断

3).延迟计算运行

// 实现一个add方法，使计算结果能够满足如下预期：
add(1)(2)(3) = 6;
add(1, 2, 3)(4) = 10;
add(1)(2)(3)(4)(5) = 15;

以上是一道面试题，可以采用函数柯里化的方式进行实现

function add(){
    let args = [...arguments];
    let num = function(){
        args.push(...arguments);
        return num;
    }

    num.toString = function(){
        return args.reduce(function(pre, cur){
            return pre + cur;
        })
    }
    return num;
}

4.封装函数柯里化的方法

采用递归的方法，将一个接受多个参数的函数转换为每次接收单一参数的函数。

/**
 * fn:要被柯里化的函数
 */
function curry(fn) {
    //获取fn的参数个数
    let len = fn.length;
    return function temp() {
        //收集参数
        let args = [...arguments];
        // 参数全部收集完成
        if(args.length >= len){
            return fn(...args);
        } else {
            return function() {
                temp(...args, ...arguments);
            }
        }
    }
}

这样，就完成了一个简单的函数通用柯里化封装。