I called the following recursion procedure, it crashed by stack overflow.
proc f(n: int): int =
if n == 0: 0 else: n + f(n - 1)
echo f(2000)
Traceback (most recent call last)
main.nim(4) main
main.nim(2) f
...
main.nim(2) f
main.nim(2) f
main.nim f
Stack overflow
How can I avoid stack overflow? Is it possible that 2,000 times recursion calls in nim?
Thank you.
Compile with -d:release.
GCC/Clang will not do tail call optimization otherwise.
the stack(where the return addresses are stored) has only a limited size. So obviously once it's full, there will be a stack overflow error.
The most straight forward solution would be to rewrite your function to be iterative instead of recursive:
proc f(n: int): int =
for i in 1..n:
result += i
echo f(2000)
This solution is probably much faster too, since a jumping back for the next loop iteration is way cheaper than a function call and return.
Thank you for your answer.
'-d:release' solved my problem. I seem that somehow with '-d:release', recursive procedures that has no tail call do not raise stack overflow over 2,000 times recursive calls.
Thank you for you reply.
I agree that in this case we should not use recursive call. I showed the procedure as just an example. Actually, I tried to implement an algorithm that similar to Depth-First-Seach, then I faced this problem.
Actually, I tried to implement an algorithm that similar to Depth-First-Seach
Maybe it would have been wise to say that at the beginning, because your initial post was looking a bit like "Nim can still not cook fine coffee", so some devs may have just ignored you.
I would be indeed interested how to increase stack size -- my knowledge is very limited and only about Linux, like
https://stackoverflow.com/questions/2279052/increase-stack-size-in-linux-with-setrlimit
The creation of a new thread is a very old trick, I can remember some Amiga programmers using it. Setrlimit() seems to be not available for Nim currently.
- Depth-first-search is bounded by the maximum depth of your trees/path, breadth first search by the width, if width < depth, use the BFS.
- Use a trampoline or try to search for Continuation Passing Style in C/C++/\<insert non-TCO language here\> and reimplement them in Nim.