Comp 110 Designing a Recursive Function

Step 1 - Base Case

What is your absolute base case? What is the simplest case you can imagine?

What argument can the function be called with where an answer can be determined in a single step?

Examples:

  • Function: count...processes a List to count the number of values it contains
    • Base Case: The list is empty! The count function returns 0

Step 2 - Next simplest case

What is the next simplest case of the function that can be expressed in terms of the absolute base case?

This is the recursive case...it's like induction in math.

Lists:

  • The base case is when the list is empty
  • The next simplest case is when the List has one element in it!

Example:

  • Base Case: 
    • count(null) = 0
  • Recursive Case:
    • count("C" -> null) = 1 + count(rest("C" -> null))
Step 3 - Edge Cases

Are there any special base cases to handle?

Can your function conclude a final answer before reaching the absolute base case? if so, add a special base case to handle it

Example:

  • Function: includes...processes a List to see if a specific value is included in the List


    • Special Base Case: the specific value is found! return true (even if not at end of list!)

Examples

Write a function that calculates the factorial (!) of a given number 'n'

STEP 1: BASE CASE

  • When do we want to stop multiplying? n===1!
    • Stop before we hit 0 (0 * x = 0)
    • factorial(1) or (1!) is 1!
      • so...return 1!

let factorial = (n: number): number => {
     if(n === 1){
          return 1;
     }....

STEP 2: RECURSIVE CASE

  • What is the next simplest form (if the base case is n===1)? n===2!
    • factorial(2) = 2*1 = 2
      • ...same as 2 * factorial(1)
      • ...same as n * factorial(n-1)
      • return n * factorial(n-1)
let factorial = (n: number): number => {
     if(n === 1){
          return 1;
     } else {
          return n * factorial(n-1)
     }
};

STEP 3: SPECIAL CASE?

Under any circumstance, do we want to stop multiplying before we get to 1?

  • No! Factorials will always include 1
  • so...no special case!