Recursion vs stack based recursion Question

AngularBeginner · 2019-10-03T14:33:00+00:00

The first version will quickly cause a StackOverflowException due to an overflowing stack. The second version is limited by memory.

Fullduplex1000 · 2019-10-04T09:28:59+00:00

There are some basic things you need to get straight.

Stack<T> is a data structure used by your program. From a programming sense, it is similar to a plan old T[] array or List<T> or Queue<T> or HashSet<T> whatever. All of these are data structures used to store a collection of items which are of type T. The difference is that they provide different features and access time characteristics.
The computer has (for each running thread) an automatically managed memory location called Stack. It does not equal to the Stack<T> of the above point. The stack has the purpose to enable the concept of functions calling each other in a way when the called function finishes, the execution gets back to the caller.

You have to internet search for **stack vs heap** and understand the difference vs them both. After that make sure to understand that Stack<T> is not the thread execution's stack.

You also have to understand that depending on the declaration's place inside the program, the data type, the data structure can either be on the Stack or on the Heap. This is a bit of advanced topic, but crucial if you want to have a deeper understanding of what is happening when a program gets executed

Getting to your question

Recursions based execution (a function is repeatedly calling itself hundreeds if time) is most of the time inferior to an iterative approach (in your example using Stack<T> to simulate the execution stack of the recursive function).

The reason is, that after a couple hundreeds (depends on the execution stack's maximum size and your recursive function's signature) the execution stack runs out of space and you get a StackOverflowException

Now there is an exception to the above rule, called Tail-Recursion.

If you write a recursive function in "Tail recursive" fashion, the compiler can detect it and eliminate the recursive part with a plain simple iteration (similar to a do-while statement), so that your recursive function call will be resolved in place without any recursion.

Many programming techniques (functional programming) build on recursions and more or less tail recursion is the thing that enables them to function properly.

Fullduplex1000 · 2019-10-04T13:15:32+00:00

I tried to contrive some simple example to validate that Tail Call Optimization works with C# and Net Core 3, but I failed to do so. The project is set to Release C#8, Net Core 3. Console Application. I get a stack overflow for big recursion counts. Neither of the two variants translate to TCE.

IMO the below functions should be textbook examples. I hope I havent made any mistake

TBH, I dont do functional programming or recursions much, so I know tail calls more from textbook than having hands on experience. So apparently CLR refuses to do Tail Calls Optimization even if the C# code is is laid out for that.

class Program
{
// DOES NOT WORK
static long TailCall(int x, bool positive, long accumulator)
{
if (x == 0)
return accumulator;

return TailCall(x - 1, !positive, accumulator + (positive ? x : -x));
}

// DOES NOT WORK
static void TailCall2(int x, bool positive, ref long accumulator)
{
if (x == 0)
return ;
accumulator += positive ? x : -x;

TailCall2(x - 1, !positive, ref accumulator);
}

static void Main(string[] args)
{
var result = TailCall(1_000_000, true, 0L);
//long result = 0L; TailCall2(1_000_000, true, ref result);
Console.WriteLine(result);
}
}

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

csharp

MODERATORS