FACTORIAL IN PYTHON USING RECURSION:
Let’s first see what is factorial and what is recursion, in order to completely understand the concept behind its implementation.
Basically it is the product of an integer and all the integers below it.
1. 4! = 4 x 3 x 2 x 1 = 24
2. 7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040
In order words, we can say that
n! = n x(n-1)!
This is the concept or the formula, that we are going to use in our program for finding the factorial of a number using recursion in Python.
Now recursion seems a bit complicated to understand but actually it is not that complicated at all. In simple words, we can say that the process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called recursive function.
Now there are certain problems that we can solve with recursion very easily which are otherwise very difficult to solve using any other method.
Thus a recursive function performs a task in part by calling itself to perform the sub-tasks. Generally there are two cases in a recursive function.
1. Base Case: It the most fundamental case where the function does not recur i.e. it can perform the subtask without calling itself.
2. Recursive Case: It this case the function calls itself to perform the subtask.
General format of a recursive function (in Python)
if (test for base case):
return some base case value
return some work and then a recursive call
Now that you have got the basic idea about what is factorial and what is recursion, let’s see how we implement these to make a program for finding factorial of a number using Python.
if n == 0:
n = input('Enter the number you want to find the factorial of: ')
answer = fact(int(n))
Now let’s understand each line of code step by step:
- First we define a function fact & pass it a parameter n which is actually a variable.
- In line 2, we are testing for base case as “if the number for which we are going to find factorial is zero then return 1 as 0! = 1 (factorial of zero is one)”
- In line 3, we are testing for recursive case as “else if number is not zero then return the number multiplied by the factorial of (number – 1)” .This is the recursive statement as fact function is calling itself and we are passing the parameter number – 1 as n! = n x(n-1)!
- Now what happens is, let’s say the number is 3 then first it check the condition that if number is zero then return 0, which is not true here. Then it goes to the else statement and return 3 x fact (2).
- Now number becomes 2, therefore again it returns 3 x 2 x fact (1)
- Instantly number becomes 1, therefore again it returns 3 x 2 x 1 x fact (0)
- Now number becomes 0, therefore again it returns 1
- So the final value that is returned is 3 x 2 x 1 x 1 = 6, which is the factorial of 3.
- Now in line 6, we are asking for the number n using built in input function in Python.
- In line 7, we are storing the result of fact function in a variable named answer. Now if you notice carefully, I am casting variable n into an integer using int. This is because the built in input function in Python returns string and to be on a safer side, we are casting our variable n into an integer.
- In line 8, we are just printing the answer using built in print function.
For more information:
Check out more about Python: https://docs.python.org/3/