Recursion and Factorials

Overview

This lecture introduces recursion in computer science, using the example of the factorial function to explain how recursive definitions and solutions work.

Introduction to Recursion

• Recursion is a problem-solving method where a function calls itself.
• Recursive functions break a problem down into smaller instances of the same problem.

Understanding Factorials

• The factorial of a positive integer n (written n!) is the product of all integers from n down to 1.
• Example: 4! = 4 × 3 × 2 × 1 = 24.
• 2! = 2 × 1 = 2; 1! = 1.
• By definition, 0! = 1.

Recursive Definition of Factorial

• Observing the equation: n! = n × (n−1) × (n−2) × ... × 1.
• The part after the initial n is equivalent to (n−1)!.
• Therefore, n! can be rewritten as n × (n−1)!.
• This recursive equation works for n ≥ 1, but fails for n = 0 without an additional case.
• The complete recursive definition:
  • n! = n × (n−1)! if n ≥ 1
  • n! = 1 if n = 0

Writing a Recursive Factorial Function

• When implementing, check if n is 0; if so, return 1 (base case).
• Otherwise, return n × factorial(n−1) (recursive case).
• The base case prevents infinite recursion and handles the special case n = 0.

Example: Calculating 3 Factorial Using Recursion

• 3! = 3 × 2!
• 2! = 2 × 1!
• 1! = 1 × 0!
• 0! = 1 (base case)
• Substituting back up gives 3! = 3 × 2 × 1 × 1 = 6

Key Terms & Definitions

• Recursion — A method where a function solves a problem by calling itself with a smaller input.
• Base Case — The simplest instance of a problem, which ends the recursion.
• Factorial (n!) — The product of all positive integers up to n; 0! is defined as 1.

Action Items / Next Steps

• Practice writing a recursive factorial function in your preferred programming language.
• Review the concept of base cases and their importance in recursion.