Invert a string: Recursion vs iteration in javascript

one month ago I've been interviewed by some google PTO members. One of the questions was: Invert a string recursively in js and explain the running time by big O notation

this was my solution:

function invert(s){
    return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s;
}

Pretty simple, I think.

And, about the big-o notation, I quickly answered O(n) as the running time depends linearly on the input. - Silence - and then, he asked me, what are the differences in terms of running time if you implement it by iteration?

I replied that sometimes the compiler "translate" the recursion into iteration (some programming language course memories) so there are no differences about iteration and recursion in this case. Btw since I had no feedback about this particular question, and the interviewer didn't answer "ok" or "nope", I'd like to know if you maybe agree with me or if you can开发者_运维百科 explain me whether there could be differences about the 2 kind of implementations.

Thanks a lot and Regards!

Your solution looks O(n²) to me. The call to substring is most likely O(n) — a typical implementation will allocate space for a new string and then copy the substring across. [But see comments.] The string concatenation + will probably also be O(n). It may even be the case that length is O(n) but I think this is fairly unlikely.

You brought up the idea that a compiler can transform recursion into iteration. This is true, but it's rarely implemented outside of functional languages and Scheme; and typically the only transformation that gets applied is tail recursion elimination. In your code, the recursion is not in tail position: after the recursive call to invert you've still got to compute the +. So tail recursion elimination does not apply to your code.

That means that an iterative version of invert would have to be implemented in a different way. It might have the same or different complexity, we can't say until we've seen it.

On a side note, to use tail recursion which allows the compiler to implement your recursion as a loop, you cannot have state left on the stack. To work around this you can pass the "state" as an additional parameter to your function:

function invert(sofar, s)
{
    return (s.length > 0) ? invert(s.charAt(s.length-1)+sofar, s.substring(0,s.length-1)) :  sofar;
}