Monday, July 23, 2018

Recursion to calculate Factorial

Recursion is the method of breaking down a problem into sub-parts, progressively into smaller and smaller parts, such that the last part's solution becomes easily/manually solvable.

To know factorial of 5 i.e 5! which is 5*4!, we need factorial of 4.

Hence the recursive code, recursively calls the same logical code/method to find 4!, which in turn would require 3! ; then 2! ; and then 1! and ultimately 0! which is known to be 1.

Knowing 0!=1 ; would trace back the path in backward way i.e we would know 1!=1*0!=1*1=1
3!=3*2!=3* 2=6

Generalizing this algorithmic logic

Similarly to know factorial of any integer n, Recursion goes back all the way from n to (n-1) to (n-2) and so on to 0! ;
and then traces back in the reverse direction, from 0!=1 to 1! to 2! to 3! and so on to ultimately get the answer of n!


No comments: