Why Factorial Using Recursion in DSA Javascript?

The Big Idea

Discover how a function calling itself can solve big problems step by step!

The Scenario

Imagine you want to find the factorial of a number, like 5! (which means 5 x 4 x 3 x 2 x 1). Doing this by hand means multiplying all numbers one by one, which can get tricky and slow for bigger numbers.

The Problem

Manually multiplying each number is slow and easy to mess up, especially if the number is large. You might forget a number or multiply in the wrong order, causing mistakes.

The Solution

Recursion lets the computer break the problem into smaller, similar problems. It solves the factorial by calling itself with smaller numbers until it reaches 1, making the process simple and error-free.

Before vs After

✗ Before

function factorial(number) {
  let result = 1;
  for (let i = number; i > 0; i--) {
    result *= i;
  }
  return result;
}

✓ After

function factorial(number) {
  if (number <= 1) return 1;
  return number * factorial(number - 1);
}

What It Enables

Recursion enables solving complex problems by breaking them down into simpler, repeatable steps automatically.

Real Life Example

Calculating combinations in probability, where factorials are used to find how many ways to arrange or select items.

Key Takeaways

Manual multiplication is slow and error-prone for factorials.

Recursion breaks the problem into smaller, easier steps.

Recursive factorial is simpler and less error-prone.

Practice

1. What does the factorial of a number represent in mathematics?

easy

A. The number multiplied by 2

B. The sum of all positive integers up to that number

C. The product of all positive integers up to that number

D. The number divided by 2

Solution

1. Step 1: Understand factorial definition

   Factorial of a number n (written as n!) is the product of all positive integers from 1 to n.

2. Step 2: Compare options with definition

   Only The product of all positive integers up to that number matches this definition exactly.

3. Final Answer:

   The product of all positive integers up to that number -> Option C

4. Quick Check:

   Factorial = product sequence [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial doubles the number
• Mixing factorial with division

2. Which of the following is the correct base case for a recursive factorial function in JavaScript?

easy

A. if (n === 1) return n * factorial(n - 1);

B. if (n === 1) return 0;

C. if (n === 0) return 0;

D. if (n === 0) return 1;

Solution

1. Step 1: Identify base case for factorial

   Factorial of 0 is defined as 1, so base case should return 1 when n is 0.

2. Step 2: Check options for correct base case

   if (n === 0) return 1; returns 1 when n is 0, which is correct. Others either return wrong values or recursive calls.

3. Final Answer:

   if (n === 0) return 1; -> Option D

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Base case for factorial(0) is 1 [OK]

Common Mistakes:

• Returning 0 for factorial(0)
• Using recursive call in base case
• Confusing base case with recursive step

3. What will be the output of the following JavaScript code?

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. 24

B. 10

C. 16

D. 120

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1 * factorial(0) factorial(0) = 1 (base case)

2. Step 2: Calculate values bottom-up

   factorial(1) = 1 * 1 = 1 factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24

3. Final Answer:

   24 -> Option A

4. Quick Check:

   4! = 24 [OK]

Hint: Multiply down from n to 1 recursively [OK]

Common Mistakes:

• Adding instead of multiplying
• Stopping recursion too early
• Misunderstanding base case

4. Find the error in this recursive factorial function:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n + 1);
}

medium

A. The base case should be n === 0, not n === 1

B. The recursive call should use n - 1, not n + 1

C. The function should return n + factorial(n - 1)

D. There is no error; the function is correct

Solution

1. Step 1: Analyze recursive call direction

   The function calls factorial(n + 1), which increases n, causing infinite recursion.

2. Step 2: Correct recursive call

   To reach base case, n should decrease by 1 each call: factorial(n - 1).

3. Final Answer:

   The recursive call should use n - 1, not n + 1 -> Option B

4. Quick Check:

   Recursion must move toward base case [OK]

Hint: Recursive calls must reduce n to base case [OK]

Common Mistakes:

• Increasing n in recursive call
• Wrong base case value
• Using addition instead of multiplication

5. Consider this modified factorial function that returns the factorial of n only if n is even, otherwise returns 0:

function evenFactorial(n) {
  if (n === 0) return 1;
  if (n % 2 !== 0) return 0;
  return n * evenFactorial(n - 2);
}
console.log(evenFactorial(6));

What is the output of this code?

hard

A. 48

B. 720

C. 0

D. 120

Solution

1. Step 1: Understand function behavior

   Function returns 0 if n is odd. For even n, it multiplies n by factorial of n-2 recursively.

2. Step 2: Calculate evenFactorial(6)

   evenFactorial(6) = 6 * evenFactorial(4) evenFactorial(4) = 4 * evenFactorial(2) evenFactorial(2) = 2 * evenFactorial(0) evenFactorial(0) = 1 (base case) So, 2 * 1 = 2 4 * 2 = 8 6 * 8 = 48

3. Final Answer:

   48 -> Option A

4. Quick Check:

   Product of even numbers down to 0 = 48 [OK]

Hint: Multiply even numbers down by 2 recursively [OK]

Common Mistakes:

• Calculating full factorial instead of even factorial
• Returning 0 for even inputs
• Ignoring base case for 0