4 ms·

I always thought recursion was very elegant, but until now I was using it to scan through folders on the file-system and that was about it. Then I had an inter

I always thought recursion was very elegant, but until now I was using it to scan through folders on the file-system and that was about it. 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.

imglorp 7y ago
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.
- iCodeSometime 7y ago
  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
gliese1337 7y ago
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.
- herbstein 7y ago
  In some cases in C# you can write a tail-recursive function and then have Resharper rewrite it into a loop for you.
tigershark 7y ago
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.
- jmnicolas 7y ago
  I use .NET 4.8 but I need to check if it's x86 or x64.
  - tigershark 7y ago
    You need also to check if your function is tail recursive.
zelphirkalt 7y ago
Could also consider externalizing the stack http://wiki.c2.com/?ExternalizeTheStack http://wiki.c2.com/?ExternalizeTheStack

imglorp 7y ago

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.

iCodeSometime 7y ago
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

gliese1337 7y ago

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.

herbstein 7y ago
In some cases in C# you can write a tail-recursive function and then have Resharper rewrite it into a loop for you.

tigershark 7y ago

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.

jmnicolas 7y ago
I use .NET 4.8 but I need to check if it's x86 or x64.
- tigershark 7y ago
  You need also to check if your function is tail recursive.

zelphirkalt 7y ago

Could also consider externalizing the stack http://wiki.c2.com/?ExternalizeTheStack http://wiki.c2.com/?ExternalizeTheStack