Given a non-negative integer n, return the product of all natural numbers from 1 to n.
Example 1
Input: n = 4
Output: 24
Explanation: The natural numbers to multiply are 1, 2, 3, and 4. Accumulating the product continuously (1 4 = 4, 4 3 = 12, 12 * 2 = 24) results in a final multiplied total of 24.
Example 2
Input: n = 5
Output: 120
Explanation: Accumulating the multiplication of the numbers from 5 down to 1 gives a final carried product of 120.
Approach 1
Parameterized recursion carries the product calculated so far into the next recursive call.
The running product begins with 1, since multiplying any number by 1 keeps its value unchanged. Before moving from n to n - 1, the current value is multiplied into the running product.
By the time n reaches 1, every required number has already been included, so the accumulated product is the final answer.
Algorithm
Define a recursive function with
nandcurrentProductas parameters, wherecurrentProductkeeps track of the multiplication completed so far.Start
currentProductwith1, because it allows the first multiplication to begin without changing the result.When
n <= 1, returncurrentProduct, as all values from the originalndown to2have already been multiplied.For a larger value of
n, call the function again withn - 1andcurrentProduct * n. This moves toward the base case while carrying the updated product forward.
Dry Run
Multiplication of N Parameterized Recursion Approach Dry Run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Builds the product by carrying the running result in each call. long long calculateProduct(int n, long long currentProduct) { // All required values have already been multiplied. if (n <= 1) { return currentProduct; } // Multiply the current value before moving to n - 1. return calculateProduct( n - 1, currentProduct * n ); }public: // Returns the product of all natural numbers from 1 to n. 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), where N is the given number. Each recursive call processes one value before moving to the next smaller value.
Space Complexity: O(N), because the recursive calls remain stored in the call stack until the base case is reached
Approach 2
Functional recursion does not carry a running product.
Instead, each call asks the smaller recursive call for the factorial of n - 1. Once that result is available, the current value n is multiplied with it.
The complete answer is therefore built while the recursive calls return from the base case.
Algorithm
Define a recursive function that receives only
n, since each call is responsible for returning the factorial of its current value.When
n <= 1, return1. This gives the multiplication a valid starting value and also handles0! = 1.For a larger value of
n, ask the smaller call for the factorial ofn - 1.Multiply the returned value by
nand return the result to the previous call.
Dry Run
Multiplication of N Functional Recursion Approach Dry Run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the product from 1 to n using recursive return values. long long factorial(int n) { // Product up to 0 or 1 is 1, which stops the recursion. if (n <= 1) { return 1; } // Multiply n with the product returned for n - 1. 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), where N is the given number. The function processes every value from N down to 1.
Space Complexity: O(N), because each call waits in the call stack until the smaller recursive call returns.
Interview follow-up Questions
Parameterized recursion carries the running product as an argument. Functional recursion receives the result from a smaller call and multiplies the current value while returning.
Be the first to add a comment.