[MUSIC] >> Welcome. This week we're going to talk about recursion. Recursion is an important concept in computer science that helps us to solve complicated problems with similar internal structures. And rather than explain recursion, I first want to start out with a little demo and we've got our court jester here. So I'm going to make him take this and can you take that apart for me? [LAUGH]. >> Oh, oh, oh. Okay, okay. >> Is it apart yet? >> No. I got that, I got that, okay. Let's see. [SOUND] Okay. [SOUND] I'm doing, doing very good here. >> All right, you, you might get it. >> [LAUGH] >> You might get it. >> Lets see. How many of these are there? >> Did you get to the end? >> I did. >> [LAUGH] Okay. Good job Joe. [LAUGH] All right, this is, this is a demonstration of recursion, all right? And the point here is that he only had to follow one procedure, but he did it over and over again. And we knew that he was eventually, well, I knew he was eventually going to get to the end, he might not have. >> I was scared for a while there. >> And the key there is that the problems got smaller, each problem was exactly the same as the previous because the structure of the nesting dolls is exactly the same, but each doll is a little bit smaller than the previous one. So eventually, we're going to get to a doll that's too small to have a doll inside it and we're done. And that's the fundamental idea behind recursion. want to explain, in more detail, Joe, why we care? >> So I teach recursion in the class I do on campus here. And it often frightens students. And kind of the way I think about it is, kind of recursion marks, kind of the transition from being a programmer, to computer science. Recursion requires a little bit of math, math-, mathematical sophistication to understand, but once you've mastered it, you'll find that it opens up a wide range of ways to solve important problems such as you'll come up on when you're working on computer science. >> So, Loui. I know you like recursion, yes? >> Nice hat, Loui. >> I'm surprised you recognized me with hair. >> [LAUGH] You look better with the hat on. >> Yeah, I know. >> So, what are you doing over there? >> I'm trying to learn about arrays in Java, how to do arrays in Java. I know how to do it in pseudocode, Scott, but I don't know how to do it in Java. >> Important topic. Important topic. >> Yeah. So it seems to be on page 144, I'm going to go there. And, I'm going to read the about arrays for you. >> [LAUGH] There must be a better way to do that. You want to help him out, Joe? >> Okay, alright, stop, stop, stop, okay. Alright, let's just do this. Go, go to halfway in the book. >> Is this halfway? >> Okay, what page number is that? >> 226. >> Okay, so it's lower. So, why don't you do what I just did and do that again, except, just do it with the lower half of the book. >> Oh, okay. So I get your point, so now it's lower than 226 I go left, it's actually 144 [LAUGH]. >> You're a very lucky guy [LAUGH]. >> Okay, so the point is that we go to the middle of the book, roughly middle of the book, if the page I'm looking for is smaller than the current page number, I go left, if it's bigger than the current page number I go right, and I repeat this process until I get to that page number. >> So, so what does that have to do with recursion, or is this just a diversion here? >> This is nothing but recursion actually, because I'm repeating the same process over and over, which is I compare the current page I'm at to the page I'm looking for. And if the page I'm looking for is smaller, then I go left and repeat the process. If, if the page I'm looking for is bigger, I go right and repeat the process. And this is known as binary search, by the way. >> Okay. So recursion is a difficult concept, especially when you see it for the first time. All right. But once you start to get comfortable with recursion, I think Joe's correct, you truly start to become a computer scientist. This is how we think about complex problems. It's a powerful technique that will allow us to solve a wide array of problems that have this similar structure where you can repeat the process again and again, make the problem smaller and smaller and smaller and finally get to a solution.
