Week 14

Recursion

You might find these notes useful: Recursion lecture slides from 15-110

A recursive function is one that calls itself.

Not necessarily infinitely, because you can make the recursive call based on a condition.

Every recursive function has two parts:

  1. The base case: One or more simple cases that can be solved directly and immediately (non-recursively).
  2. Recursive cases: One or more cases that can be solved by solving simpler versions of the original problem.

Example: Adding two non-negative integers

Adding zero is trivial: Any number plus zero equals the number. That’s our base case:

How can we simplify a + b and make it closer to a + 0? Let’s assume we know how to add 1 or subtract 1. That’s simpler than full addition, right? We’ll use the property that a + b = (a + 1) + (b – 1) to make the recursive case:

Neither one of these is a full solution, but if we put them together we have an adder!

Let’s look at what happens with adder(4, 3):

Recursion with Graphics

simple-rec

function setup() {
    createCanvas(400, 400);
    frameRate(10);
}

function draw() {
    background(240);
    fill(0);
    recPattern(80, 80, 243);
}

function recPattern(x, y, size)
{
    // base case:
    if (size <= 2) {
        rect(x, y, size, size);
    } else { // recursive case:
        // draw smaller pattern in corners and center
        var third = size / 3;
        recPattern(x, y, third); // upper left
        recPattern(x + 2 * third, y, third); // upper right
        recPattern(x + third, y + third, third); // middle
        recPattern(x, y + 2 * third, third); // lower left
        recPattern(x + 2 * third, y + 2 * third, third); // lower right
    }
}

Recursive Music!

Sierpinski Triangle Music

Recursive Search Problem

Recursion is an alternative to iteration. In class, we did 2 “warm-up” exercises: recursive function to print 0 through N, recursive function to print elements of an array, and then implemented linear search with recursion.

Print 0 through N using recursion

The recursive description of this problem is: To print i through N, print i, then print i+1 through N. The base case is print nothing when i > N.

Here’s a solution:

Print elements of an array

Similar to just printing 0 through N, we print a[0] through a[N-1], where N is the length.

Recursive Implementation of Linear Search

Implement linear search recursively, starting with this code:

Here’s a solution: