Comp 110 Basic Rules of Recursion

Thinking About Recursion

When we use recursion, we are calling a function within the body of that same function. When we want to write a recursive function, we need a base case and a recursive case. Our recursive case is where we call our function. In the base case, we do NOT call our function.

When thinking through how to write recursive functions, start small! First think about the simplest possible implementation of the function then work your way up to more complicated cases until you've covered everything.

When we enter the recursive case of a function, we know we're going to be calling the function again. In order to prevent this from happening without end, we need a way to make it so that eventually we'll enter the base case of our function. To do this, we must change the arguments we provide when we call the function in our recursive case.

Rules for Recursive Functions

  1. Test for a base case!
    • Not including the base case could give us infinite recursion, which would send a stack overflow error our way!
    • A good base case to start with when recurring with Lists is to check if the List is empty.
      • if (list === null) { // ...
    • When recurring with number parameters, it's often good to check whether the number is equal to zero.
      • if (num === 0) { // ...
  2. Change at least one argument when recurring
    • If we never change the arguments we call the function with, we'll end up in an endless cycle of calling the function, and it'll give us an error.
    • We've got to change the arguments so they get closer to the base case each time, so that eventually they'll hit that base case and we'll stop recurring.
    • When we use recursion with Lists, a good way to change the arguments is to recur on the rest of the List.
      • rest(list)
    • When recurring with number parameters, subtracting one from the number can make it smaller until it will eventually reach a base case of zero.
  3. To build a List, process the first value, and then cons it onto the result of repeating the same process recursively on the rest of the List.
  4. Never make a recursive function call with the same arguments more than once per invocation of a function. If you need to use a recursive result multiple times, store the result in a variable first.

Examples of Recursion

Count Algorithm

The count algorithm counts the number of elements in a list. If it's an empty List, the count is 0, but if not, the count is one more than the count of the rest of the items in the List.

import { List, rest } from "introcs/list";

let count = (list: List<string>): number => {
   if (list === null) {
      return 0; // this is the base case!
   } else {
      return 1 + count(rest(list)); // this is the recursive case!
   }
};

Includes Algorithm

The includes algorithm will check if a certain value is in a given List. If it's an empty List, the value is not part of it, so we'll get false. If it's not empty, we'll check if the first element equals our value. If it does, we'll get true! If not, we'll repeat this process with the rest of the List.

import { List, first, rest } from "introcs/list";

let includes = (list: List<string>, search: string): boolean => {
   if (list === null) {
      return false; // base case
   } else {
      if (first(list) === search) {
         return true;
      } else {
         return includes(rest(list), search); // recursive call using the rest of the list!
      }
   }
};