Recursion Solution

[00:00:00]
>> Kyle Simpson: Okay, let's talk about the solution to the recursion exercise. If it helps, you might have wanted to try it iteratively first just to wrap your head around it, but the hint in the read me really was designed to help you skip right to thinking about the isPalindrome.

[00:00:18]
As we said in the lecture just a little while ago, there are various different strategies for solving things recursively, and one of those strategies, a very common strategy, is solve the sub-problem. Reduce the problem set by one or more, and solve the sub-problem, so that's what's hinted at here, is that the question of if an arbitrarily long string is a palindrome can be formulated recursively as.

[00:00:45]
It is a palindrome if both of these things are true, number one, the first in the last letter of any given string have to be equal, and everything in between has to be a palindrome. So if you think about this string the abcdcba, the a and the a are equal, and if we look only at bcdcb, that is also a palindrome.

[00:01:16]
So a recursive definition for a palindrome is that the first and the last letter are equal, and everything in between is also a palindrome. And of course you answer that by doing the exact same thing, comparing the b and the b and everything in between is a palindrome.

[00:01:30]
So that hints out at how we would approach the recursive solution. Let's take in a string for our isPalindrome, and let's consider our base condition, how do we know what our base conditions are? Well, I hinted at those here, I said, both an empty string and the single character string are in fact palindromes, just by definition they're palindromes.

[00:01:50]
So, if str.length is less than or equal to 1, then we know we have a palindrome, that's a base condition. Now, if we are in a length that is 2 or greater, then we know we need to do some comparison of characters. So the way to look at those characters, we'll set up the first variable, we'll look at strings of 0, and the last variable will look at str[str.length-1].

[00:02:30]
So we'll access the first and the last character. And we need to check to make sure that those are equal. So if those two are equal, if (first === last), then we know we have more work to do. But if first doesn't equal last, then we definitely don't have a palindrome, so we can return false.

[00:02:53]
>> Kyle Simpson: If the first does equal last, then we want to solve the sub-problem which is, the stuff in between is that a palindrome, even if there's nothing in between, we still have that question of, is it a palindrome. So we can simply call isPalindrome with a substring, (str.substring), and that takes in two indices.

[00:03:17]
We want the substring from position one to the position non-inclusive of (str.length-1). Checking the documentation on substring in all languages that there's a substring, it always goes non-inclusive to the final index, so that's why we say -1 instead of -2 there. So this is gonna get that smaller substring, which in the case in the read me would have been the bcdb, it's gonna get that substring and it's gonna ask, is that a palindrome?

[00:03:50]
And then so on and so on.
>> Student: Why is that not the 1, after the substring the 1, why is that not a 0? Wouldn't you want.
>> Kyle Simpson: We want, because it's inclusive on the left hand side and non-inclusive on the right hand side. We wanna start at position 1, not at position 0, we've already looked at position 0.

[00:04:10]
>> Student: Okay.
>> Kyle Simpson: Remember, we've trimmed off two characters here. We've trimmed off this character and this character, and we wanna look at everything in between.
>> Student: But it still knows that spot is 1, even though you've changed it.
>> Kyle Simpson: We didn't change the string yet.
>> Student: Okay.
>> Kyle Simpson: We just looked at it, we said string sub 0.

[00:04:25]
>> Student: Okay.
>> Kyle Simpson: And then substring is actually getting a subset of those characters, still not modifying the string, remember a string is immutable, it's not gonna change. So we'll just do a quick check to make sure I didn't make a mistake here. We'll run this code and we should see all of our test cases pass.

[00:04:44]
And we see them pass. And so, we pass the job interview, and hopefully got the job.