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
the idea that something will re-occur in smaller amounts
divides a complex problem into smaller sub-problems (i.e. divide and conquer)
sub-problems are smaller instances of the same type of problem.
is self-referential (calls 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!
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) {
let answer = 0;
for (let i = 1; i <= n; i++)
answer += i;
return answer;
}
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.
Are there any restrictions to this function? Any error checking?
Yes, the input must be a number >= 1
What is the base case?
The base case is when n gets down to 1
What should we return at the base case?
We should return 1
What should we return when it's not the base case?
We should return the previous value + 1
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
}