JavaScript之递归

[zzyundragon]

程序调用自身的编程技术称为递归。

递归的例子：

阶乘

    function factorial(n){
        if(n <= 1) return n
        return n * factorial(n-1)
    }
    factorial(5) // 5*4*3*2*1 = 120

斐波那契数列

    function f(n){
        return n < 2 ? n : f(n-1) + f(n-2)
    }
    console.log(f(5)) //  1 1 2 3 5

递归的条件

构成递归需要具备临界条件、递归前进段和递归返回段。当边界条件满足时，递归返回，当不满足边界条件时，递归前进。
使用递归需要注意两个问题：

• 子问题须与原始问题处理同样的事，且更为简单
• 不能无限制调用本身，必须有个出口，化简为非递归状况处理。

递归优化

修改函数指向

    let anotherFactorial = factorial
    factorial = null
    console.log(anotherFactorial(5)) // error

修改了factorial变量引用后，再调用anotherFactorial会导致错误。这种情况可以通过arguments.callee解决，arguments.callee是一个指向正在执行的函数的指针，使用arguments.callee代替函数名，可以确保无论怎样调用函数都不会出问题，比使用函数名更加保险。

    function factorial(n){
        if(n <= 1) return n
        return n * arguments.callee(n-1)
    }
    factorial(5) // 5*4*3*2*1 = 120

但是在严格模式下，不能通过脚本访问arguments.callee，访问这个属性会报错。此时使用命名函数表达式来避免这个问题。

    let factorials = (function f(n) {
            if (n <= 1) return 1
            return n * f(n - 1)
    })
    let anotherFactorials = factorials
    factorials = null
    console.log(anotherFactorials(5)) // 120

通过创建一个名为f()的命名函数表达式，然后将它赋值给factorials。即便把函数赋值给了另一个变量，函数的名字f仍然有效。所以递归调用照样能正确完成。这种方式在严格模式和非严格模式都行得通。

内存占用大

当执行一个函数时，就会创建一个执行上下文，并且压入执行上下文栈。当函数执行完毕后将函数的执行上下文从栈中弹出。

递归函数会不停的创建上下文压入执行上下文栈，对于内存而言维护这么多执行上下文栈也是一笔不小的开销。因此，需要通过尾调用的方式来解决内存占用大的问题。

尾调用

尾调用是指函数内部最后一个动作是函数调用，该调用的返回值，直接返回给函数。

    // 尾调用
    function f(x) {
        return g(x)
    }
    // 非尾调用
    function f(x) {
        return g(x) + 1
    }

最后一个动作必须是函数调用，没有其他运算才是尾调用。区别在于，两者在执行上下文栈的变化上不一样。

模拟执行上下文栈的行为，定义执行上下文栈是一个数组：

    ECStack = []

模拟尾调用函数执行时执行上下文栈的变化：

    ECStack.push(<f> functionContext)
    ECStack.pop() // 函数执行完毕，执行上下文会被弹出
    ECStack.push(<g> functionContext)
    ECStack.pop()

而非尾调用函数执行上下文栈的变化是：

    ECStack.push(<f> functionContext)
    ECStack.push(<g> functionContext)
    ECStack.pop()
    ECStack.pop()

也就是说尾调用函数执行时，虽然也调用了一个函数，但是因为原来的函数执行完毕，执行上下文会被弹出，执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数，就会创建多个执行上下文压入执行上下文栈。

函数调用自身，为递归；如果是尾调用自身，则为尾递归。

所以为了避免使用递归造成内存占用过高的问题，可以将函数改造成尾递归的形式，就可以避免创建太多执行上下文。

阶乘函数优化

因此优化阶乘函数需要将函数内部用到的变量改写为函数的参数，

    function ff(n, res){
        if (n <= 1 ) return res
        return ff(n - 1, n * res) 
    }
    console.log(ff(5,1)) // 120

此时通过柯里化将所需的多个参数的函数转换成一个使用一个参数的函数执行。

    let newFunc = curry(ff, _, 1)
    newFunc(5) // 120        

应用

递归的应用在很多地方，比如二叉树遍历，函数柯里化，判断两个对象相等，深浅拷贝以及数组的扁平化等场景。