## Factorial with Recursion

Back to Programming

### Description

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.

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