Invert a string: Recursion vs iteration in javascript

Question

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!

Answer 1

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.