Python factorial using recursion

Question

I am trying to find a factorial of a large number using recursion in Python 3.6. Although I have set the recursion limit to 10**9, still running the code makes the kernel go dead. I know that iterative solutions are much better, yet I wanted to know the reason for this

import sys
mod = 10**9+7
sys.setrecursionlimit(10**9) 
def fac(n):
    if(n == 1):
        return 1
    return (fac(n-1)%mod*n%mod)%mod 
print(fac(10000))

The standard basis case for factorial is 0, not 1. Your code fails for 0!. Also, you have grouping problems, so in effect the final % does nothing. You need to add parentheses around (n%mod) if you want it to do what you intend. Also, it makes no sense to use recursion for factorial. It's a simple iteration. You shouldn't need to increase the stack limit at all. Factorial is not a good candidate for recursion. — Tom Karzes
– Tom Karzes, Commented Aug 10, 2020 at 12:15
can you explain mod? why not fac(n-1)*n? Is mod needed to demonstrate the stack overflow? — Mulan
– Mulan, Commented Aug 10, 2020 at 21:55
Not using mod will generate really large numbers with higher n leading to very slow implementation. Try the above code without mod for say n= 10000 or so. — Aman Oswal
– Aman Oswal, Commented Aug 18, 2020 at 14:28

user13897142 · Accepted Answer · 2020-08-10 12:17:21Z

1

Calculating factorial of such a large number results in overflow in stack memory as whenever we apply recursion all recursive calls get their own memory getting stacked over one another.

Therefore for such a large number, the recursive stack grows bigger and bigger with recursive calls resulting in stack overflow

Collectives™ on Stack Overflow

Python factorial using recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related