Problem link - Factorial
Problem Statement:
Given an integer N, calculate and output the factorial of a N. Factorial of an integer N is the product of first N natural numbers.
Recursive equation for Factorial:
Factorial(n) = N∗Factorial( n − 1 ), Factorial(0)=1, Factorial(1)=1
Approach:
The key idea of this solution is to use recursion to calculate the factorial of the number N. Recursion is a technique where a function calls itself to solve smaller subproblems until a base condition is met.
Here’s how the logic works:
- Base Case:
- If N is 0 or 1, the function directly returns 1 because by definition, 0! = 1 and 1! = 1.
- Recursive Case:
- For any number greater than 1, the function multiplies N by the factorial of N - 1.
- This recursive call continues reducing the value of N until the base case is met, at which point the recursion stops, and the results are multiplied together to give the final result.
Time Complexity:
- O(N) because the function makes N recursive calls to calculate the factorial.
Space Complexity:
- O(N) due to the recursive call stack, where each recursive call takes space.