Unit 2 - Divide & Conquer
2.1 - Recursion (part 1)

Q. How would you compute the answer to 4+3*2-6/2 ? This is equal to 4 + (3*2-6/2)

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

Multiplication is repeated addition (eg. 4*6)
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 solution

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

Solution in code

function additivePower(base, exp) {
if (exp == 0) return 1;
let result = 0;
let additions = base**(exp - 1); // Cheating
for (let x = 0; x < additions; x++)
result += base;

return result;
}

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)

Let's take a look at an example of recursion - summing up to n.

Given n, sum from 1 to n. For example sum(4) = 4 + 3 + 2 + 1 = 10

As a loop, this is simple:

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

return answer;
}

This can be recursive because sum(4) == sum(3) + 4 == sum(2) + 3 + 4, etc...
Let's do it recursively by calling itself with a length of one less:

function sum(n) {
if (n > 0) return n + sum(n-1);
return 0;
}


* Note this can be (optionally) simplified using a ternary expression:

function sum(n) {
return (n > 0) ? n + sum(n-1) : 0;
}

Another Example: Palindromes

We'll look at the simple case of a palindrome - a String which reads the same forwards as backwards (i.e. "level", "noon", "mom"). How can we write a method that takes a String and recursively determines whether the string is a palindrome? To do this recursively, we must express a palindrome problem in terms of smaller palindrome problems.

Here is the recursive formulation of the problem:

  • A String is a palindrome if its first and last characters are identical AND the substring in between those characters is also a palindrome.
    radar --> ada --> d

This does some kind of "checking" (i.e. compare first and last characters) and then formulates the remainder of the problem as solving the same problem but on a smaller String. Notice the following very important facts about recursion:

  • The sub-problem(s) MUST be an instance of the same kind of problem.

  • The sub-problem(s) MUST be smaller than the original problem size.

Eventually, the problem (String) will become so small that there we can no longer formulate a smaller version (there is no substring). This level is known as the Base Case. In the palindrome problem, an empty string or a single character is trivially a palindrome and hence will be considered the base case for that problem. The base case is used to "stop" the recursive process.

Here are some palindrome examples that show when the base case is reached.

1 - isPalindrome("level") --> isPalindrome("eve") --> isPalindrome("v") --> true
2 - isPalindrome("poop") --> isPalindrome("oo") --> isPalindrome("") -->
true
3 - isPalindrome("abcdba") --> isPalindrome("bcdb") --> isPalindrome("cd") -->
false
4
- isPalindrome("doomed") --> isPalindrome("oome") --> false

The base case is when the substring is of length 0 or 1. Keep in mind, if ever the first and last characters do not match, return false.

Of course this can be coded with loop(s), but where's the fun in that?

Group Task, as a class:

  • Let's create two functions:

    • isPalindromeLoop(str) that determines if the given input is a palindrome, using loop(s).

    • isPalindromeRec(str) that determines if the given input is a palindrome, using recursion. This means that the function calls itself with the substring as the new input to the function.