You use it to find the number of different ways you can design a seating arrangement, or choose t-shirts for your vacation to the Maldives. But how can you calculate the factorial of a number?
What Is the Factorial of a Number?
The factorial of a positive number is the product of all positive integers less than or equal to the value of the number itself. A number followed by an exclamation mark(!) denotes the factorial of a number. You represent the factorial of five as 5! and calculate it as:
5! = 5 * 4 * 3 * 2 * 1 = 120
Another way to visualize it is:
5! = 5 * 4! where 4! = 4 * 3!, 3! = 3 * 2! and so on until you get 1! = 1 * 0! which is 1.
You will use this concept to build our factorial program using a popular concept called recursion.
What Is Recursion?
Recursion is a process in which a function calls itself. One of the main advantages of this process is that it breaks a bigger problem into smaller chunks. This makes the problem easier to solve.
You can use recursion to solve appropriate problems in three easy steps:
Find the base case: If a function always calls itself, the process will be infinite. To prevent this from happening, define a base case that becomes the logical stopping point for your function. For example, in a factorial program, stop the calculation at zero. This becomes the base case for the problem. Find the relation between the problem and the subproblems: Break down the bigger problem into a subproblem. For example, the problem is to find the factorial of five. Assume you have the answer of factorial of four, that is 24. How will you get the factorial of five using 24? By multiplying five itself into it. This is the relation between the problem and the subproblem. Generalize the relation found in Step 2: Now that you have the relation, generalize it in terms of n. So, the factorial of a number n is the product of n and the factorial of n-1.
You can use this concept to find the sum of n natural numbers, calculate GCD, LCM, the Fibonacci series, and check prime numbers.
Pseudo Code for the Factorial Function Using Recursion
This is how you use recursion and write the pseudo code to build your program in any language. With different languages, the syntax and execution change but the logic remains intact.
Factorial Program in C
C was the first high-level, platform-independent programming language. It has strict syntax, is case-sensitive, and executes code with the fastest speed. It is a procedural programming language and hence you declare any function on top of the main function. Here’s how you can build the factorial program using recursion in C language:
Import the standard input output header file for displaying the output to the screen. #include <stdio. h> Define function fact and take integer n as an argument. int fact(int n) { Write the base case of the function using the if statement and check its equality using ==. If n equals zero, return one. if (n == 0) return 1; Write the generalized equation and return the product of n with a function call of subproblem n-1. return n * fact(n - 1);} Declare the main function and initialize a variable of integer type to store the number whose factorial you want to find. int main() { int num = 5; Display the factorial of the number using the printf() function. %d is the decimal format specifier. Use each of the format specifiers to replace it with the number whose factorial you want to find and get the result by calling the function. printf(“Factorial of %d is %d”, num, fact(num)); return 0;}
Factorial Program in Java
Java is a compiled programming language and is platform-independent. You store all the code inside a class and the execution begins from the main function. It is case-sensitive and syntax strict. The code is a bit longer but faster compared to Python. Here’s how you can build the factorial program using recursion in Java:
Define the Main class. class Main { Define a static function with return type int that accepts a variable n of integer type. You declared a static method as the main method in Java is also declared as static. Additionally, you cannot call a non-static method from a static instance. static int fact(int n) { Write the base case of the function using the if statement and check its equality using ==. If n equals zero, return one. if (n == 0) return 1; Write the generalized equation and return the product of n with a function call of subproblem n-1. return n * fact(n - 1); } Declare the main function in Java. Declare the access modifier as public, so it can be accessible by all the other classes and methods. You declare the main function as static so that the compiler can invoke it without instantiating the class. The return type is void, and it accepts arguments of type String. Store the number whose factorial you want to find. public static void main(String[] args) { int num = 5; Use the println() method, an instance of the PrintStream class, defined in the System class to display the factorial of the number. System. out. println(“Factorial of " + num + " is " + fact(num)); }}
Factorial Program in Python
Writing code in Python is super easy and fun. As it’s an interpreted platform-independent language, you don’t have to declare the data type of variables. You also avoid having to declare classes and import libraries for such a simple program. The playground is ready for you to start coding.
The syntax is easier, with a small code length but takes a little more time to execute than the other languages. Here’s how you can build the factorial program using recursion in Python:
Define function fact that accepts as argument n. def fact(n): Write the base case of the function using the if statement and check its equality using ==. If n equals zero, return one. if n == 0: return 1 Write the generalized equation and return the product of n with a function call of subproblem n-1. return n * fact(n-1) Store the number whose factorial you want to find and display it using the print statement. num = 5;print(“Factorial of”, num, “is”, fact(num))
There Are Many Applications of Recursion
Recursion is an effective way of solving problems. It is the crux of Artificial Intelligence and has real-world uses in puzzle games such as chess or Sudoku.
It’s also a powerful method for sorting data structures such as Tree or sorting algorithms such as Quick sort and Merge sort. You might also use recursion in searching algorithms like Binary search, mathematical expressions such as the Fibonacci series, and more.
