Recursion

Recursion in programming can be applied to solve a problem whose solution depends on the solutions to smaller instances of the same problem. We can therefore say that Recursion refers to a function, which can calculate the right answer by first solving a smaller version of its own self and then using that result along with some more computation to get the final answer.

Let’s have a look at our example of finding the factorial of a number. A factorial of a number is the product of that number and all positive integers below it. So, factorial of 5 or 5! can also be represented as follows:

5! = 5 * 4 * 3 * 2 * 1 …….(1)

Now, look at the preceding statement carefully. Since a factorial of a number is product of that number and all positive numbers below it we can say that 4 * 3

* 2 * 1 = 4!. Hence, statement (1) can be rewritten as:

5! = 5 * 4 * 3* 2 * 1 = 5 * 4! ……(2)

Following the definition of factorial, we can now write (2) as:

5! = 5 * 4 * 3 * 2 * 1 =5 * 4 * 3! ……(3)

Similarly,

5! = 5 * 4 * 3 * 2 * 1 =5 * 4 * 3 * 2! …….(4)

So, if we define a method find_factorial(n) to find factorial of number n, it would mean that find_factorial(n) is same as n * find_factorial(n-1) and find_factorial(n-1) is same as (n-1) * find_factorial(n-2), and so on.

Therefore, as we start writing the code for recursion, the following may seem like the right way to start. However, the following code is not complete yet.

def find_factorial(n):

return n*find_factorial(n-1)

At this point, it is important to understand base case or terminal case. Every problem in recursion has a base case. It is one or more special values for which a function can be evaluated without recursion or it is that part of the recursion problem, which cannot be defined in smaller instances of itself. Without a base case a recursive function will never stop executing. A recursive function makes calls to itself, which step by step takes the function to the base case, and the function then stops executing.

So, the preceding code is not complete because it has no base case. As per the definition of factorial, we say that factorial of a number is the product of itself with all the positive numbers below it. This means that the last number to be multiplied is always 1. Thus, the function should stop executing when a call is made to it with value n= 1. This will be the base case for our find_factorial() function.

def find_factorial(n):

if(n==1):

return 1

return n*find_factorial(n-1)

print (find_factorial (5))

So the Algorithm for finding factorial using recursion will be -

Function find_factorial(n):

Step 1: Read the number n provided for finding factorial.

Step 2: Check whether the value provided is equal to 1. If true, return 1.

Step 3: Else return value of n*find_factorial(n-1).