Factorial Using Recursion in DSA Python - Build from Scratch

Factorial Using Recursion

📖 Scenario: Imagine you want to find the factorial of a number. Factorial means multiplying the number by all smaller numbers down to 1. For example, 4 factorial is 4 x 3 x 2 x 1 = 24.We will use a simple method called recursion, where a function calls itself to solve smaller parts of the problem.

🎯 Goal: Build a program that calculates the factorial of a given number using recursion and prints the result.

📋 What You'll Learn

Create a variable to hold the number to find factorial of

Create a recursive function named factorial that takes one parameter n

Use a base case in the function to stop recursion when n is 1

Use recursion to calculate factorial for numbers greater than 1

Print the factorial of the number

💡 Why This Matters

🌍 Real World

Factorials are used in math, statistics, and computer science to count arrangements and combinations.

💼 Career

Understanding recursion and factorials helps in algorithm design and problem solving in software development.

1

Create the number variable

Create a variable called number and set it to 5.

DSA Python

# Create a variable called number and set it to 5
# Your code here

Hint

Use number = 5 to create the variable.

2

Define the recursive factorial function

Define a function called factorial that takes one parameter n. Inside the function, write an if statement to return 1 if n == 1.

DSA Python

number = 5
# Define the factorial function with parameter n
# Your code here

Hint

Use def factorial(n): to start the function and check if n == 1: to return 1.

3

Add recursive call to factorial function

Inside the factorial function, after the if statement, add a return statement that returns n * factorial(n - 1).

DSA Python

number = 5

def factorial(n):
    if n == 1:
        return 1
    # Add recursive return statement here
    # Your code here

Hint

Use return n * factorial(n - 1) to call the function recursively.

4

Print the factorial result

Use print(factorial(number)) to display the factorial of number.

DSA Python

number = 5

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

# Print the factorial of number
# Your code here

Hint

Use print(factorial(number)) to show the result.

Practice

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

easy

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

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

C. The number multiplied by 2

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 correctly states this product definition.

3. Final Answer:

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

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 Python?

easy

A. if n == 1: return 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 == 0, which is correct. Others return wrong values.

3. Final Answer:

   if n == 0: return 1 -> Option D

4. Quick Check:

   Base case n=0 returns 1 [OK]

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

Common Mistakes:

• Returning 0 for factorial(0)
• Using wrong base case condition
• Returning n+1 instead of 1

3. What is the output of the following code?

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(4))

medium

A. 10

B. 16

C. 24

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 C

4. Quick Check:

   4! = 24 [OK]

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

Common Mistakes:

• Stopping recursion too early
• Adding instead of multiplying
• Wrong base case causing infinite recursion

4. Find the error in this recursive factorial function:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n+1)

print(factorial(3))

medium

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

B. The print statement should be outside the function

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

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

Solution

1. Step 1: Analyze recursive call parameter

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

2. Step 2: Correct recursive call to decrement n

   It should call factorial(n-1) to move towards base case and stop recursion.

3. Final Answer:

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

4. Quick Check:

   Recursion must approach base case by decreasing n [OK]

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

Common Mistakes:

• Increasing n in recursive call causing infinite loop
• Wrong base case value
• Adding instead of multiplying in return

5. How can you modify the recursive factorial function to handle negative inputs gracefully?

hard

A. Change base case to n == -1

B. Add a check to return None or error if n < 0 before recursion

C. Use absolute value of n in recursive call

D. Ignore negative inputs and proceed as usual

Solution

1. Step 1: Understand factorial domain

   Factorial is not defined for negative numbers, so function should handle this case explicitly.

2. Step 2: Add input validation before recursion

   Check if n < 0 and return None or raise error to avoid invalid recursion.

3. Final Answer:

   Add a check to return None or error if n < 0 before recursion -> Option B

4. Quick Check:

   Validate input before recursion [OK]

Hint: Check for negative input before recursion [OK]

Common Mistakes:

• Using absolute value hides invalid input
• Changing base case to negative number
• Ignoring invalid inputs causes wrong results