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

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

### Example: Adding two non-negative integers

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

1 2 3 |
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:

1 2 3 |
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!

1 2 3 4 5 6 7 |
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):

1 2 3 4 5 6 7 8 |
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 |

## 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!

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

1 2 3 4 5 6 7 8 9 10 11 12 |
// print numbers from i through lastNum function counter(i, lastNum) { // base case: nothing left to print if (i > lastNum) { return "done"; } // recursive case: println(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.

1 2 3 4 5 6 7 8 9 10 11 12 |
// print values in an array function printer(i, a) { var len = a.length; // base case if (i >= len) { return; } // recursive case println(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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function setup() { var ar = [3, 5, 6, 8, 3, 65, 4, 7, 5] println(findNum(ar, 65, 0)); // should find 65 at index 5 println(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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// 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; println(findNum(x, ar)); } |

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

1 2 3 4 5 6 7 8 9 10 11 |
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?

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:

1 2 3 4 5 6 7 8 |
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.)