Understand Factorial CPP Problem

Problem Name: Factorial CPP

Problem Description:

Topic: Factorials - A Breakdown and Recursive Approach

Difficulty: Easy to Moderate
Topics: Recursion, Iterative Algorithms, Mathematics
Applications: Used in combinatorics, probability, and programming challenges.

Concept of Factorials

Imagine you have a set of building blocks, and you want to know how many unique structures you can create by stacking them in every possible arrangement. This is the idea behind factorials in mathematics.

Definition

The factorial of a number n, written as n! (n factorial), represents the total number of ways you can arrange a set of n distinct objects.

Example

For n = 3 (3 blocks):

3! = 3 \times 2 \times 1 = 6 \text{ unique arrangements.}

Recursive Approach to Factorials

What is Recursion?

Recursion involves solving a problem by breaking it down into smaller, similar subproblems. A recursive function calls itself within its body but with a smaller input until it reaches a base case (a condition where the function stops calling itself).

Factorial Using Recursion

To calculate n! using recursion:

Multiply n by the factorial of n-1.
Continue this process until n reaches the base case, where n = 1 or n = 0.

For these cases:

0! = 1 \quad \text{and} \quad 1! = 1.

Recursive Formula

n! = n \times (n-1)!

Example Walkthrough

Find `5!` Recursively:

5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1 (Base case reached)

Result:

5! = 5 \times 4 \times 3 \times 2 \times 1 = 120

Test Cases

Test Case 1: Small Number

Input:
n = 5

Execution:
factorial_recursive(5)

Output:
120

Test Case 2: Base Case (`n = 0`)

Input:
n = 0

Execution:
factorial_recursive(0)

Output:
1

Test Case 3: Base Case (`n = 1`)

Input:
n = 1

Execution:
factorial_recursive(1)

Output:
1

Test Case 4: Larger Number

Input:
n = 10

Execution:
factorial_recursive(10)

Output:
3628800

Category:
Arrays
Backtracking
DP

Programming Language:
C++

Reference Link:

https://www.geeksforgeeks.org/problems/factorial5739/1?itm_source=geeksforgeeks&itm_medium=article&itm_campaign=bottom_sticky_on_article

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

INPUT: N =5

OUTPUT: 120

int main() {

int num = 5; // Example input

cout << "Factorial of " << num << " is " << factorial(num) << endl;

return 0;

}//function end

Helper Function:

int factorial(int n) {

if (n <= 1){

return 1;

}

int ans = factorial(n - 1);

return n * ans;

}

Utility Functions and Global variables:

Utility Function is not required.