0% completed
Problem Statement
Calculate the Factorial of a Positive Number Using Recursion.
The factorial of a non-negative integer N, denoted as N!, is the product of all positive integers less than or equal to N. The factorial of 0 is defined as 1.
Here is what the example input/output looks like:
| Input | Expected Output | Explanation |
|---|---|---|
| Number = 5 | Factorial = 120 | The factorial of 5 is calculated as 5 _ 4 _ 3 _ 2 _ 1 = 120. |
| Number = 7 | Factorial = 5040 | The factorial of 7 is calculated as 7 _ 6 _ 5 _ 4 _ 3 _ 2 _ 1 = 5040. |
| Number = 1 | Factorial = 1 | The factorial of 1 is 1 itself. |
Solution
The algorithm to calculate the factorial of a positive number using recursion can be defined as follows:
- If the given number is 0 or 1, return 1 (base case).
- Otherwise, return the product of the number and the recursive call to calculate the factorial of the number minus 1.
The recursive approach works by breaking down the problem into smaller subproblems. We calculate the factorial of a number by multiplying it with the factorial of the number minus 1. This process continues until the base case is reached, where the number is 0 or 1. The base case stops the recursion and returns 1.
By multiplying the numbers in decreasing order, we ensure that each number is multiplied with the product of the previous numbers, eventually giving us the factorial of the given number.
Code
Here is the code for this algorithm:
Time and Space Complexity
The time complexity of the algorithm is O(N) since we make N recursive calls, where N is the given input.
The space complexity of the algorithm is also O(N) because the maximum depth of the recursion is N. Each recursive call adds a new stack frame, consuming additional space on the call stack.
Table of Contents
Problem Statement
Solution
Code
Time and Space Complexity