Let’s say I want to write the factorial function in Julia in the following recursive way:
FACTORIAL(n) = n==1 ? 1 : n*BigInt(FACTORIAL(n-1))
Doing so, it shows the following error when trying to compute FACTORIAL(1e6)
julia> FACTORIAL(1e6)
ERROR: StackOverflowError:
Stacktrace:
[1] FACTORIAL(n::Float64) (repeats 65428 times)
@ Main ./REPL[36]:1
[2] top-level scope
@ REPL[38]:1
However, one may easily see that factorial(BigInt(1e6)) does not throw an overflow error.
-
I wonder what is wrong with the recursive code that results in such an error?
-
Is there a way to write such a function recursively which avoids such an error?
Note that my question is general and not about the factorial function by itself. I have seen such a behavior with a few other functions written recursively.
At first I thought this was a type issue, or comparison issue in the base case. But it’s not. The reason is you’ve recursively called factorial 65428 times and it’s overflowed the stack.
Unlike scheme for example there is no tail recursion elimination in Julia, for good reasons to do with multiple dispatch.
1 Like
A “stack overflow” is not the same thing as “numerical overflow.” A stack overflow is usually caused by a recursive function that recurses “too many” times. Every time it calls itself, it has to add its data to the top of the stack (a part of memory designated for basic program data). The stack is preallocated at some specific size, so if too many functions get piled on it then it runs out of space and you get a stack overflow. In this case, it ran out of stack space after 65k recursions (far short of the 1M you asked for).
So the issue here is that this function tried to recurse 1 million times and the stack was too small to hold that many. Some languages utilize “tail call optimization” to eliminate the excess memory use of some simple recursive functions (EDIT: but to be clear, functions like factorial would not work as mentioned below), but others (like Julia) do not for assorted technical reasons.
A non-recursive calculation like
FACTORIAL(n) = prod(1:n)
called with FACTORIAL(big(1e6)) will give you the answer without a stack overflow or numerical overflow. I recommend against FACTORIAL(big(1000000)) as an input because that number is very big to represent as an integer (it takes about 3MB just to store it, since it’s roughly 10^{5,565,709}) and computing it will take a while.
3 Likes
Even if Julia had TCO, it wouldn’t work for the FACTORIAL(n) function here because the recursive call is not in tail position. (This seems to be a widespread misapprehension about TCO — many people don’t realize how narrowly applicable it is.)
For the particular case of the factorial function, of course, you should just call the built-in factorial function, which supports BigInt and is highly optimized by the GMP library. factorial(big(1000000)) takes about 0.1 seconds on my laptop. It isn’t implemented using explicit recursion, though the underlying mathematical algorithm is formally recursive.
10 Likes
The stated reason has nothing to do with multiple dispatch, and is one I only halfway agree with.
The comment itself is on point, as is the solution. Where I differ is that I consider tail call elimination an important and missing feature, preventing several esoteric-yet-important programming styles, and which would lead to better code if implemented. Examples include continuation-passing style, recursive-descent, and dynamic programming. These aren’t just leetcode interview questions, in certain domains they’re the cleanest and best way to solve the problem.
I do agree that an explicit annotation is the way to go, but I don’t think the issue should be closed; the language should have tail call elimination.
As @stevengj pointed out though, in this case tail-call elimination wouldn’t even help because the recursive call isn’t in tail position.
1 Like
Please, not another TCO thread. See e.g. Does Julia have tail call optimization? and references therein. There is nothing new to say on this topic.
6 Likes