If you're getting a stack overflow, you might check if your language supports tail call optimization, or just known as tail recursion. Not all environments support this, but if you can rearrange your recursive function it would avoid the overflow.
The short version of the tail call story is only one copy of the stack frame is kept, instead of all of the frames on the way down.
Re:Thinking About Recursion
by iCodeSometime on Monday February 10, 2020 @05:48PM
(#22294256)
Alternatively, adding some kind of memoization can reduce run time and stack size pretty significantly for some algorithms.
e.g. if you're using recursion to compute fibonacci, you're re-computing quite a lot of steps by default
Re:Thinking About Recursion
by gliese1337 on Monday February 10, 2020 @02:27PM
(#22292326)
You really need language support to make recursion the best practical solution for most problems. However, even when working in "normal" languages like C#, I find that recursion has utility in designing solutions--it is often easiest to find a provably-correct solution for an inherently recursive problem by actually designing a recursive algorithm; you merely then have to perform some compiler work yourself to transform that initial design into an efficient iterative implementation.
In some cases in C# you can write a tail-recursive function and then have Resharper rewrite it into a loop for you.
Re:Thinking About Recursion
by zelphirkalt on Tuesday February 11, 2020 @05:12PM
(#22303494)
Could also consider externalizing the stack http://wiki.c2.com/?ExternalizeTheStack
Re:Thinking About Recursion
by tigershark on Tuesday February 11, 2020 @12:38AM
(#22296359)
C# from .Net 64bit supports tail-call optimization as far as I know. If you write your function in a tail recursive way it will be optimized and you won’t have any stack overflow if you use a C# version more recent than that.
I use .NET 4.8 but I need to check if it's x86 or x64.
Re:Thinking About Recursion
by tigershark on Wednesday February 12, 2020 @06:54AM
(#22308064)
You need also to check if your function is tail recursive.
Then I had an interesting problem at work where recursion seemed the most elegant solution ... but I quickly encountered errors that were not caught in a try catch block and made the program fail silently.
I'll admit my ignorance, but I thought a stackoverflow was a "feature" of low level programming languages such as C and C++ since I never encountered one in 10 years of coding in C#.
So it seems my love for recursion will have to remain mostly platonic and I'll have to use those unappealing loops for a while.