Problem Statement
The task is to calculate the factorial of a non-negative integer. The factorial of a number is the product of all positive integers less than or equal to that number.
Definition
- The factorial of a number
n is represented as n!.
- Formula:
n! = n imes (n - 1) imes (n - 2) imes ... imes 1
- Special Case:
0! = 1 (by definition)
Example Inputs
Explanation: The factorial of 5 is calculated as 5! = 5 imes 4 imes 3 imes 2 imes 1 = 120.
Approach - Use Recursion
Approach
Recursion is a method in which a function calls itself. In the case of calculating factorial, we use the principle that n! = n imes (n-1)!. This means that to calculate the factorial of a number n, we can break the problem into smaller sub-problems by calculating the factorial of n-1, and multiply it by n.
Steps
- Define the base case for recursion: If the number is 0 or 1, return 1.
- For other numbers, recursively call the function with the number reduced by 1, and multiply the result by the current number.
- Continue the recursion until the base case is reached.
- Return the final result.
Time & Space Complexity
- Time Complexity: O(n), where
n is the input number. We make n recursive calls until we reach the base case.
- Space Complexity: O(n), due to the recursion stack. Each recursive call adds a new layer to the stack.
Code Snippet
Dry Run
Let’s dry run the code with the input 5.
- factorial(5): 5 * factorial(4)
- factorial(4): 4 * factorial(3)
- factorial(3): 3 * factorial(2)
- factorial(2): 2 * factorial(1)
- factorial(1): 1 (base case)
- Return from factorial(1): 1
- Return from factorial(2): 2 * 1 = 2
- Return from factorial(3): 3 * 2 = 6
- Return from factorial(4): 4 * 6 = 24
- Return from factorial(5): 5 * 24 = 120
Output:
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(n) because we make
n recursive calls.
- Space Complexity: O(n) due to the recursion stack. Each recursive call adds a new frame to the stack.
Conclusion
Using recursion to calculate the factorial of a number is a simple and elegant solution. The recursion stack makes the solution intuitive by breaking the problem into smaller subproblems. However, for larger numbers, recursion may lead to a stack overflow or inefficiency due to the large number of function calls. Non-recursive (iterative) solutions can be more efficient in such cases.