1 00:00:06,050 --> 00:00:10,220 For our next recursive example, we're going to take a look at what a palindrome is. 2 00:00:11,390 --> 00:00:17,090 You might already be familiar with what a palindrome is, but in case you're not, it is a sequence 3 00:00:17,090 --> 00:00:22,250 that reads the same from left to right and right to left. 4 00:00:22,520 --> 00:00:28,970 So we're going to have a function that's going to return true if it is a palindrome and false if it's 5 00:00:28,970 --> 00:00:29,480 not. 6 00:00:29,570 --> 00:00:31,280 So it's going to be Boolean. 7 00:00:32,420 --> 00:00:39,170 So if we look at this sequence, we have one, two, three, four, which we can easily tell that it's 8 00:00:39,170 --> 00:00:42,290 not the same from left to right as it is from right to left. 9 00:00:42,290 --> 00:00:44,480 So it's not going to be a palindrome. 10 00:00:45,440 --> 00:00:50,150 This sequence, however, we see we have one, two, three, four, three, two, one. 11 00:00:50,150 --> 00:00:55,910 So we see we have one and one, two and two, three and three, and then four is in the middle. 12 00:00:55,910 --> 00:00:57,490 So that's always going to be there. 13 00:00:57,500 --> 00:00:59,660 Therefore, this is a palindrome. 14 00:01:00,860 --> 00:01:04,010 And again, this doesn't always have to be on integers. 15 00:01:04,010 --> 00:01:06,000 We can do it on strings as well. 16 00:01:06,020 --> 00:01:14,210 So we have the word racecar here and we see that we have R and R, A and a, C and C, and then E is 17 00:01:14,210 --> 00:01:16,400 in the middle, which is always going to be there. 18 00:01:16,400 --> 00:01:18,920 So this is also a palindrome. 19 00:01:22,120 --> 00:01:24,400 So for us to implement this. 20 00:01:25,520 --> 00:01:31,490 We'll have a function called palindrome, and we're going to pass in a vector. 21 00:01:31,880 --> 00:01:37,880 We're going to check to see if the vector containing integers is a palindrome or not. 22 00:01:38,150 --> 00:01:44,990 And what we want to do is we want to have the starting index of our vector, which is always going to 23 00:01:44,990 --> 00:01:45,710 be zero. 24 00:01:46,070 --> 00:01:53,900 And then we want to have the ending index, which is going to be length minus one. 25 00:01:54,560 --> 00:02:02,570 Remember, because indexes are always start at zero and then we want to check if the starting index 26 00:02:02,570 --> 00:02:04,760 and the ending index are the same. 27 00:02:04,760 --> 00:02:08,240 And if they are, then we want to reverse inward. 28 00:02:08,240 --> 00:02:13,730 So now we would want to check if A and B are the same. 29 00:02:13,730 --> 00:02:20,330 And then if they are, we know C in the middle is always going to be in the middle because of this being. 30 00:02:21,900 --> 00:02:23,270 The a link the five. 31 00:02:23,280 --> 00:02:25,170 So C will always be in the middle. 32 00:02:25,170 --> 00:02:33,990 So assuming that as the start and end match and then A and B match, then this would also be a palindrome. 33 00:02:35,030 --> 00:02:43,070 So let's take a look at how we can implement this and check to see if we can create some palindromes 34 00:02:43,070 --> 00:02:43,940 ourselves. 35 00:02:49,830 --> 00:02:52,380 So we have our function created. 36 00:02:54,110 --> 00:02:58,670 And we know that we want it to be a vector. 37 00:02:59,180 --> 00:03:05,390 So we'll say we have our array and we'll make it a reference. 38 00:03:05,390 --> 00:03:08,630 That way our function does not absorb 39 00:03:11,360 --> 00:03:19,760 our vector, and then we want to pass in the start and the end, and then we want it to return a boolean. 40 00:03:22,980 --> 00:03:25,290 It helps if I spell you size right. 41 00:03:29,030 --> 00:03:33,110 So in here we have a base case. 42 00:03:33,110 --> 00:03:36,770 We want to see if our start is equal. 43 00:03:38,620 --> 00:03:42,730 Or greater than greater than or equal to our end. 44 00:03:44,980 --> 00:03:55,150 And then if it is return true because and we do this because if our vector is of size one. 45 00:03:56,190 --> 00:04:03,800 Our start would be zero, and then our end would be length minus one, which is also zero. 46 00:04:03,810 --> 00:04:08,490 So we want to make sure that there's more than one element in our array. 47 00:04:09,210 --> 00:04:11,010 Otherwise, we. 48 00:04:11,860 --> 00:04:17,950 Know for a fact that it's a palindrome because there is only one element in there which is always going 49 00:04:17,950 --> 00:04:19,480 to be a palindrome. 50 00:04:21,270 --> 00:04:26,490 So we'll say if the start is equal 51 00:04:28,980 --> 00:04:33,510 to the end, then that is good. 52 00:04:33,990 --> 00:04:38,190 And that means we want to start reversing inward. 53 00:04:38,430 --> 00:04:46,230 So we will keep passing in our array and we will go start plus one to increment our index up one. 54 00:04:47,210 --> 00:04:51,160 And then we will go end minus one to increment D. 55 00:04:52,260 --> 00:04:55,070 Encouragement from the end. 56 00:04:55,100 --> 00:04:57,740 That way we meet somewhere in the middle eventually. 57 00:04:59,180 --> 00:05:07,580 And then if at any point this condition is false, then we want to return false because we found two 58 00:05:07,580 --> 00:05:10,220 elements that do not match when they should match. 59 00:05:10,220 --> 00:05:12,590 Therefore, it is not a palindrome. 60 00:05:14,550 --> 00:05:19,830 So I went ahead and created our test cases here, which we did on. 61 00:05:22,030 --> 00:05:27,370 Her notepad and we expect one, two, three, four to return false. 62 00:05:27,550 --> 00:05:34,240 And then we would expect one, two, three, four, three, two, one to return true. 63 00:05:36,790 --> 00:05:43,060 So if we run this, we see that we have false for the first call, which is correct. 64 00:05:43,210 --> 00:05:46,230 And then we have true for the second call. 65 00:05:46,240 --> 00:05:55,150 So we have a fully functioning palindrome function that is going to look at a sequence of integers inside 66 00:05:55,150 --> 00:05:59,110 of a vector and tell us if it is a palindrome or not.