Recursive program to calculate factorial of a number
Write a recursive C/C++, Java, and Python program to calculate the factorial of a given non-negative number.
The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It is denoted by n!. There are n! different ways to arrange n distinct objects into a sequence. For example,
5! = 1 × 2 × 3 × 4 × 5 = 120
The value of 0! is 1
We can recursively define the problem as:
| 1 if n = 0
For example,
2! = (1) × 2 = 1! x 2 = 2
3! = (1 × 2) x 3 = 2! x 3 = 6
4! = (1 × 2 × 3) × 4 = 3! x 4 = 24
5! = (1 × 2 × 3 × 4) × 5 = 4! x 5 = 120
6! = (1 × 2 × 3 × 4 × 5) x 6 = 5! x 6 = 720
This is demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <stdio.h> // Recursive function to calculate factorial of a number unsigned long factorial(int n) { // base case: if `n` is 0 or 1 if (n < 1) { return 1; } // use the recurrence relation return n * factorial(n - 1); } int main() { int n = 5; printf("The Factorial of %d is %lu", n, factorial(n)); return 0; } |
Output:
The Factorial of 5 is 120
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Main { // Recursive function to calculate factorial of a number public static int factorial(int n) { // base case: if `n` is 0 or 1 if (n < 1) { return 1; } // use the recurrence relation return n * factorial(n - 1); } public static void main(String[] args) { int n = 5; System.out.println("The Factorial of " + n + " is " + factorial(n)); } } |
Output:
The Factorial of 5 is 120
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Recursive function to find factorial of a number def factorial(n): # base case: if `n` is 0 or 1 if n < 1: return 1 # use the recurrence relation return n * factorial(n - 1) if __name__ == '__main__': n = 5 print(f'The Factorial of {n} is', factorial(n)) |
Output:
The Factorial of 5 is 120
The time complexity of the above solution is O(n), and the auxiliary space used by the program is O(n) for the call stack.
We can also write the above recursive program in a single line, as shown below:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <stdio.h> // Recursive function to calculate factorial of a number unsigned long factorial(int n) { return (n < 1) ? 1 : n * factorial(n - 1); } int main() { int n = 6; printf("The Factorial of %d is %lu", n, factorial(n)); return 0; } |
Output:
The Factorial of 6 is 720
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Main { // Recursive function to calculate factorial of a number public static long factorial(int n) { return (n < 1) ? 1 : n * factorial(n - 1); } public static void main(String[] args) { int n = 6; System.out.println("The Factorial of " + n + " is " + factorial(n)); } } |
Output:
The Factorial of 6 is 720
Python
Also see:
Exercise: Efficiently print factorial series in a given range.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)