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:

1. Multiply n by the factorial of n-1.
2. 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:

1. 5! = 5 × 4!
2. 4! = 4 × 3!
3. 3! = 3 × 2!
4. 2! = 2 × 1!
5. 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

---

— Written by Saurabh Patil • B.Tech CSE • Software Developer