Unit 3 - Divide & Conquer
3.2 - Recursion (part 2)

Reminder: 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)

Factorials

In mathematics, a factorial is defined as: n! = n x (n-1) x (n-2) x (n-3) x ... x 3 x 2 x 1
For example, 5! = 5 x 4 x 3 x 2 x 1 = 120

  • What is the base case?

  • Important notes:

    • n is always a non-negative integer.

    • By definition, 0! = 1

  • What is 1! ?

Head over to Replit. Take a moment and devise a recursive algorithm that will return the factorial of a number:
function factorial(n) {...}
If you need some assistance with that, take a look at the notes for 3.1 - Recursion (part 1)

Converting Strings to Integers

The parseInt() and Number() functions perform a very important function. We couldn't do a lot without them. But how do they work? Let's focus on parseInt().

    • Take a string and (for now) assume it is made of only the digits 0-9. For example "4293"
      Hints:
      -       The length of that string (currently 4) can be a very helpful piece of information.
       - The integer ascii character values for characters '0' to '9' are 48 to 57.
      -       JavaScript has a charCodeAt() function that gives you the integer code value of a character.

    • Can we recursively convert a String to a number? Let's generate some pseudocode to do it.

Problem: Palindromes

Let's look at a palindrome - a String which reads the same forwards & backwards (i.e. "level", "noon", "mom"). How can we write a function that takes a String and recursively determines whether the string is a palindrome? To do this recursively, we must express the 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
    noon --> oo --> " " (empty 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 we can no longer formulate a smaller version (there is no substring). This is 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.

Here are some palindrome examples.

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