Unit 4 - Divide & Conquer
4.1 - Recursion (part 1)

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]

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
}

Definition:  Recursion

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!

If too many calls are placed on the Stack for the memory, this is called a "Stack Overflow".  🤯

## The Base Case

In order to stop the calls to the function and trace back through all of the previous calls (pop each off the stack), 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. So far all this does is resemble a for-loop.

The real power of recursion happens when the return statement(s) actually return a value!

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

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

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

As a loop, this is simple:

function sum_to_n(n) {
for (let i = 1; i <= n; i++)

}

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

Let's code it recursively.

Try coding the recursive sum_to_n(n) or click here to reveal the solution.

Recursive sum_to_n(n):

function sum_to_n(n) {
if (isNaN(n)) return -1;   // ERROR CHECK
if (n == 1) return 1;      // BASE CASE

return n + sum_to_n(n - 1);   // All other cases
}