Find all factorial numbers less than or equal to n
Write a recursive program to find all factorial numbers less than or equal to n.
The factorial n! of a non-negative integer n is the product of all positive integers less than or equal to n. For example, the factorial of number 5 is 120, and the factorial of number 6 is 720, and so on…
The factorial of a number can be recursively defined as:
n! = | n * fact(n – 1) if n > 1
| 1 if n = 0 or n = 1
| 1 if n = 0 or n = 1
A simple solution is to call the factorial function for every number less than or equal to n using the above recurrence. 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 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <stdio.h> // Recursive function to calculate factorial of a number unsigned long fact(int n) { // base case: if `n` is 0 or 1 if (n < 1) { return 1; } // use the recurrence relation return n * fact(n - 1); } // Naive function to efficiently print factorial series in a given range void factorial(int beg, int end) { // check for invalid input if (beg < 0 || end < 0 || beg > end) { return; } // call `fact()` function for every number in the given range for (int i = beg; i <= end; i++) { printf("The factorial of %d is %lu\n", i, fact(i)); } } int main() { int beg = 1; int end = 10; factorial(beg, end); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class Main { // Recursive function to calculate factorial of a number public static long fact(int n) { // base case: if `n` is 0 or 1 if (n < 1) { return 1; } // use the recurrence relation return n * fact(n - 1); } // Naive function to print factorial series in a given range public static void factorial(int beg, int end) { // check for invalid input if (beg < 0 || end < 0 || beg > end) { return; } // call `fact()` function for every number in the given range for (int i = beg; i <= end; i++) { System.out.printf("The factorial of %d is %d\n", i, fact(i)); } } public static void main(String[] args) { int beg = 1; int end = 10; factorial(beg, end); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# Recursive function to calculate factorial of a number def fact(n): # base case: if `n` is 0 or 1 if n < 1: return 1 # use the recurrence relation return n * fact(n - 1) # Naive function to print factorial series in a given range def factorial(beg, end): # check for invalid input if beg < 0 or end < 0 or beg > end: return # call `fact()` function for every number in the given range for i in range(beg, end + 1): print(f'The factorial of {i} is {fact(i)}') if __name__ == '__main__': beg = 1 end = 10 factorial(beg, end) |
Output:
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of 3 is 6
The factorial of 4 is 24
The factorial of 5 is 120
The factorial of 6 is 720
The factorial of 7 is 5040
The factorial of 8 is 40320
The factorial of 9 is 362880
The factorial of 10 is 3628800
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of 3 is 6
The factorial of 4 is 24
The factorial of 5 is 120
The factorial of 6 is 720
The factorial of 7 is 5040
The factorial of 8 is 40320
The factorial of 9 is 362880
The factorial of 10 is 3628800
The above solution calculates the factorial function repeatedly for each number less than or equal to n. An efficient solution is to call the factorial function only once for a number n and calculate the factorial of all numbers less than n in the same function call, as 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 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <stdio.h> // Recursive function to calculate factorial of a number unsigned long fact(int n, long F[]) { // base case: if `n` is 0 or 1 if (n < 1) { return 1; } // use the recurrence relation to calculate F[n] F[n] = n * fact(n - 1, F); return F[n]; } // Function to efficiently print factorial series in a given range void factorial(int beg, int end) { // check for invalid input if (beg < 0 || end < 0 || beg > end) { return; } // F[i] stores factorial of `i` long F[end + 1]; // call fact() only once for the last number in the given range // (This will also calculate factorial of all numbers less than it) fact(end, F); // print the results for (int i = beg; i <= end; i++) { printf("The factorial of %d is %lu\n", i, F[i]); } } int main() { int beg = 1; int end = 10; factorial(beg, end); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Main { // Recursive function to calculate factorial of a number public static long fact(int n, long[] F) { // base case: if `n` is 0 or 1 if (n < 1) { return 1; } // use the recurrence relation to calculate F[n] F[n] = n * fact(n - 1, F); return F[n]; } // Function to efficiently print factorial series in a given range public static void factorial(int beg, int end) { // check for invalid input if (beg < 0 || end < 0 || beg > end) { return; } // F[i] stores factorial of `i` long[] F = new long[end + 1]; // call fact() only once for the last number in the given range // (This will also calculate factorial of all numbers less than it) fact(end, F); // print the results for (int i = beg; i <= end; i++) { System.out.printf("The factorial of %d is %d\n", i, F[i]); } } public static void main(String[] args) { int beg = 1; int end = 10; factorial(beg, end); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# Recursive function to calculate factorial of a number def fact(n, F): # base case: if `n` is 0 or 1 if n < 1: return 1 # use the recurrence relation to calculate F[n] F[n] = n * fact(n - 1, F) return F[n] # Function to efficiently print factorial series in a given range def factorial(beg, end): # F[i] stores factorial of `i` F = [0] * (end + 1) # check for invalid input if beg < 0 or end < 0 or beg > end: return # call fact() only once for the last number in the given range # (This will also calculate factorial of all numbers less than it) fact(end, F) # print the results for i in range(beg, end + 1): print(f'The factorial of {i} is {F[i]}') if __name__ == '__main__': (beg, end) = (1, 10) factorial(beg, end) |
Output:
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of 3 is 6
The factorial of 4 is 24
The factorial of 5 is 120
The factorial of 6 is 720
The factorial of 7 is 5040
The factorial of 8 is 40320
The factorial of 9 is 362880
The factorial of 10 is 3628800
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of 3 is 6
The factorial of 4 is 24
The factorial of 5 is 120
The factorial of 6 is 720
The factorial of 7 is 5040
The factorial of 8 is 40320
The factorial of 9 is 362880
The factorial of 10 is 3628800
Also See:
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 :)