**Unit 3 - Divide & Conquer3.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 ****m****ultiplication**** 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**

**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**

**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?