Week 14 – [OLD FALL 2018] 15-104 • Introduction to Computing for Creative Practice

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:

The base case: One or more simple cases that can be solved directly and immediately (non-recursively).
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:

function adder(a, b) {
    if (b == 0) return a;
}

function adder(a, b) {

if (b == 0) return a;

}

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:

function adder(a, b) {
    if (b > 0) return adder(a + 1, b - 1);
}

function adder(a, b) {

if (b > 0) return adder(a + 1, b - 1);

}

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

function adder(a, b) {
    if (b == 0) {
        return a;  // base case
    } else {       // recursive case (b > 0)
        return adder(a + 1, b - 1);
    }
}

function adder(a, b) {

if (b == 0) {

return a; // base case

} else { // recursive case (b > 0)

return adder(a + 1, b - 1);

}

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

adder(4, 3) calls ...
    adder(5, 2) which calls ...
        adder(6, 1) which calls ...
            adder(7, 0) which returns ...
            7
        so adder(6, 1) returns 7
    so adder(5, 2) returns 7
so adder(4, 3) returns 7

adder(4, 3) calls ...

adder(5, 2) which calls ...

adder(6, 1) which calls ...

adder(7, 0) which returns ...

so adder(6, 1) returns 7

so adder(5, 2) returns 7

so adder(4, 3) returns 7

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 numbers from i through lastNum
function counter(i, lastNum) {
    // base case: nothing left to print
    if (i > lastNum) {
        return "done";
    }
    // recursive case:
    print(i);
    return counter(i + 1, lastNum);
}

// to print 0 through 10, call counter(0, 10)

// print numbers from i through lastNum

function counter(i, lastNum) {

// base case: nothing left to print

if (i > lastNum) {

return "done";

}

// recursive case:

print(i);

return counter(i + 1, lastNum);

}

// to print 0 through 10, call counter(0, 10)

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.

// print values in an array
function printer(i, a) {
    var len = a.length;
    // base case
    if (i >= len) {
        return;
    }
    // recursive case
    print(a[i]);
    printer(i + 1, a);
}
// to call print the elements in ar, call printer(0, ar)

// print values in an array

function printer(i, a) {

var len = a.length;

// base case

if (i >= len) {

return;

}

// recursive case

print(a[i]);

printer(i + 1, a);

}

// to call print the elements in ar, call printer(0, ar)

Recursive Implementation of Linear Search

Implement linear search recursively, starting with this code:

function setup() {
    var ar = [3, 5, 6, 8, 3, 65, 4, 7, 5]

    print(findNum(ar, 65, 0));  // should find 65 at index 5
    print(findNum(ar, 100, 0)); // should not find 100, prints -1
}


// find x in a, starting at location i
// if found, return the location
// if not found, return -1
function findNum(a, x, i) {
    // add code here
}

function setup() {

var ar = [3, 5, 6, 8, 3, 65, 4, 7, 5]

print(findNum(ar, 65, 0)); // should find 65 at index 5

print(findNum(ar, 100, 0)); // should not find 100, prints -1

}

// find x in a, starting at location i

// if found, return the location

// if not found, return -1

function findNum(a, x, i) {

// add code here

}

Here’s a solution:

// return index of x in a
//    if a[i] == x, then return i
//    otherwise return -1
function findNumHelper(i, x, a) {
    // base case: 
    //    if nothing left, we're done: -1
    if (i > a.length) {
        return -1;
    } else if (a[i] == x) {
        return i;
    } else {    // recursive case:
        return findNumHelper(i + 1, x, a);
    }
}

// findNumHelper(0, x, a) does the job, but we can make
// things slightly prettier by eliminating the need to 
// pass in zero; for that we just define another function
// to call findNumHelper():
function findNum(x, a) {
    return findNumHelper(0, x, a);
}

// here's a test
function setup() {
    var ar = [3, 5, 6, 8, 3, 65, 4, 7, 5];
    var x = 65;
    print(findNum(x, ar));
}

// return index of x in a

// if a[i] == x, then return i

// otherwise return -1

function findNumHelper(i, x, a) {

// base case:

// if nothing left, we're done: -1

if (i > a.length) {

return -1;

} else if (a[i] == x) {

return i;

} else { // recursive case:

return findNumHelper(i + 1, x, a);

}

// findNumHelper(0, x, a) does the job, but we can make

// things slightly prettier by eliminating the need to

// pass in zero; for that we just define another function

// to call findNumHelper():

function findNum(x, a) {

return findNumHelper(0, x, a);

}

// here's a test

function setup() {

var ar = [3, 5, 6, 8, 3, 65, 4, 7, 5];

var x = 65;

print(findNum(x, ar));

}

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:

function bsearch(a, key, lo, hi) {
    if (lo > hi) return -1; // not found
    var mid = int((lo + hi) / 2);
    if (a[mid] == key) {
        return mid; // found
    } else if (a[mid] > key) { // search lower half
        return bsearch(a, key, lo, mid - 1);
    } else if (a[mid] < key) { // search upper half
        return bsearch(a, key, mid + 1, hi);
    }
}

function bsearch(a, key, lo, hi) {

if (lo > hi) return -1; // not found

var mid = int((lo + hi) / 2);

if (a[mid] == key) {

return mid; // found

} else if (a[mid] > key) { // search lower half

return bsearch(a, key, lo, mid - 1);

} else if (a[mid] < key) { // search upper half

return bsearch(a, key, mid + 1, hi);

}

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?

(From http://cs.sru.edu/~mullins/cpsc100book/module02_introduction/module02-05_introduction.html)

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 2⁰ + 2² + 2⁶ = 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:

var TABLESIZE = 1000;
function hashcode(str) { // string -> hash
    var hash = 0;
    for (var i = 0; i < str.length; i++) {
        hash += str.charCodeAt(i);
    }
    return hash % TABLESIZE;
}

var TABLESIZE = 1000;

function hashcode(str) { // string -> hash

var hash = 0;

for (var i = 0; i < str.length; i++) {

hash += str.charCodeAt(i);

}

return hash % TABLESIZE;

}

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