Unit 4 - Divide & Conquer
4.2 - Recursion (part 2)

Reminder:  Recursion

Factorials are a perfect example for recursion.

Last class you were asked to devise a recursive algorithm that will return the factorial of a number: 
function factorial(n) {...}
How successful were you? If you struggled, have a classmate (or your teacher) explain the solution. Recursion can be difficult to understand.

A new Challenge - Converting Strings to Integers

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

🤔 Can we recursively convert a String to a number? Generate some pseudocode to do it (feel free to work with a partner).

Another 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:

Notice the following very important facts about recursion:

Eventually, the problem (the 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

Could you generate pseudocode for the is_palindrome() function?