C# Recursion Depth - How Deep can you go

Question

Is there any control how much you can Recursively call something?

From a basic test program I get a recursion depth of just over 18k

which depends on the stacksize....

is there a way to set up a chunk of memory (perhaps a thread) with a massive stack to increase recursion depth?

Jerlenejermain

possible duplicate of [How do you change default stack size for managed executable.net ](#1042845) – Gregarious

Infinitely deep. Or at least in languages supporting tail calls. – Armchair

<inception ref>3 levels deep...</inception ref> – Indevout

@Juliet: ...and if you can write tail-recursive functions. :) – Larock

C# does not support tail calls. There is an opcode for it in CIL, but as far as I know no .NET languages actually use it (except maybe F#) – Sappy

Afaik the jitter doesn't necessarily need the tail call instruction to rewrite a tail call. From what I recall on .net 3.5 only the 64 bit jitter rewrites tail calls. – Stuyvesant

You have to understand that 99.99% of code doesn't blow the stack and 99.99% of the code that does does so because it is infinitely recursive. That leaves only 0.02% of code that blows the stack by using a finite amount. It's only these programs that can benefit by increasing the stack. – Underdrawers

can I have the source of your statistics? :) – Jerlenejermain

Answer 1

I've increased the stack size during some documents recognition. It was really needed.

So you can increase stack size for thread using following code:

var stackSize = 10000000;
Thread thread = new Thread(new ThreadStart(BigRecursion), stackSize);

Thread(ThreadStart, Int32) -- Initializes a new instance of the Thread class, specifying the maximum stack size for the thread.

Source

Hope this what you need.

Intussuscept

I really doubt this is what anyone needs. You simply shouldn't be creating code like this, I would sack a programmer who tried. Any recursive algorithm can be implemented without using recursion and sometimes it can be implemented in ways that reduces the order of the problem by a magnitude. This is like a car mechanic using sledge hammer to fix an engine. – Harquebus

@Mick, what if the code that uses recursion is outside of your control? For example, you could be using a third-party library that uses recursion. – Jellied

I'd find fourth-party ;) – Harquebus

Seriously... Unless they an exceptional case for such an implementation I would lose confidence in the ability of the vendor and would be reluctant to rely on their products. – Harquebus

I coded something like a crawler say a spider which gather a result from a web request and according to result it calls the same method for new result, I mean there is a recursion. It was giving a StackOverFlow error after 3k request in UI Thread. Now, I created a thread as described above and it passed that range. Still working 4.6k...+ at the moment. Thanks! – Grammer

I just stumbled on this. @Mick, Am I to believe that recursion should never be done? What if you're not executing through a linear structure, what if you're executing through a large complex TREE structure? Recursion also makes staying immutable much easier which also has advantages. Should we all not think about the trade-offs and just bow to the dogmatic wisdom that all recursion is always bad? – Unpopular

@StewartAnderson no I'm saying an algorithm that uses recursion with an indefinite level of recursion, especially one as in this case that requires you to start fiddling with the available stack definitely needs a rethink and should be re-implemented using a non-recursive approach. I've never encountered a recursive algorithm that couldn't be implemented just as easily without using recursion. – Harquebus

just for reference, the question is a "can", as for "why", there are various reasons none of which are sackable offences :) I think sometimes people get too focused on their own little bubble and what they are trying to achieve that they don't consider the vast world of what people want to do with programming languages. Having super strong opinions about what you should and shouldn't do often constrains your thinking. Having said that, this is something most people generally shouldn't need and you should always evaluate the tradeoffs you are making – Jerlenejermain

@KeithNicholas If I am to understand that .net threads use native threads, there is a reason to avoid arbitrary stack growth. According to this documentation, reserving extra space for the stack reduces the virtual memory address space available for use in the heap. If your application is multithreaded and 32-bit, you could easily run out of address space without even using very much memory if you max out your stack size. You get more portability and memory efficiency by using the heap. – Methaemoglobin

Answer 2

I think you are risking problems here. It's hard to determine exactly how much stack a recursive algorithm will use. And, if you are to the point where there's some question about if there'll be enough, I'd look for another approach.

Most recursive algorithms could be rewritten to not be recursive. You can then allocate as much memory as you need and even recover gracefully if there's not enough.

Outdare

+1 Every recursive algorithm can be written as non recursive with a loop and a stack data structure. – Gregarious

@Byron: Thanks for making me remember my data structures class in college. Prof: "Write this tree-traversal program in a non-recursive format." Me: "Why do you hate us?" : ) – Fury

My question was how to do it, I was more curious than wanting to actually do it. While this is good advice, it doesn't answer the question as posed. – Jerlenejermain

Don't forget these considerations when choosing recursion. – Altruist

Answer 3

The default stack size is stored in the PE header.

If you spawn the thread yourself, Thread has a constructor that takes the stack size as a parameter.

However, the default .NET stack size of 1 MB should be enough for most tasks, so before you change it you should at least review the task.

Dennet

Answer 4

Even if you manage to get greater recursion depths, simply for performance reasons I would implement this algorithm without recursion. Method calls are way more expensive than iterations within a while loop. I'd strongly advise against implementing anything that requires fiddling with the default stack size.

I occasionally use recursion but only when the call depth is defined and low (as in less than 100). When creating commercial software, using recursive algorithms that have an indefinite number of iterations is completely unprofessional and likely to give you very angry customers.

Harquebus