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

**r**ada**r**-->**a**d**a**-->**d****n**oo**n****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**