Recursion vs Iteration in C#

Question

I was asked a question in a recent interview to write a recursive function to reverse a string and whether an iterative version is better than recursive one for this particular algorithm. I am not sure how the recursive solution is worse/better than iterative one. Can anyone help me understand this?

Isn't the below code a tail recursive one?

public static string Reverse(string str)
{
    return (str.Length <= 1 ? str : str[str.Length - 1] 
          + Reverse(str.Substring(0, str.Length - 1)));
}

Please see if [this][1] answers your question. [1]: http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration — AksharRoop, Jan 11 '12 at 10:16
That is not tail-recursive. For a tail-recursive function, the last thing called must be the function itself. In this case, the last thing called is actually the `+` operation. — porges, Jan 11 '12 at 10:17

score 3 · Answer 1 · answered Jan 11 '12 at 10:16

3

There's no guarantee that anything will be compiled using tail recursion (although x64 .net seems more inclined to do so). If the string is a long one, you're going to run out of stack.

answered Jan 11 '12 at 10:16

spender

117,338
33
229
351

I understand that my example is not tail recursive, but can't we know for sure whether tail-recursive functions are transformed to iterative ones by C# compiler? – blitzkriegz Jan 11 '12 at 10:30
@mkg: It's not the C# compiler that does it, it's the JITer. And it's not guaranteed, there are [lots of exceptions](http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx). While it's technically possible to check whether it's been done on your machine, you shouldn't assume that goes for all other machines. This is meant to be a black-box implementation, not something that you should rely on in any way. – Cody Gray - on strike Jan 11 '12 at 10:40

score 2 · Answer 2 · answered Jan 11 '12 at 10:35

Check the Optimize flag and look at the code with a debugger(ida,olly,whatever) to see what the compiler did to it. it could be possible for sure,but i won't bet that he converts a recursion into an iterative algorithm.

in general you should use iterative algorithms whenever possible as they are less likely to run out of memory/cause a stack overflow etc. if it really helps understanding the code and there is no chance to have a stack overflow, you can use a recursion

Recursion vs Iteration in C#

2 Answers2