Invert a string: Recursion vs iteration in javascript

Posted by steweb on Stack Overflow See other posts from Stack Overflow or by steweb
Published on 2011-01-17T21:47:39Z Indexed on 2011/01/17 21:53 UTC
Read the original article Hit count: 338

Filed under:

JavaScript

|

recursion

|

interview-questions

|

iteration

|

big-o

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!

© Stack Overflow or respective owner

Related posts about JavaScript

CHAT ROOMs 7 by 6

as seen on Stack Overflow - Search for 'Stack Overflow'
I am looking for chatroom on one page with 7 loggedin users and 6+rows for say 42 users.these users will keep on adding wthnew users.Need urgent help.A PRETTY UNUSUAL Q FOR MOST OF U.What is MORE REQ new features: Usernames are unique to users currently chatting You can see a "currently chatting"… >>> More
Integrating JavaScript Unit Tests with Visual Studio

as seen on Stephen Walter - Search for 'Stephen Walter'
Modern ASP.NET web applications take full advantage of client-side JavaScript to provide better interactivity and responsiveness. If you are building an ASP.NET application in the right way, you quickly end up with lots and lots of JavaScript code. When writing server code, you should be writing… >>> More
Has Javascript developed beyond what it was originally designed to do?

as seen on Programmers - Search for 'Programmers'
I've been talking with a friend about the purpose of Javascript, when and how it should be used, etc. He quoted that: JavaScript was designed to add interactivity to HTML pages [...] JavaScript gives HTML designers a programming tool HTML authors are normally not programmers… >>> More
PHP, javascript, single quote problems with IE when passing variable from ajax post to javascript fu

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi! I have been trying to get this to work for a while, and I suspect there's an easy solution that I just can't find. My head feels like jelly and I would really appreciate any help. My main page.php makes a .post() to backend.php and fetches a list of cities which it echoes in the form of: <li… >>> More
Javascript in XSL that is loaded by Javascript

as seen on Stack Overflow - Search for 'Stack Overflow'
Is there anyway to have javascript run when a XSL sheet has been applied to an XML file by Javascript? I am using a JQuery plugin to apply the sheet to the xml but the javascript that is located inside of the XSL file will not run. I put the Javascript at the bottom of the file and it still does… >>> More

Related posts about recursion

tail recursion vs. forward recursion

as seen on Stack Overflow - Search for 'Stack Overflow'
Can someone give me the difference between these two kinds recursions and example? specifically in ocaml. Thanks >>> More
Are there advantages for using recursion over iteration - other than sometimes readability and elegance?

as seen on Programmers - Search for 'Programmers'
I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion (at least in general purpose languages such as Java, C++, Python etc.). If it's true that recursion… >>> More
Python recursive function error: "maximum recursion depth exceeded"

as seen on Stack Overflow - Search for 'Stack Overflow'
I solved Problem 10 of Project Euler with the following code, which works through brute force: def isPrime(n): for x in range(2, int(n**0.5)+1): if n % x == 0: return False return True def primeList(n): primes = [] for i in range(2,n): if isPrime(i): … >>> More
Dynamic Programming Recursion and a sprinkle of Memoization

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion: You must start at one of the zero points in the row with 70 elements. Your… >>> More
How does the recursion here work?

as seen on Stack Overflow - Search for 'Stack Overflow'
code 1: public static int fibonacci (int n){ if (n == 0 || n == 1) { return 1; } else { return fibonacci (n-1) + fibonacci (n-2); } } how can you use fibonacci if you haven't gotten done explaining what it is yet? I've been able to understand… >>> More