# 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

``````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 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: