Because this is the poster example for bad recursion usage. There should be a ban for using this as an example for the elegance of recursion, because it really is totally inelegant w.r.t. the machine.
For every call to fib
, you reap another two fib
calls:
depth | call tree
------+------------------------------------------------------------------------
1 | fib-----+
| | \
2 | fib fib
| | \ | \
3 | fib fib fib fib
| ....
4 | fib fib fib fib fib fib fib fib
| ....
5 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
6 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
7 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
8 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
9 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
... and for depth 50, ...
[562,949,950,000,000] × fib
... all existing in parallel, roughly 560 million packets of each a million fib
.
What you have is not an OCaml problem, but rather a computation/algorithm problem. Fibonacci numbers are a good example for a case where "simple" recursion is not desirable. It looks simple and elegant, but denies reality.
So, implement this as a loop instead and your problem will be gone.
Complexity
This is a good question to point out computational complexity (Big O Notation). Your implementation has exponential complexity O(2n), i.e. the time required to run your algorithm grows exponentially w.r.t. to the input. A summing loop will run in O(n), i.e. the time required to solve the problem grows linearly w.r.t. to the input.
See also Algorithm function for fibonacci series.