The Factorial Algorithm is great for recursion
What is factorial ?
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example
5! = 5 x 4 x 3 x 2 x 1 = 120. It is just the product of an integer and all the integers below it.-Wikepedia
The factorial program can be written recursively, because it is a function that calls itself.
1. func factorial(n)
2. if (n == 1)
3. return 1
4. return n * factorial(n -1)
if(n == 1)
return n *factorial(n-1);
You can see how to convert a function to recurrence relation in this video, it’s not the factorial function, but a function with the same recurrence relation.
Write the factorial function as a recurrence relation
This function written as a recurrence relation is:
T(n)=1 for n=0
T(n)=1+T(n-1) for n>0
This recurrence running time in Big O notation is: **O(n)**, which is the main purpose for converting algorithms to recurrence relations.
you can learn how to solve this from this video
Let’s look at an example:
Suppose we had a arbitrary number n=5, so we use the function factorial(5)
We get the following Number of iterations
1) factorial(5) = 5 * factorial(4)
2) factorial(4) = 4 * factorial(3)
3) factorial(3) = 3 * factorial(2)
4) factorial(2) = 2 * factorial(1)
5) factorial(1) = 1
So the factorial function called itself 5 times which is the exact same number of the input size’n’, where n = 5. So the recurrence ran ’n’ times, and is therefore O(n).
Thanks for reading this article I hope it’s helpful to you all ! Keep up the learning, and if you would like more algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )
Check Out the following for more content / videos on Algorithm Analysis and Programming:
Video Tutorials on Recurrence Relation:
Video Tutorial on Algorithm Analysis: