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:

Binary Search

How Binary Search Works

Binary search searches an array for a value. It requires that the array be sorted and uses the following trick: You can avoid searching half the array by comparing to see if your search target is in the upper or lower half of the array. This reduces the search problem by half, and you can do this recursively until you only have one place left to look. Here’s an implementation:

How many steps does linear search take to search an array of 1,000,000 items?

On average, you need to look at 500,000 items, so the time is however long it takes to perform 500,000 “steps” of accessing the array, comparing to your search key, and moving on.

How many steps does binary search take to search an array of 1,000,000 items?

Step 1: reduce search to 500,000 items.
Step 2: reduce to 249,999.
Step 3: reduce to 124,999.
Step 4: reduce to 62,499.
Step 5: reduce to 31,249.
Step 6: reduce to 15,624.
Step 7: reduce to 7,811.
Step 8: reduce to 3,905.
Step 9: reduce to 1,952.
Step 10: reduce to 976.
Step 11: reduce to 488.
Step 12: reduce to 244.
Step 13: reduce to 122.
Step 14: reduce to 61.
Step 15: reduce to 30.
Step 16: reduce to 15.
Step 17: reduce to 7.
Step 18: reduce to 3.
Step 19: reduce to 1 — We’re done in 19 steps!

Well, in this implementation, we might compare several times for each step, but still, we’re WAY FASTER than even 500,000 tiny steps, right?

Can we go even FASTER?

Think about searching billions of pages on the web. There must be a way …

Prerequisite: Array Implementation

What does an array look like inside your computer?

Computers have memory.

Memory is a giant array in hardware.

Every element of this array is tiny; it’s 8 bits; it’s one byte; it’s only enough to store one character from a string.

But the array is long: billions! A 4GB computer has 4 billion bytes of actual memory organized as an array. You also have 100s of GBs of disk space for files, but that’s organized differently and cannot be accessed directly and quickly like “main” memory, with which you can read or write any byte in about 10ns (that’s 100 million times per second!).

Every byte has a number: 0, 1, 2, …

So what about Javascript arrays? First, the array is going to be located somewhere in this vast expanse of bytes. Let’s call the starting location START.

Array elements have equal size. E.g. if you have a 64-bit computer, probably array elements are 64-bits or 8 bytes each.

So you have an element at location START, another at START + 8, then START + 16, etc.

To find the element at index i, you just compute (START + 8 * i) and go to that location in memory. (That will take about 10ns — pretty fast!)

Thus, arrays are ideal for storage, but only if the “keys” are consecutive integers and the elements all have the same size.

(An aside: if you are wondering how you could possibly store strings in an array, since strings have different sizes, the answer is that you store the location of the string, not the string itself. All locations (on a 64-bit machine) are 64-bit integers, or 8 bytes each.)

Hash Tables and Hashing

What is a HashTable Data Structure – Introduction to Hash Tables, Part 0 – this a simple and clear introduction to hashing. The video is so low-key, it is worth adding that the result is a data structure where you can insert and look up information using a key (such as a person’s name) in constant time, i.e. the cost of inserting and looking up is independent of the number of items in the hash table. Compare this to linear search and binary search.

Hash Functions

How do we turn a key (usually a string) into a number?

First, characters are stored as numbers in the computer. The most common character encoding is ASCII. In ASCII, ‘A’ is 65, ‘B’ is 66, etc. ‘0’ is 48, ‘1’ is 49, etc. ‘a’ is 97, ‘b’ is 98. There are encodings for all the characters on your keyboard (if you have an American/English keyboard), including ! @ # $ % ^ & * ( ) _ + = { } | [ ] \ ? , / ., and there’s even ASCII character 7 which tells your console to make a “beep” sound (the “character” is called BEL).

In Javascript, you can get the character code using var myString = "A"; var code = myString.charCodeAt(0); In this example, code is set to 65.

Second, you can combine character codes numerically to make a hash function. Here’s a very simple one:

What’s good and bad about this particular function?

What makes it a hash function?

Hash Tables in Javascript

Objects are implemented using hash tables!

You can write:
key = "age";
value = 25;
myObject = {}; // create an empty object
myObject[key] = value;
print(myObject["age"]);

This uses hashing to quickly store values and retrieve them using keys, which can be numbers or strings. (In fact, if you use integers for keys, you can expect Javascript to make an array, which is even faster than hash tables because you can use the integer index to compute the value location directly without hashing.)