Unit 4 - Divide & Conquer
4.2 - Recursion (part 2)
Reminder: Recursion
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 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().
Take a string and (for now) assume it is made of only the digits 0-9. For example "4293"
- 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? 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:
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 (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?