In order to learn recursion you need to learn recursion.

The above quote is hilarious, but seriously – what is recursion?

Recursion is when a function calls itself. If this should work there has to be some stop condition to prevent infinite looping. If function is called a stack frame that holds local variables and some other data is created. When next call happens the new stack frame is created and appended on stack. If this happens many, many times there might be a situation there’s not enough stack space and StackOverflow exception occurs. But there’s also another type of recursion.

Tail recursion

If we know that we will not need the local variables we could save the stack space and store next call stack frame on the same place where the current one is. Of course it can be done only if in fact we do not need to keep any values for later use when the call returns. This type of recursion is called tail recursion.

C# vs F#

IL does have a prefix for a call method that indicates that the call should be a tail call (tail.- 0xFE 0x14) but C# compiler never produces such. You will always end up with a regular one and due to that fact at some point hit StackOverflow exception. F# on the other hand can utilise tail call and produce more efficient recursion. This is one of the differences that might be in favour of F#.

More about that can be read on Wikipedia – tall call

Founder of Octal Solutions a .NET software house.
Passionate dev, blogger, occasionally speaker, one of the leaders of Wroc.NET user group. Microsoft MVP. Podcaster –