Unit 3 - Divide & Conquer
3.1 - Recursion (part 1)

Definition: Recursion

  • the idea that something will re-occur in smaller amounts

    • divides a complex problem into smaller sub-problems (i.e. divide and conquer)

    • subproblems are smaller instances of the same type of problem.

  • is somehow self-referential (calls itself)

Q. How would you compute the answer to 4+3*2-6/2 ?
That is equal to 4 + (3*2-6/2)
Which is equal to 4 + (3*2) - (6/2) <-- Breaking it down to saller problems.

One of the most common techniques used in computer science is known as Divide and Conquer. A technique used to solve complex problems by "dividing" them into smaller problems and "conquering" the smaller parts.

Let's look at two more math concepts - exponents and multiplication.

Exponents are repeated multiplication (eg. 2^5)
 2 * 2 * 2 * 2 * 2

And multiplication is repeated addition (eg. 4*6)
either 4 + 4 + 4 + 4 + 4 + 4 or 6 + 6 + 6 + 6

Can we combine those concepts and use repeated addition (divide and conquer) to solve 4^3?

Mathematical divide and conquer:

4^3 = 4*[4*4]
= 4 * [4 + 4 + 4 + 4]
= [4 + 4 + 4 + 4] + [4 + 4 + 4 + 4] + [4 + 4 + 4 + 4] + [4 + 4 + 4 + 4]

Recursion in Programming

We might immediately think "I should use loops for this". But loops aren't the only way to repeat things.

A function can call itself, creating a recursive loop:

function recurse() {
console.log("I'm doing something!");
recurse(); // call itself
}

But when does it end?

Each call to the function places another instance into memory (called the "Call Stack"). Eventually we will run out of memory!


The Base Case

In order to stop the calls to the function and trace back through all of the previous calls, we need to create a trap called the base case.

function recurseFixed(n) {
console.log("I'm doing something!");

 // Base Case
if (n <= 0) return;

// All other cases
 recurseFixed(n - 1);
}

In the example above, we can make the first call to our function with a number (eg. recurseFixed(10) ) and it will stop when we get down to zero.

The real power of recursion happens when the return statement(s) in the base case or other areas actually return a value!

Important note - pseudocode is really important when creating a recursive function!

Let's start by looking at a simpler example of recursion - summing from 1 to n.

For example sumToN(4) = 4 + 3 + 2 + 1 = 10

As a loop, this is simple:

function sumToN(n) {
let answer = 0;
for (let i = 1; i <= n; i++)
answer += i;

return answer;
}


This can be recursively because:
sumToN(4) == sumToN(3) + 4 == sumToN(2) + 3 + 4 == sumToN(1) + 2 + 3 + 4 == 1 + 2 + 3 + 4

Let's code it recursively.

  • Are there any restrictions to this function? Any error checking?

  • What is the base case?

    • What should we return at the base case?

  • What should we return when it's not the base case?