The factorial of a number, denoted as n!, is the product of all integers between n and 1. n! = n x (n-1) x (n-2) … x1. The value of 0! is 1. You can use iteration and recursion in implementation.
Table of Content
Iteration
In iteration implementation, you assign the initial value of fact to be 1. This is default value for number 0 and 1. Then you use for loop iterate from 2 to the input number. Each time fact is updated to previous fact times the loop variable i. When it finishes, return fact.
Java
|
1 2 3 4 5 6 7 |
//Iteration, Time O(n), Space O(1), n is input number public static int factorial(int num) { int fact = 1; for (int i = 2; i <= num; i++) fact *= i; return fact; } |
Javascript
|
1 2 3 4 5 6 7 |
//Iteration, Time O(n), Space O(1), n is input number function factorial(num) { var fact = 1; for (let i = 2; i <= num; i++) fact *= i; return fact; } |
Python
|
1 2 3 4 5 6 |
#Iteration, Time O(n), Space O(1), n is input number def factorial(num) : fact = 1 for i in range(2, num+1): fact *= i return fact |
Doodle
Recursion
In recursion implementation, the function calls itself with input number minus 1. The base condition is when the input number is 0, function returns 1. Then the call stack returns. The recursion simplifies the problem conceptually, but is not as efficient as loop-based approach.
Java
|
1 2 3 4 5 6 |
//Recursion, Time O(n), Space O(n) public static int fact(int num) { if (num == 0) //base condition return 1; return num * fact(num-1); } |
Javascript
|
1 2 3 4 5 6 |
//Recursion, Time O(n), Space O(n) function factRec(num) { if (num == 0 ) //base condition return 1; return num * factRec(num-1); } |
Python
|
1 2 3 4 5 |
#Recursion, Time O(n), Space O(n) def factRec(num) : if num == 0 : #base case return 1 return num * factRec(num-1); |
Doodle
Download Java, JavaScript and Python code
Factorial number animated