Closures with recursion 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);
    }

I have two questions about the above code:

does the above code break the (my ignorance is showing) stateless nature of function programming?
what if str was a large string, is this implementation slower/more memory intensive than a solution that did not use a closure?

And what exactly is stateless nature of functional programming? -.- — freakish
– freakish, Commented Dec 12, 2014 at 20:46
@freakish that's why I qualified my ignorance is showing. My understanding is that by having i stick around for multiple function calls seems like state to me, instead of, say, passing i as a parameter to a function call. — wootscootinboogie
– wootscootinboogie, Commented Dec 12, 2014 at 20:49
Yes, but from what you say it sounds like you believe that 1) it's bad 2) it should not be done in functional progamming. Both are false IMHO. — freakish
– freakish, Commented Dec 12, 2014 at 21:36
can you elaborate, please? i didn't mean to sound like anything was bad and the whole point of this question was to better understand functional programming in general. — wootscootinboogie
– wootscootinboogie, Commented Dec 12, 2014 at 21:47

6502 · Accepted Answer · 2014-12-12 23:11:08Z

2

Yes, you're not using the functional paradigm.

In your case you're using the recursion just to loop and the processing is done using variables that are outside of the function. It's really not much different than using global variables (except that they're not global but locals of the outside function).

To reverse a string using the functional approach you should consider that the reverse of a string is composed by last_char + (reverse of middle part) + first_char. This definition expands naturally into a recursive function... for example:

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];
    }
}

this uses no explicit state (as you may notice there are no assignments at all).

If you're looking for a tail-call optimizable version instead consider:

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

the idea in this case is that the processing case must be return <recursive-call> (in the previous example this is not happening because the result of recursion is added one char to each end before returning).

If your code ends up returning the unprocessed result of a recursive call then the function can be tail-call optimized as no stack space is needed. In other words the recursive call becomes a simple loop.

Finally this is another version, not purely functional but that seems similar to what you're attempting:

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);
}

This is not purely functional because the vector elements are swapped (and you can see there are assignments) but uses a tail-call optimizable recursion to do the loop. Note that rev1 is not a closure but a function (captures no state and you can also put it outside of rev).

edited Dec 12, 2014 at 23:11

answered Dec 12, 2014 at 20:57

6502

115k17 gold badges177 silver badges277 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

wootscootinboogie Over a year ago

I've actually been playing around with recursion and specifically reversing strings for funsies and had something similar to yours. In my example, I suppose if it were to be in the functional paradigm I would need i to be an accumulator (I believe that's the nomenclature)?

6502 Over a year ago

@wootscootinboogie: in the purely functional paradigm you cannot assign a new value to a variable and there is no mutable data structure. Variables are names for values, like in math, and things like i = i+1 simply don't have any meaning. Se other examples for tail-call recursion optimization (the reason for which often you see accumulators used in recursive functions).

mike652638 Over a year ago

Thanks for the detailed explanation. BTW, with recursion, could it be simplified to following please ? function revStr(str){ if(str.length <2){ return str; }else{ return revStr(str.slice(1)) + str[0]; } } console.log(revStr('Hello World'));

Collectives™ on Stack Overflow

Closures with recursion JavaScript

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related