Invert string: recursion versus iteration in javascript

Question

a month ago I was interviewed by some members of the Google PTO. One of the questions: Invert string recursively to js and explain runtime with large musical 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 notation, I quickly answered O (n), since the runtime is linearly dependent on the input. “Silence,” and then, he asked me, what are the differences in deadlines if you implement it by iteration?

I replied that sometimes the compiler "translates" recursion into iteration (some language courses of the programming language), so in this case there are no differences in iteration and recursion. By the way, since I didn’t have feedback on this particular question, and the interviewer did not answer “good” or “no”, I would like to know if you agree with me or if you can explain to me whether there may be differences regarding 2 type of implementation.

Thanks a lot and welcome!

Answer 1

Your solution looks O (n²) for me. The substring call is most likely O (n) - a typical implementation will allocate space for a new line and then copy the substring to another. [But see Comments.] String concatenation + is likely to also be O (n). It may even be that length is O (n), but I think this is hardly possible.

---

You understand that the compiler can convert recursion to iteration. This is true, but rarely implemented outside functional languages ​​and Schemas; and, as a rule, the only transformation that applies is the elimination of tail recursion. In your code, recursion is not in the tail position: after the invert recursive call, you still need to calculate + . So eliminating tail recursion does not apply to your code.

This means that the iterative version of invert must be implemented differently. It can have the same or different complexity, we cannot say until we saw it.

Answer 2

On the side of the note, to use tail recursion, which allows the compiler to implement your recursion as a loop, you cannot leave state on the stack. To get around this, you can pass “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; }