How to calculate the factorial of a large number using recursion in Python

How to calculate the factorial of a large number using recursion in Python.

Here's a detailed step-by-step tutorial on how to calculate the factorial of a large number using recursion in Python.

Step 1: Understanding the factorial function

The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n. For example, 5! (read as "5 factorial") is equal to 5 4 3 2 1, which equals 120.

Step 2: Writing the base case

In recursion, we always start by defining a base case, which is the simplest form of the problem that we can solve directly. For the factorial function, the base case is when the input number is 0 or 1, as 0! and 1! both equal 1. Therefore, if the input number is 0 or 1, we can simply return 1.

Step 3: Defining the recursive case

The recursive case is where we break down the problem into smaller subproblems until we reach the base case. In the case of factorial, we can define it as n! = n * (n-1)!. This means that to calculate the factorial of n, we need to calculate the factorial of n-1.

Step 4: Implementing the recursive function

Now that we understand the base case and recursive case, we can implement the recursive function to calculate the factorial of a given number.

def factorial_recursive(n):
    # Base case
    if n == 0 or n == 1:
        return 1
    # Recursive case
    else:
        return n * factorial_recursive(n-1)

In this code, we check if n is 0 or 1. If it is, we return 1 as the base case. Otherwise, we return n multiplied by the factorial of n-1, which is calculated by calling the same function recursively.

Step 5: Testing the function

To test the factorial_recursive function, you can call it with different input numbers and print the result.

print(factorial_recursive(5))  # Output: 120
print(factorial_recursive(10)) # Output: 3628800
print(factorial_recursive(0))  # Output: 1

These test cases will give you the factorial of 5, 10, and 0 respectively.

Step 6: Handling large numbers

The above implementation works well for small numbers. However, when dealing with large numbers, it may encounter a recursion depth limit or take a long time to compute. To handle large numbers, we can use the Python library math to calculate the factorial more efficiently.

import math

def factorial_large(n):
    return math.factorial(n)

The math.factorial function handles large numbers efficiently and returns the factorial directly.

Step 7: Testing the large number factorial function

To test the factorial_large function, you can call it with large input numbers and print the result.

print(factorial_large(100))   # Output: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
print(factorial_large(1000))  # Output: 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000

These test cases will give you the factorial of 100 and 1000, respectively.

That's it! You now know how to calculate the factorial of a large number using recursion in Python.