Week 14

Recursion

You might find these notes and video useful: Recursion lecture at freecodecamp.org

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.

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[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

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?

Faster Search and Hashing

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.

What’s a Byte?

A byte is a basic unit of measurement of information storage or transmission that consists of 8 bits. It can be used to represent letters and numbers – up to 256 of each. For example, a Byte containing the 8 bits 01000101 represents

the letter E in the ASCII character set, or
the number 69, since (counting from the right, starting at 0) 01000101 has bits at positions 0, 2, and 6. These bits represent 20 + 22 + 26 = 1 + 4 + 64 = 69.

There are many things the same pattern of bits could represent – as long as we all agree on the representation or rules for understanding it – like part of one pixel in an image. There are usually three parts to a pixel, one byte for red, another for green and the third for blue. All together that is 24 bits, so we can represent a total of 224 or 16 million (approximately) colors. Often, there is a 4th byte for transparency.

More on Memory

But the memory array of bytes 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 an address which is its location, and like arrays in programs, memory addresses are integers: 0, 1, 2, …

Arrays in Javascript

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 access that location in memory. (This computation is typically built-in to the computer hardware, so there’s an actual electronic circuit among the millions of transistors in your CPU that do the add and multiply needed to produce a memory address, and the address is transferred over actual copper wires — really tiny ones — to memory chips that retrieve the stored bits and return them to the CPU. That will all 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, the ASCII code for “A”.

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

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.)