Invert a string: Recursion vs iteration in javascript
- by steweb
Hi all, 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!