# Why do Julia BigInt iterative functions overflow?

**URL:** <https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674>\
**Category:** General Usage\
**Tags:** question\
**Created:** [February 23, 2024, 10:00pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674 "2024-02-23T22:00:40Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Claude\_Shannon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/claude_shannon/32/207260_2.png) [@Claude\_Shannon](https://discourse.julialang.org/u/Claude_Shannon)\
**Post date:** [February 23, 2024, 10:00pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674/1 "2024-02-23T22:00:40Z")

</div>

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
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.

1. I wonder what is wrong with the recursive code that results in such an error?

2. 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.

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [February 23, 2024, 10:05pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674/3 "2024-02-23T22:05:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [February 23, 2024, 10:07pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674/4 "2024-02-23T22:07:50Z")

</div>

A “[stack overflow](https://en.wikipedia.org/wiki/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

```julia
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.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 23, 2024, 10:13pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674/5 "2024-02-23T22:13:59Z")

</div>

> [@mikmoore](#):
>
> Some languages utilize “tail call optimization” to eliminate the excess memory use of some simple recursive functions

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](https://discourse.julialang.org/t/tail-call-recursion/87847/19) — many people don’t realize how [narrowly applicable it is](https://discourse.julialang.org/t/tail-call-recursion/87847/17).)

For the particular case of the factorial function, of course, you should just call the [built-in `factorial` function](https://docs.julialang.org/en/v1/base/math/#Base.factorial), which supports `BigInt` and is highly [optimized by the GMP library](https://gmplib.org/manual/Number-Theoretic-Functions). `factorial(big(1000000))` takes about 0.1 seconds on my laptop. It [isn’t implemented using explicit recursion](https://github.com/alisw/GMP/blob/2bbd52703e5af82509773264bfbd20ff8464804f/mpz/oddfac_1.c#L266-L419), though the underlying [mathematical algorithm is formally recursive](https://oeis.org/A000142/a000142.pdf).

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [February 23, 2024, 11:10pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674/6 "2024-02-23T23:10:57Z")

</div>

> [@dlakelan](#):
>
> Unlike scheme for example there is no tail recursion elimination in Julia, for good reasons to do with multiple dispatch.

The [stated reason](https://github.com/JuliaLang/julia/issues/4964#issuecomment-961932928) 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.

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [February 23, 2024, 11:14pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674/7 "2024-02-23T23:14:08Z")

</div>

As @stevengj pointed out though, in this case tail-call elimination wouldn’t even help because the recursive call isn’t in tail position.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 23, 2024, 11:47pm UTC](https://discourse.julialang.org/t/why-do-julia-bigint-iterative-functions-overflow/110674/8 "2024-02-23T23:47:59Z")

</div>

Please, not another TCO thread. See e.g. [Does Julia have tail call optimization?](https://discourse.julialang.org/t/does-julia-have-tail-call-optimization/64101) and references therein. There is nothing new to say on this topic.