FOR FREE CONTENT
Factorial with Recursion
Back to ProgrammingDescription
The factorial of a number is the product of the integer numbers from 1 to that number. If n is a number then the factorial of n=1×2×3×……×(n-2)×(n-1)×n. The factorial of n is also written as n!
The factorial of 0 is 1.
For example, 5! = 1×2×3×4×5 = 120.
Algorithm
INPUT: A number.
OUTPUT: Factorial of that number.
PROCESS:
Step 1: [Taking the input]
Read n [the number to find the factorial]
Step 2: [Defining a function ‘factorial(n)’ where n is the number and the function returns an integer]
If n=1 then
Return 1
Else
Return n × factorial(n-1)
[Here, the function ‘factorial(n)’ is called recursively]
[End of ‘if’]
Step 3: Set f<-1
If n≠0 then
Set f = factorial(n)
[End of ‘if’]
[Calling the function ‘factorial(n)’ for the first time and then the returned value is stored in a variable ‘f’]
Step 4: Print “The factorial is: f“.
Step 5: Stop.
Code
TIME COMPLEXITY:
Each time the factorial function is called, 3 operations are performed- 1 comparison, 1 multiplication and 1 subtraction. Therefore, the time complexity can be analyzed as:
T(n) = T(n-1) +3
T(0)=1
T(n) = T(n-1) + 3
= T(n-2) + 6
….
=T(n-p)+3p
If n-p=0 then we can find that n = p.
Therefore, T(n)=T(0)+3n
= 1+3n
Therefore, the complexity is O(n)
SPACE COMPLEXITY:
The space complexity of the factorial calculation using recursion is O(n) where n is the number.
Contributed by
