Given an integer n, compute the factorial of n (denoted as n!) using a recursive function. The factorial of a number is the product of all positive integers less than or equal to n.
Example 1
Input: n = 4
Output: 24
Explanation: The factorial calculation is 4 * 3 * 2 * 1, which results in a final multiplied total of 24.
Example 2
Input: n = 0
Output: 1
Explanation: By absolute mathematical definition, the factorial of 0 is exactly 1.
Approach 1
In parameterized recursion, the product is built while moving toward the base case.
Along with n, the function carries a parameter called currentProduct. It stores the multiplication completed so far. Before moving to n - 1, the current value of n is multiplied into this running product.
The product starts with 1, since multiplying by 1 does not change the result. When n reaches 0, every required value has already been included, so currentProduct contains the factorial.
Algorithm
Use a recursive function with two parameters:
nandcurrentProduct. ThecurrentProductparameter keeps track of the multiplication completed during the earlier calls.Start
currentProductwith1, as1is the neutral value for multiplication and allows the product to build correctly.When
nbecomes0, returncurrentProduct, because all numbers from the original value ofndown to1have already been multiplied.For a positive value of
n, call the function withn - 1andcurrentProduct × n. This includes the current number in the product and moves the recursion closer to the base case.
Dry Run
Factorial of N Parameterized Recursion Appraoch Dry Run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Carries the product built // during previous recursive calls. long long calculateProduct( int n, long long currentProduct ) { // All required values // have already been multiplied. if (n == 0) { return currentProduct; } // Include n in the product // and move toward the base case. return calculateProduct( n - 1, currentProduct * n ); }public: // Returns factorial using // parameterized recursion. long long factorial(int n) { return calculateProduct(n, 1); }};int main() { int n = 5; Solution solution; cout << solution.factorial(n) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because one recursive call processes each number from N down to 1.
Space Complexity: O(N), because every recursive call adds a frame to the call stack until the base case is
Approach 2
Factorial can be broken into a smaller version of the same problem.
For example:
5! = 5 × 4!In general:
n! = n × (n - 1)!Each call asks the smaller recursive call for (n - 1)!. Once that value is returned, the current value of n is multiplied with it.
Here, the product is formed while the recursive calls return from the base case
Algorithm
Use a recursive function that takes only
n, since each call is responsible for returning the factorial of its current value.When
n <= 1, return1, because both0!and1!are equal to1.For a value greater than
1, ask the smaller recursive call for the factorial ofn - 1.Multiply the returned value by
nand return the result to the previous call.
Dry Run
Factorial of N Functional Recursion Appraoch Dry Run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns factorial using // functional recursion. long long factorial(int n) { // Both 0! and 1! // are equal to 1. if (n <= 1) { return 1; } // Use the smaller factorial // to build the current result. return n * factorial(n - 1); }};int main() { int n = 5; Solution solution; cout << solution.factorial(n) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because each number from N down to 1 is handled once.
Space Complexity: O(N), because the calls remain in the call stack until the smaller factorial values are returned.
FAQs
Q1. Why is the factorial of 0 equal to 1?
0! is defined as 1. This also keeps the recursive relation consistent, since 1! = 1 × 0!.
Q2. Why does the running product start with 1 in parameterized recursion?
Starting with 1 allows multiplication to build normally. Starting with 0 would make every later product equal to 0.
Q3. What is the difference between parameterized and functional recursion?
Parameterized recursion carries the running product into each call. Functional recursion gets the product from a smaller call and multiplies the current value while returning.
Q4. What happens when n is negative?
Factorial is not defined for negative integers. Such input should be rejected or handled separately before starting the recursion.
Q5. Can factorial values overflow an integer type?
Yes. Factorials grow very quickly. A 32-bit signed integer can store values only up to 12!, while a 64-bit signed integer can store values only up to 20!.
Q6. Can factorial be calculated without recursion?
Yes. An iterative loop can calculate factorial using O(N) time and O(1) auxiliary space, avoiding the recursive call stack.
Be the first to add a comment.