javascript - 带有递归 JavaScript 的闭包

Question

//reverse a string with recursion and a closure
    function r(str){
        var i = str.length-1,results=[],j=0;
        function _r(str){
            if(i===0){
                return results.join('') + str[0];
            }
            console.log('i = ' + i);
            results[j] = str[i];
            i--,j++;
            console.log('j = ' + j);    
            return _r(str);    
        }

        return _r(str);
    }

我对上面的代码有两个问题:

1. 上面的代码是否破坏了(我的无知)函数编程的无状态本质？
2. 如果 str 是一个大字符串，这个实现是否比不使用闭包的解决方案更慢/更占用内存？

Answer 1

是的，您没有使用函数范式。

在您的情况下，您使用递归只是为了循环，并且处理是使用函数外部的变量完成的。它实际上与使用全局变量没有太大区别(除了它们不是全局变量而是外部函数的局部变量)。

要使用函数方法反转字符串，您应该考虑字符串的反转由last_char +(中间部分的反转)+first_char 组成。 这个定义自然地扩展到递归函数......例如:

function rev(str) {
    if (str.length < 2) {
        // Empty string or a single char... reverse = input
        return str;
    } else {
        return str[str.length-1] + rev(str.slice(1, -1)) + str[0];
    }
}

这不使用显式状态(您可能会注意到根本没有分配)。

如果您正在寻找尾调用优化版本，请考虑:

function rev(todo, done) {
    if (todo === "") {
        return done;
    } else {
        return rev(todo.slice(1), todo[0] + (done||""));
    }
}

本例的想法是处理案例必须是 return <recursive-call> (在前面的示例中，这种情况没有发生，因为递归结果在返回之前会在每一端添加一个字符)。

如果您的代码最终返回递归调用的未处理结果，则可以对该函数进行尾调用优化，因为不需要堆栈空间。换句话说，递归调用变成了一个简单的循环。

最后，这是另一个版本，不是纯粹的功能，但看起来与您正在尝试的类似:

function rev(str) {
    function rev1(v, i, j) {
        if (i >= j) {
            return v.join("");
        } else {
            var t=v[i]; v[i]=v[j]; v[j]=t;
            return rev1(v, i+1, j-1);
        }
    }
    return rev1(str.split(""), 0, str.length-1);
}

这不是纯粹的函数式，因为向量元素被交换(并且您可以看到有赋值)，而是使用尾调用优化递归来执行循环。请注意rev1不是一个闭包，而是一个函数(不捕获任何状态，您也可以将其放在 rev 之外)。