17 ms·
The biggest problem with recursion in most languages is the maximum stack size is too small, so you end up banging against the limit when your problem gets big
by CJefferson 6y ago
The biggest problem with recursion in most languages is the maximum stack size is too small, so you end up banging against the limit when your problem gets big enough.
In Rust I'm spinning up another thread just to run recursive algorithms in, which I give a huge (1/2 size physical memory) stack size for running recursive algorithms in.
- souprock 6y agoCurious... does Rust require code to be marked unsafe when the maximum depth of recursion can't be proven to fit within the available stack? If not, it's a huge hole in the memory protection.
- CJefferson 6y agoRust does have code in the compiler to make sure your code "cleanly" segfaults when you stack overflow, so while you can't catch up, you won't (as you do in some other languages) start corrupting the heap, or any other pieces of memory. However, you still can't recover.
- souprock 6y agoThat is actually worse than C on Linux. For C, that segfault is provided by the kernel placing a guard page off the end of the stack. C programs recover via sigaltstack, sigaction, and siglongjmp. The C program can continue running safely afterward. I was expecting Rust to give a compile-time error. Rust should refuse to compile a program that would overflow the stack. Unbounded recursion is such a case. Another case would be recursion that is bounded but very large. For example, if the recursion depth can be 128, then on Linux (with the 8 MiB stack default) it would not be allowable to have the stack frames be 64 kilobytes each. That should not compile. Rust is not a memory-safe language.