Factorial function in python is being limited

Question

I made a simple factorial program:

import sys

sys.set_int_max_str_digits(0)
sys.setrecursionlimit(1000000)

def factorial(x):
    if x == 0 | x == 1:
        return 1
    elif x > 1:
        return x * factorial(x - 1)

i = 0
while 1:
    print(factorial(i), '\n')
    i += 1

But after a while the program halts. I want to know if there's a way to remove the limit on how big it could get.

`recursion` has a limit check [What is the maximum recursion depth in Python, and how to increase it?](https://stackoverflow.com/a/3323013/9465840). — rafathasan, Oct 22 '22 at 23:16
How large is the last number you get? You may just be running out of memory and having massive swapping going on. — Mark Ransom, Oct 22 '22 at 23:16
The last number is 29147787700729646733317401674448014464775705849593899142229282022494583262760283952082419433969059879748081302644739182242972198053252307456661041885244296873052499498551133071395204195753493612403370730920662513548031201042710884732323703081991061826353938430997084064596749030300769847292810726406097934112373321966031291529298963108884153890159346575504429071770061838764205630918658167378660117181832731545607527007479938624670807100592436346730239621149269954487882650127615967157927262641309593110288139204641756817058433762384073700546240499623644186158766662586201085686... — Youssef Gamil, Oct 22 '22 at 23:18
Try to print value of `i` instead and tell us where it stops. — Yuri Ginsburg, Oct 22 '22 at 23:44
No, 6000 digits number is not too big. I ran your code to `i = 17000` and `i!` has `64538` decimal digits. IMHO the problem is _not_ recursion depth. — Yuri Ginsburg, Oct 22 '22 at 23:48
The code stops @ `i = 21000` with the error message `Segmentation fault: 11` and `factorial(i)` has `81649` digits. — Yuri Ginsburg, Oct 22 '22 at 23:52
Could be that @YuriGinsburg is running a 64-bit version of Python but you're using a 32-bit version. — Mark Ransom, Oct 23 '22 at 15:17
@YoussefGamil Try to print only index, not factorial in the body of loop. Something like `r = factorial(i); print(i)` and see at what `i` it stops. — Yuri Ginsburg, Oct 23 '22 at 23:43

score 1 · Accepted Answer · answered Oct 22 '22 at 23:31

1

Recursion is not meant to be infinite. Eventually your program would fail, even on a system with a huge amount of memory.

Also note that the recursion limit given to setrecursionlimit() is not a guarantee that you'll get that recursion depth. To quote from the sys.setrecursionlimit documentation:

The highest possible limit is platform-dependent. A user may need to set the limit higher when they have a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

I would suggest either limiting the program to calculating a reasonable sized factorial, or not using recursion. Some tasks are much better suited to recursion versus iteration, but factorials is not one of them.

answered Oct 22 '22 at 23:31

sj95126

6,520
2
15
34

Actually, the size of the number used by the factorial will become less practical before the recursion gets unreasonable. – jsbueno Oct 23 '22 at 00:25
Some people are getting better results with the same code so I don't think it's related to recursion depth. Especially considering I'm not getting the error message for recursion depth. – Youssef Gamil Oct 23 '22 at 13:21
@YoussefGamil: It's likely that the segmentation fault you're getting is because the Python process has run out of stack space, which would be a direct result of excessive recursion. And it makes sense that different people get different results, because as quoted above the limit is *platform-dependent*. – sj95126 Oct 23 '22 at 14:27
@jsbueno one of the most amazing things about Python is that integer size is essentially unlimited. It can have numbers that are far beyond practical without breaking a sweat. I've worked with million-digit numbers just for testing. – Mark Ransom Oct 23 '22 at 15:20
@sj95126 I'm not getting any errors at all, no segmentation fault, no nothing. – Youssef Gamil Oct 23 '22 at 19:34
@YoussefGamil: Sorry, it was someone else's comment I was referring to. My mistake. – sj95126 Oct 23 '22 at 19:35
that integer numbers in Python work seamless to the millions of digits does not mean they work _fast_ to the millions of digits. AFAIK the major burden is when they have to be converted to decimal as strings, though - and again, when recursing, one has to keep all those large numbers in memory - the numbers are big, the resources used due to recursion far less. – jsbueno Oct 24 '22 at 13:51
"I'm not getting any errors at all, no segmentation fault, no nothing" - that is likely due to the numbers themselves consuming too much resources. Moving to an interactive implementation would be of no help either. – jsbueno Oct 24 '22 at 14:05

Factorial function in python is being limited

1 Answers1