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) {
for (let i = 1; i <= n; i++)

}

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?