YT YouTube2Text

YouTube2Text → Transcripts → Recursion in Programming - Full Course

Recursion in Programming - Full Course — Transcript

by freeCodeCamp.org · 19,459 words · 1,099 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00When learning about recursion, it can seem like you're always going back to the beginning.
0:04In this course, the simple engineer will help you understand recursion using animations,
0:09thought processes, and more. Hey, guys, and welcome to another video brought to you by
0:14the simple engineer. In today's video, we are going to delve deep into the depths of recursion,
0:19and strengthen your algorithmic mental model around this programming paradigm will do so by
0:26looking at a variety of different examples and animations. So let's get right into it.
0:41The first question that we have to answer about recursion is what even is recursion? And I think
0:47the best way to talk about it is through this analogy, and let's imagine that you're sitting in
0:52line waiting to withdraw money out of an ATM. And for the sake of this example, let's assume that
0:58this right here is you and you have this question this underlying question. And you want to know
1:03how many people are standing in front of you in this line. And this kind of brute force, iterative
1:10version of you says, Well, what I can do is I could step out of line, I could run to the front,
1:15and I can maybe, maybe count one by one. And maybe I store these counts in some auxilary, you know,
1:22notebook that I have some external variable that you can imagine, and then you run down this line,
1:28and you get back and you say, Okay, I got my answer. But I did a lot of work. And we want
1:32to kind of switch this paradigm, we want to think, how can I be lazy? What's the least amount of work
1:38that I can do, and sort of break this problem down in some sort of sub structure? And so what I do
1:43well, I tap on this girl's shoulder in front of me, and I asked her a very simple question, I say,
1:48hey, what number are you? And she turns around and looks at me and says, you know, I'm sorry,
1:51I don't really know. But what I'll do is I'll ask the woman in front of me. And what happens is,
1:57this process kind of continues, and it continues up until we hit some stopping condition. And this
2:04condition that we get stopped at is when we hit this woman, and she taps on this guy's shoulder.
2:08And he says, she says, hey, what number are you in line? And he gives this response. And he's number
2:15one. And this is interesting, right? Because this is kind of the stopping condition to this sort of
2:20problem that we were solving. And what she does, if she takes that number, and she says, Well,
2:26if he was number one, then I'm basically one plus one, because I count myself.
2:33And this guy says, Well, if she was number two, that I'm one plus whatever she was,
2:38and this idea unravels backwards to the original asker. And this woman basically says to the guy,
2:46hey, there were, you know, 10 people in front of me, I count myself.
2:50And now I'm at 11. And it turns out, that we can model this problem with this simple blueprint,
3:00we ask the first question, what's the least amount of work that I can do? How do I break
3:05this problem down into some sub problem? And the second question that I have is,
3:09when would the process complete? Like, what's my stopping condition. And in this case,
3:13it's when we hit the first person in line, which is the gentleman withdrawing money from the ATM,
3:21it just so happens that we can actually write this problem in a very simplified, minimal,
3:27beautiful piece of code. And the function that we have is just this get my position in line. And
3:33we have this kind of abstraction of a person that we have. And notice the return values in
3:38integer. And, again, if we think back to those two questions that we have for this blueprint,
3:45we say if the next person in line is null, then we must be the first person in line.
3:50Right? That's kind of this base case, imagine nobody is in line, well, then you're probably
3:54the first person in line. Now, if we don't satisfy this conditional, then what do we do, we do just
4:01a little bit of work, we say, I'm going to count myself as somebody that contributes to the number
4:06of people in line. And I'm going to add this kind of recursive call, and I'm calling myself.
4:12And this is the interesting property of recursion, we're calling our self.
4:16But the parameter that we condition on actually further progresses us to the problem that we're
4:22trying to solve. And so I'm not I'm not passing the same person object into the function again,
4:28I'm actually passing a person that progresses me a little bit closer to the question that I'm asking,
4:34which is, how many people are in front of me. And this is really all recursion is about is how can
4:39I take some large problem and break it down into a bunch of subproblems such that each invocation
4:45of my method gets me a little bit closer to the problem that I'm trying to solve? Let's think
4:50about another example. Let's take back to the the school days where you're writing a bunch of essays
4:55and typically this process, at least for me, is you know, you writing So you submitted to your
5:00professor and he says, Hey, you know, that essay was terrible, I want you to go make revisions.
5:06And the essay gets passed back to the student. And this process can actually continue over and
5:10over and over again, you write an essay, you make revisions, you submit it, it gets denied,
5:14and you rinse and repeat. And you do this until the professor says, Okay, that was good,
5:19I'm going to put it into my briefcase, and start grading it. And it just so happens, this, again,
5:26is this kind of recursive strategy that can be developed. If we look at a simple piece of code.
5:33And what are we doing, we're really, we look at an essay, we revise the essay, we read it,
5:38we get feedback on it, we apply changes to it. And then notice, we just call ourselves again,
5:44right. And there's a single base case kind of hidden in here. And we do it
5:49until the essay is complete. And notice that each invocation is the same essay
5:54object. But what we've done is we've inched our way a little bit closer to that goal,
5:59that goal of no longer needing revisions on the essay. So the whole process again,
6:05just to re emphasize is that we do a little bit of work on each invocation of our method call Intel,
6:13we hit some base case, some stopping condition that says, hey, you no longer need to continue.
6:22So again, like what is recursion, recursion is nothing more than a method that calls itself
6:29and to be more precise, it's usually a method that maybe returns a value, maybe it doesn't.
6:36But it's conditioned on some parameter, such that when you hit some conditional at some point in
6:42time, you can actually stop recursing, some base case, right. And we consider this piece the base
6:48case, this is the stopping condition, such that we no longer grow the number of recursive calls
6:54that we're storing in memory. And this piece down here, this is the recursive call. This is where I,
7:00you know, I do some unit of work, some small sub problem that inches me or progresses me closer
7:07to the goal or question I'm trying to answer. Before we dive into the technical
7:13intricacies of recursion, it's important that we discuss some of the trade offs.
7:18Why would we want to use recursion? And why would we want to avoid recursion.
7:23And I think there are valid examples for both. And it really comes down to the situation.
7:29The first pro that I'll give is that it really bridges the gap between elegance and complexity,
7:35we will look at a variety of different problems where we're traversing
7:38complex data structures like trees and graphs. And it really boils down to three or four lines of
7:44code. And that is vastly different than doing something like that, in this kind of imperative
7:50approach, where we're, we're looking at things with a lot of loops and a lot of variables. And
7:54that can get really messy really quickly, with data structures that are inherently recursive.
8:01Now, on the downside, you know, adding a bunch of
8:05method calls on the call stack incurs some CPU overhead, right, there is some slowness,
8:10with calling methods in your code compared to iterating through a loop. And that, again,
8:17is another trade off you need to make it can be a time or space trade off that you need to consider.
8:25Now, I touched on this briefly, but again, like recursion can reduce the need for complex loops,
8:32and auxiliary data structures. recursion has this sort of implicit stack, which is a data
8:38structure commonly used in a lot of algorithms. And so having that sort of implicit stack and
8:44kind of self manage looping construct, it's given to you as a part of recursive calls,
8:50you can exploit that property to really simplify your code and focus on the problem you're solving.
8:58Now, the con for that is as you're growing the amount of method invocations
9:03in your computer memory, you can actually run out of memory. And we'll look at a lot of examples as
9:08to why this is, and we'll, we'll start to explore this, this idea of a Stack Overflow exception. And
9:14this is where we start to run out of the pre allocated buffer of memory
9:18that we have for our program, which can actually cause your program to crash.
9:26There are a lot of pros when it comes to recursion when talking about optimization, reducing time
9:32complexity. And that's what this idea of memos zation, and we'll look at some examples of
9:38memorization and caching, to help speed up redundant calls. And that's a beautiful property
9:44of recursion. Now, the con again, just like any piece of code, is that if recursion is overused,
9:53you can get into this sort of habit where you start to develop really complex code,
9:58if it's not well instructed, and you want to make sure that
10:02and what we'll get a lot better at this as we go through this This tutorial
10:06is when you look at problems, you want to kind of ask yourself, Is this a good use case?
10:11For recursion? Can I really break it down into subproblems that make sense for recursion?
10:16If you cannot, then you may get into this con where you have unnecessarily complex code.
10:24Now, the final thing, as I had mentioned before, is recursion
10:27works really well for recursively defined data structures, JSON objects, trees, graphs,
10:35things that allow you to basically focus on one tiny unit of the data structure at a time.
10:41And it just so happens we'll look at a bunch of different examples as to why this holds true. But
10:48this is just a small set of pros and cons, things to consider when thinking about using recursion.
10:58This brings us to a topic that I think is often overlooked when teaching recursion,
11:04which I think is one of the fundamental concepts that you really need to grasp
11:08to understand what people call quote unquote, magical
11:12about recursion. It's just magic with how it works. And after we look at this example,
11:18we'll start to realize how logical recursion is and why it's not necessarily such a magical thing.
11:26Let's imagine that you go to work one day, and the first thing that you want to do is check your
11:32email. And whilst checking your email, you get interrupted by your boss, and your boss says, Hey,
11:38I need you to go attend some meeting. And you have to actually deviate from your task.
11:44So you don't finish checking your email, you get interrupted. And before you can check your email,
11:48now you need to attend this meeting. Now, let's say your boss, well walk into this meeting,
11:53your boss interrupts you again. And he says, Hey, our investors are visiting,
11:58I would love for you to go to this board meeting and impress them with all your knowledge. And
12:03so again, we'll walk into this meeting, you get interrupted, you have to go impress the investors.
12:10Right, that's your next task. And so before you can attend the meeting, before you can check
12:14your email, you need to impress these investors. And finally, your boss, he interrupts you again.
12:21And he says, Hey, you know, I'm sorry. But I need you to go help Jake with his code, his code is
12:26failing. And we need to push to production. So now you have to basically avoid the investor meeting,
12:33avoid the initial meeting, you can't check your email until you help j code. Once you help him,
12:39this thing kind of gets popped off your to do list, you know, you go to the board meeting,
12:44you attend this original meeting. And then finally, you can check your email.
12:50And you may be asking, like, why is this ever at all relevant to recursion. And it just so happens
12:56that this sort of idea is exactly how the call stack works when we're talking about invoking
13:02methods within our programs. Let's take a look at this simple program here. Notice
13:09we have three method calls. And they're kind of chained together. The first one returns a string,
13:14but it has a dependency on B, B returns a string, but it has a dependency on C.
13:22And c just returns a string. So nothing fancy at all. Now, the call stack is going to be this sort
13:28of abstraction that our operating system leverages to store method invocations within our program.
13:36It allows us to understand what memory addresses we return data to, and it stores local variable
13:42information, like what are the parameters that were passed into me. So if we execute a,
13:48the first thing that goes on to the call stack is this sort of idea known as a stack frame.
13:54And it basically says, Hey, I want to call Hello, and I want to concatenate the result of B.
14:00But in order for me to concatenate the result of B, I need to actually now call B. So that pushes B
14:06onto the call stack. Now I'm in the same scenario, where I want to now return from B, but I have a
14:15dependency on C. So now I call C and put that on the call stack. And notice this is the same
14:21sort of process that we looked at in the previous analogy. I cannot return or pop
14:25these things off the stack until I kind of go in the order in which these things were called. So
14:32I returned friends, right. And now friends replaces that see invocation. And so now
14:37this has been fully evaluated. And so now since B is fully evaluated, I can return that value
14:44to the B method invocation. And now that B stack frame gets popped off the stack.
14:51And it's only at this point that I have now evaluated that entire chain of method calls.
14:57So now I can return this string value. And get my expected output.
15:04Now you may be asking, like why still? Why is this relevant to recursive thinking.
15:10And let's look at an example. Let's look at a call stack when we call these recursive calls,
15:16right? This is just a program that calls itself and it'll execute forever,
15:20right? So the first time I invoke a will now I need to invoke a, but it calls a again.
15:28And it just keeps happening, right? There's no stopping condition. And finally,
15:32there's going to be this point, this point in time where I try and invoke a again,
15:37and I get a, I get an error, and that error is a Stack Overflow.
15:41And this exception happens when we exceed the pre allocated buffer of memory that our program has.
15:48Right, we basically have run out of memory, we've exceeded the stack,
15:52and our invocations have overflowed, and we can no longer handle it.
15:56And this is the whole thing with recursion, why we need a base case, we need to return a value.
16:02So just like we saw previously, for methods that aren't recursive, we noticed that frames
16:08still grow and grow and grow. And the only way for those frames to shrink in size
16:13is for them to return some value for them to stop invoking methods. And the same holds true
16:20with recursion. The only difference is, we have some sort of base case something that says, hey,
16:27this is the one thing that I want to condition on to avoid us from further recursing.
16:35I want to start off the first technical component of this presentation looking at recursion with
16:40strings. And this is going to give us a really good idea of manipulating input parameters on
16:47the call stack recursively. And the first problem I want to look at is this idea of string reversal.
16:52And so what we do is we have an input string like the symbol engineer. And the idea is the
16:57output would be the input in the reverse order, right? And so the question is, how do we how do
17:03we build a really concise recursive function that gives us something like this. And as we look,
17:10as we look at the skeleton structure for this code, we of course, are going to have some sort of
17:15input, right? So the input is going to be some string, and the output is going to be the reverse
17:20version of that. And so we always ask kind of these two questions. The first is, what is the
17:25base case? And this is really asking, when can I no longer continue within my algorithm? And the
17:32next line of code is going to be all about what's the smallest amount of work I can contribute?
17:37So in this case, it's going to be basically between each invocation, what's the small
17:43unit that I can actually modify or manipulate to progress a little bit closer to the goal?
17:51So let's look at the first question. The first question is saying, When can I no longer continue?
17:57And I think I think when you think about this sort of scenario, there are two schools of thought.
18:03And when I when I like to construct base cases, I typically think if I were to just pass in a
18:09very small input, like what is the smallest input that I could just pass in to start
18:15to this function, where I would need to basically immediately return. And there could be two schools
18:22of thought with this approach, right? And the two schools of thought could be, well, one letter
18:28reversed is itself, right. And that could be a really, really good base case for string reversal.
18:35But we want to be even lazier. Like what is the laziest, like the least amount of work that I
18:41could even consider thinking about. And that would be the empty string, the empty string reversed,
18:47is again, just the empty string. And so if I passed in the empty string to this function,
18:52and it would only make sense to get the empty string back.
18:57And so if we, if we modify the code, and we look at this, we just have a simple base case
19:01where we evaluate if the input string is the empty string, then let's just return the empty string.
19:08But now we need to consider how do I even get to that point? What's the smallest amount
19:13of work that I can contribute? Right? And that's the question that we're asking here.
19:17I need to do something that whittles down the decision space within each recursive call.
19:25And so we kind of asked this question, what's the smallest unit that I can deal with in a string? A
19:31string is just a bunch of characters, right? And so maybe I can modify a single character.
19:37And this is where we get to this question. Let me pick a single character out of this string.
19:43And maybe where I position it will allow it to be concatenated from the call stack in the reverse
19:49order. And it turns out when we when we write this code, we get a recursive call where we,
19:56we take that first character from the input string and we concatenate After the recursive call,
20:03and you may be looking at this and you say, Okay, well, the input parameter has changed. And it's
20:08changed because we've actually shrunken down the decision space, we've shrunk in that input string,
20:13because our entire goal is to get closer to that base case, right. And so we've taken everything
20:20directly after the first character to the end. And the idea is that if we do this enough times,
20:25we can shrink our search space on each invocation and get the goal, which is the reverse string.
20:32So this first piece is all is all focused on shrinking the problem space. And the second piece
20:38is reflecting really the work that we're doing to contribute closer to the goal. And I think it's
20:44worthwhile to analyze what is happening on the call stack. So let's say that we pass in Hello.
20:51And we don't hit the base case, on line two, we immediately go to line six, which is basically
20:57the recursive invocation with the shrunken down substring. And then we concatenate the H. And just
21:04as we had discussed with call stacks, we can't pop this off the call stack until that recursive call
21:09has also completed, which adds an additional stack frame to the call stack.
21:15And you notice, again, we don't hit the base case, and we shrink down that input string,
21:19but we concatenate the first character. And we keep doing this. And it's nice, because I don't
21:24need to keep track of the H, I don't need to keep track of the E. It's all self managed for
21:29me in the stack frame on the call stack. And so I invoke reverse string again. And now I get Oh.
21:37And now watches this gets fairly interesting, because as I pass in,
21:40oh, I get to a point where my input string has been whittled down to just the empty string.
21:45And it just so happens that for this use case, this is the base case. So I return
21:51the empty string. So that reverse string gets evaluated the empty string
21:56from this base case, and I end up just returning the empty string plus Oh.
22:02And now this recursive call gets evaluated. And now I add L. And this just becomes o l, right.
22:09And so now I can return this. And this gets popped off the call stack.
22:14And now you can see that I'm basically returning these values to the stack frame that preceded me.
22:20And popping things off the call stack. This function gets evaluated in ADS II.
22:26So I return it and pop this off the call stack. This function gets evaluated to o Ll E.
22:32So I return it, it gets evaluated. And then this gets popped off the call stack. And as
22:39you can see, this is the goal, right? This is the reverse string. And it's the power of the call
22:44stack the power of these recursive calls that allow us to return values back down the stack.
22:51And this is a very good property that we can exploit when using recursion.
22:59Let's look at palindromes, palindromes are these unique words, where we can basically
23:08spell the same word forward and backward. Let's look at this word. The mechanical
23:14way that we kind of analyze if a word is a palindrome or not, is we look at both ends.
23:19And we basically say okay, do these letters match? Yes, they do. So we shrink in Word, we say do
23:24these letters match? Yes, they do. So we shrink in Word. And now this is just one character. And it
23:33proves that we've we've matched successfully. So this indeed would be a palindrome.
23:40Now let's look at a snippet of code to see how we could think about something like this recursively.
23:48Now, obviously, we're going to have a Boolean function, because it's either Yes,
23:52it's a palindrome or No, it's not. And we're going to evaluate some input string.
23:59And of course, the first thing we always consider is what is this base case, the thing that stops us
24:04from recursing? Now, think back to what I had said in the previous example,
24:09I always like to consider my base cases, what is the smallest input that I could just pass
24:14into this function? And it turns out very often not very often, for string recursion,
24:23you can typically whittle down your search space and evaluate the input length. So if you passed
24:27in a palindrome that was of size zero, then that's a palindrome, right? Because there's
24:33there's nothing that proves it's not a palindrome. There are no characters to compare against.
24:38And in the same vein, if we pass in just a single character, with a single character, both forward
24:43and backward is the same character. So that's also a palindrome. So these are really good use cases,
24:50or base cases to evaluate this conditional, which is whether or not a string is a palindrome.
24:57But let's continue we need to consider the small amount of work
25:00that we can do. And in the animation that we just looked at, you notice that we had two pointers,
25:06one on the left and one on the right, and we were comparing those strings, those characters,
25:10we're saying they need to be the same. If they're not the same at any point in time, then we've
25:15violated the property of a palindrome. And if we violate the property of palindrome, then we just
25:20go to this false. This is kind of this fallback base case. So at any point in the algorithm, if
25:27the characters don't match up at their respective opposite indices, then we can terminate,
25:32we return false and the false gets propagated through the call stack. And the initial color
25:37function would return the false. But if that's not the case, then we get to this interesting thing,
25:46where we call this recursive call, and it whittles down or sub our substring. So let's look at the
25:53call stack to understand what's happening. We pass in race car as an input string. And this
25:58of course, is a palindrome you can see race car forward and backwards, it's just race car.
26:04And the first thing we do is we evaluate this, this conditional this base case,
26:08is the length zero or one? Well, it's definitely not. So we continue. And now we compare the
26:13first character and the last character for this input string. And if they're equal,
26:18then we just call ourselves again, but we shrink that input string.
26:24And since these since R and R are equal, we add another stack frame to the call stack.
26:29And we've shrunken down our input string, we again, look at the base case, we don't
26:34satisfy it. So we compare the first and the last character. And we notice in this in this case,
26:40they're also equal. So we call ourselves again, right, and we don't pop the stack frame off the
26:45call stack, because we still have more work to do. And so we shrink down our input string,
26:51we still haven't satisfied the base case. And our characters
26:54at the first and last position are still the same. So we do just a little bit more work.
26:59And now we're at the last character. And we've already come to this conclusion that
27:05if the input length is zero or one, then we just return true.
27:09So for this one particular subproblem, this one particular element, this is indeed a palindrome.
27:14So what do we do, we say, yes, this was a palindrome and we pop it off the call stack.
27:20And since we return true, and all of these other conditionals have been satisfied, that we can just
27:27propagate through the true Boolean down the call stack. So we return true here and pop this off.
27:35We go to the next stack frame and return true here and pop this off. And now we
27:39get to the final stack frame, which evaluates to true. And this gets popped off the stack.
27:49Now I want to look at recursion with numbers. And the thing that you'll start to realize as
27:55we go through these sorts of problems, is that the same blueprint holds true for all of them.
28:01And the first problem I want to look at is this idea of converting decimal
28:05base 10 values to binary, which is a base two number format, ones and zeros. So the question is,
28:12how can we convert a number like 25 into its binary counterpart.
28:18And it turns out, there's a very mechanical way of doing this. So let's take the number 233.
28:24And the formula here, as we'll come to find is we can do a division by two and this is
28:30basically doing the floor operator. So it gets us an integer instead of a floating point value.
28:36And we get we get an output, which is 116. And we have a remainder, and that remainder is one.
28:43And the mechanical process that we can follow to convert decimal to binary is
28:47we take the results of this operation, which is 116. And we divide that by two.
28:53And we just keep evaluating, and this is 58, remainder zero, and then we take 58. And we
29:00divide that by two, and this is 29, remainder zero. And we basically just keep taking the
29:06result in the output and dividing it by two. And notice we're keeping track of the remainders here.
29:13And the interesting property by doing these operations gets us to a point where we can
29:18take all of these remainders. So notice, we've gotten to this base case, which is zero. And that
29:24kind of halts this progression. So now we're done. And if we take all of these remainders,
29:30in the order that they were basically pushed onto the stack, we can evaluate them and this is the
29:36result in binary string for 233. And the question is, how can we Okay, this this mechanical process,
29:44you know, very formulaic? How can we convert it into some recursive operation?
29:50Let's take a look at some of this code. Now, notice, we said the first thing is we took 233
29:57divided by two, we got some output The remainder was one. And so there are actually many ways
30:06of doing this problem. And we're going to keep it really simple. So notice we're dealing with
30:09strings. As the result outputs, we're going to be concatenating strings basically.
30:16And so what we consider here is we we think about that base case, right? If I hit zero,
30:23then there's no longer reason for me to divide further, right, I return my result.
30:31Now, if I have not hit zero yet, it means that I still have more division to do. And so the first
30:38thing that we do is we get that remainder. So when we look at 233, divided by two, we want to
30:45store that remainder because that represents one of the binary digits that we care about,
30:50basically tells us if the value is even or odd. And this is the binary,
30:54this is the remainder that will contribute to the result. And so that's why we store this
30:59in the result. And notice, we just prepend this to the result. And now what I do is I again, just
31:06call find binary and I shrink my problem space by half. And I just propagate the result through.
31:14Now let's let's actually look at the call stack. By coding this. And seeing what it
31:19looks like I want to take the code that we were just looking at, but look at it from
31:23the perspective of the call stack and understand how these stack frames are building up over time.
31:30Now, there are many ways to code this fine binary function. And a lot of people do it returning an
31:36integer. And that's completely fine. And if you want to do it that way, you can actually follow
31:40along with any modification of this and analyze the call stack with me. So as we run in debug,
31:48the call stack is going to show up down here. So these are all the stack frames that we can watch
31:53grow. And the variables on the current stack frame will show up under here in local. And so
31:59as we dive into this function, you notice that this is the first stack frame for find binary.
32:05And in order for this to complete, we need to return some value.
32:10We haven't hit our base case yet. So we jump into our work. And we just make another recursive call.
32:16So the first stack frame can't pop off yet, because we're going to invoke ourselves again.
32:20And once we do that, you notice that we add another stack frame.
32:24And also notice that the input parameters have changed. We've shrunken down our decision space,
32:28and we've appended the first digit to our binary result. We haven't hit our base case yet. And we
32:34continue. And again, we do a recursive operation. And our decision space keeps shrinking. And this
32:42is the same mechanical process that we saw in the animation, we divide by two and log the remainder,
32:48we divide by two and log the remainder. And we do this until we hit some sort of base condition.
32:54Right. And as we shrink down our problem space, notice we get to this point where
32:59the decimal is one. And that still is not our base case. So we go through,
33:05we get the result. And this binary string is looking pretty good. In on the final
33:11recursive call, you notice the decimal is now zero. And this is a really good case now,
33:17because now we can just return. So we come in here and we return this value.
33:23And this value comes in and says okay, find binary for that invocation returned this result. And so
33:30now we're just saying, okay, continue. And notice as I step through, the stack frames have grown.
33:38But now they should shrink off the call stack. So I step through. And notice they've all shrunken
33:44down, so all of them have returned, they've all returned a value. And now once I step over here,
33:54we noticed that the binary value has been evaluated,
33:57you can come into this debug console and look at it.
34:02And this is the resulting binary string. And so it's good to look at how the call stack is working
34:08to understand. Okay, how many stack frames do we build up to get to our result? And how do they
34:13unravel once we hit our base case here, we've just straight up propagated the result down through
34:19all of the stack frames, and all of them just return the same thing. And we'll look at a lot of
34:23different examples where all the stack frames kind of work together. And they wait for the result to
34:28do a little bit more work. And so there's a lot of different versions of this. The next problem
34:34that I want to look at with numbers is the sum of natural numbers. And the idea of this problem is
34:41you take an input number like 10, and then you sum all the values up to 10. And what we do here is we
34:50actually just add them all up, and we get some output and the output in this case would be 55.
34:56And the question is how can we build some succinct function that Does this recursively
35:03Now let's look at a little snippet of code and try to understand what's happening behind the scenes.
35:10So recursive summation, again, we take in an input value. And the first question we need to ask is,
35:16what is the smallest input value that I could pass in. So if I pass in one, for example,
35:23the sum of one to one is just itself. One, right. And so that's a good, that's a good place
35:32for the base case. And again, keep in mind, we are simplifying these functions. So you know,
35:38edge cases, we're not really focused on that. Right, now we're focused on the core goal,
35:42which is building a succinct function. So if I pass in one, I would return one. Now,
35:48if I pass in a larger number, like 55, I still have a lot of work to do, I need to add up
35:53all the proceeding numbers up to 55 from one. And so what I can do is I can take whatever value I am
36:00currently. And I can add it to myself again, but subtracting one from that numbers, right.
36:07So it shrinks me closer to this base case. Let's again, look at some code and understand how the
36:13call stack is working with this sort of code. So I've taken the same code from the slide. And now
36:19we want to look at the call stack and understand what's happening as we make these recursive calls.
36:24The first thing that we'll look at is the number five, so we want to add all values from one to
36:29five. Let's put a breakpoint here and debug into the call stack. So as I dive into this operation,
36:36we first evaluate the base case, which hasn't been hit yet. And so now what I want to do is
36:41I want to take five, and I want to add it to another recursive call, but that recursion
36:46is shrinking down the input space again. And so as I dive in, notice this input number
36:51change. So I make the recursive call, and the input number has shrunken down to four,
36:56and another stack frame has been added to the call stack. And so we keep evaluating has the
37:01conditional been hit? No, it has not. So I come in here and it shrinks down to three.
37:06And I keep doing this, and I come in here. I come in here. And now the input number is one
37:13has the base case been hit yet? Yes, it has. And so if I dive into this, you notice that we return
37:20one here. And this one returns this value to the stack frame right below it.
37:26And so notice that as I continue, that stack frame gets popped off. And you can see that the
37:32invocation of this method returned one here. And so now what I'm doing is I'm taking two plus one,
37:39and I'm returning this value and this value is going to continuously
37:43unravel through these stack frames. So notice, all of these get popped off.
37:50And here's the final invocation, the input number is 10 here. And as we continue,
38:01this is evaluating for recursive summation of 10.
38:08And so now again, for 10, we get down to a base case. And that base case is one. And if we look,
38:16so I'll put a breakpoint here. And we continue, we can see that we have the results of 15 and 55. And
38:26these get printed out. And so again, this is just an example to show as we're looking at the stack
38:31frames, how a stack frame can return a value to its previous stack frame to finish the operation.
38:38And that's the key here for recursion. And we'll keep doing this for a lot of the problems that
38:43we look at to get familiarized with how the call stack is working, and how the stack frames grow.
38:51I want to talk about divide and conquer algorithms, which are really great demonstrations
38:56of recursion. And the blueprint that we think about for dividing conquer holds through so
39:03we you know, still divide a large problem into several small problems.
39:08But divide and conquer is all about we divide them into subproblems. We independently solve
39:13them. And then we actually merge the results to solve some holistic problem,
39:18right? We merge them together and say, Hey, this is the solution. And they are typically
39:23recursive. And let's look at the first one, which is binary search. And the entire purpose
39:30of binary search is we look at a sorted list of numbers. And the key point here is they're sorted.
39:37And let's call this array. And the first thing that we say is we say alright,
39:41I'm going to start with the left and right index, so the far left index is zero and the
39:45far right index is the length of the array minus one. And the whole purpose of binary search is to
39:52find a value we want to find a value in this array. So we know that zero is less than the
39:58length of the array. So we can Have not hit our base case and we calculate the midpoint.
40:03So the midpoint is the left and right index added together and divided by two. And so we check, we
40:10say, okay, is that midpoint? The answer that we're looking for? So that's another sort of base case,
40:16have we hit or found the number 10? Here? And the answer is no. So we ask one of two questions, the
40:24first question that we ask is, is the number that we're looking for on the left half of the array,
40:30or is the number that we're looking for on the right half of the array.
40:34And remember, we just found the midpoint, so we're considering everything to the left and
40:38the midpoint and everything to the right of the midpoint because the input data is sorted. Now,
40:44if it's on the left half, which is what we're looking at here, then we completely discard
40:49the right half. And notice, the way that we do that is we change the bounds of the problem.
40:56So the left half stays the same. So our starting point on the left stays the same,
41:00but we only consider up to the midpoint minus one. And so that is our ability to shrink our decision
41:08space and completely discard the right half in each recursion, or each recursive invocation.
41:15Now, if we get to this other evaluation, this is basically saying the value we're looking for
41:19is on the right half. And what this allows us to do is we only consider our starting point to be
41:25the midpoint plus one all the way to the end. So we completely discard the left half
41:30for the rest of this problem. And this indeed, is also a recursive call.
41:34So look at the first stack frame in the call stack to the right, we start with zero,
41:40our upper bound index for the right variable is nine. And the number we're searching for is 10.
41:49So here's our midpoint, this is three. And we asked this question,
41:53Is this the value that we're looking for? Is this 10? And the answer is no, it's not.
42:00So what we can do is we can discard the entire left half of the search space because
42:0510 is greater than the midpoint. And it turns out, we add another stack frame to the call stack and
42:12notice how the parameters have changed. Now for the left, the starting bound, which is the left
42:17is five, which is the index where four is, and the upper bound is nine, which is the
42:23original length of the array that we're working with. And again, we calculate the midpoint,
42:28the midpoint on this sub array is nine, and we say is 10, greater than nine or less than nine.
42:35And of course, we know 10 is greater than nine. And so what we can do is completely discard
42:40the left half of that sub array and continue. And we add another stack frame. And the stack frame,
42:48the start bound is eight in the upper bound is nine. And we again, recalculate the midpoint.
42:55And the midpoint at this point actually turns out on line seven, we've hit this base case,
43:00the base case here is that we've found the number that we're looking for. And
43:03this is the solution. And so what we can do is just return this value.
43:08But we're not done yet, because we need to still consider the call stack. And so this value is 10.
43:14And so what we do from this stack frame is we return 10. And in this case, we returning the
43:21index that 10 is app. So 10 is at the eighth index of the array, and this gets popped off the stack.
43:28And now this binary search invocation has been completed, and it gets eight. So it just returns
43:34eight. And this gets popped off the stack. And now finally, we return eight. And we're complete.
43:42And the final stack frame gets popped off the stack. And that's how binary search works. Let's
43:48look at Fibonacci, a classical, mathematical and computer science problem that often demonstrates
43:55the power of recursion. And we're going to be looking at the non optimized version here.
43:59And we'll add some optimizations at the end. And let's look at the mathematical expression. First,
44:05we're basically saying that for some input in at the index n is going to be made up of the sum of
44:13the two values at the two indices that precede it. Let's look at the Wikipedia page for Fibonacci.
44:20And this is the sequence the Fibonacci sequence. And if we take one of these numbers like 55,
44:27it's the sum of the two numbers that preceded so 34 and 21. And if we look at 34,
44:34it's the sum of 21 and 13. And if we look at 13, it's the sum of eight and five, etc. And this,
44:40this formula holds true for all values of one to infinity. And so this is the Fibonacci sequence.
44:47So if we look at this expression again, now we have these base cases in pink, and basically says
44:53that for the values of at index zero and one, the base cases are zero and one was Effectively,
45:00and we can just return at that point. So that would be where we stopped that recursion.
45:05And the piece of yellow is just saying that this, this holds true for all values of one to infinity.
45:12So let's let's kind of look at this and understand why it differs from the previous.
45:18Now we're dividing and conquering, right, we're dividing this problem, we have fib of n minus
45:24one that needs to happen, we add it to fib of n minus two. And these are two recursive calls.
45:30And as we think back how the call stack works, we know that the recursion on the left needs
45:35to complete before we even considering, consider starting the recursive call on the right. So fib
45:43of n minus one could have a ton of different calls that need to complete before we even do
45:48the plus operator to fib of n minus two. So let's look at how this would animate.
45:54So we want to find the Fibonacci of five. And like I had said, we do not evaluate the right hand side
46:01of the expression yet, because we need to satisfy that first recursive call first. So this gets us
46:08F, fib of five minus one, which is four. And this gets us four minus one, which is three.
46:16And this process continues F of two. And remember our base case, f of one is just one, so we would
46:23return from here. And now to can evaluate the right hand side of its recursive operation.
46:29Remember, we're calling the same function over and over again. So now we've hit a base case,
46:34we've evaluated the left hand side, which is fib of n minus two, or fib of n minus one. And
46:41now we can do fib of n minus two for this value, which is f of zero. This again is a base case.
46:46So we can return from here. Now, the sum of these two values return and get passed up to F of three.
46:54And now F of three can evaluate its recursive call on the right hand side of that plus operator.
47:00And again, we do f of one, that's a base case, so we just return it. Right? Now this,
47:07these F of two, f of one get added together to return from F of three, and this gets passed to f
47:11of four. And now F of four can evaluate the right hand side of its expression, which is f of n minus
47:18two. So here we get F of two. And again, this recursive property holds true, this is a base
47:25case, we return it, we evaluate the right hand side, this is a base case, we return it. And
47:30now this gets propagated back up to F of four. And these values get propagated back up to F of five.
47:37And it's from here. Now, this is the very first, you know call of the function, we can now evaluate
47:43the right hand side of that plus operator. And again, we get down to f of three, we get down
47:48to f of two, and then this is f of one. And this is a base case. So we return it and this
47:54is f of zero, this is a base case, we return it. And notice like we're doing the same thing
47:58over and over again, this gets returned. Now we go to the right hand side, this gets returned,
48:04this gets passed up. And now we can add these two values. And that's how we find the Fibonacci.
48:11Now, we'll look at optimizations for this later. But I just want to point out one thing like as we
48:17evaluate this, notice, we have f of three here, we have f of three here. This is redundant,
48:23right? All of the nodes below F of three are the exact same. And so it seems extremely wasteful,
48:30that we're recalculating these values. And so as we'll come to realize, there are optimizations
48:35that we can consider to avoid recalculating something that we've already done the work for.
48:40So if you look, we have f of two, f two and f of two. And this is three nodes. And you
48:46can imagine for really large numbers, it turns out for Fibonacci, you know,
48:50most modern day computers cannot run Fibonacci for this function at a very high input. And that's
48:58because the recursive calls are so intensive. So we have to look at some optimization techniques
49:04known as memoization. Merge Sort is this poster child of divide and conquer when explaining this
49:14in a lot of computer science classes. And the idea is that we take in a bunch of unsorted
49:20values, like the following. And the idea is that we divide this array in such a way that we
49:27keep dividing. And then we merge up the sorted results to sort this array in ascending order.
49:34And it kind of looks like this. So we split the array in half and we say, Alright, I'm going
49:37to focus on the left hand side. And remember, before I even do the right hand side, I need to
49:43finish the left hand side first, right? That's the order in which recursion is going to operate here.
49:49And this process just holds through. So this is the left hand array and what do I do I split this
49:53in half. And now I decompose this into two parts. But again, I first have to focus on this half. And
50:02then I can focus on this half. So I look at, you know, I split these, and I look at foreign one.
50:09And the base case here is that you can't really soar just one value.
50:14And so I can stop splitting when I hit just one value. And I compare these two,
50:19and I merge and sort them together just by a simple comparison operator.
50:24Now I can look at the right hand side, and I basically split these. So I have one integer here,
50:30and I take two and zero, and two and zero gets split even further. And again, I'm down to this
50:37case where I just have digits, and so zero to get compared, they get merged up. Now three has
50:45a linear time comparison, again, zero and two, and these get merged together. And now we take
50:51one and 402, and three, these get merged together. And now I've solved the left half of this array.
50:59But remember, now I need to do the right half, we're evaluating in the order that recursion
51:03would consider this. So when we split this, I get the right half of the array. And I do the same
51:08thing on this side. So I take this array, split it, I get negative one and seven. This gets split,
51:16I compare them. And it just so happens, they were already in sorted order. So these get put back in
51:21the same spot. Now I take the right half of the array, right, and I split this even further.
51:30And so when this gets split, I have 10, nine and 20 gets split,
51:34nine and 20 are individual digits. And when I compare them, they are already in sorted order.
51:40And then I compare all the digits here, and they get merged back in sorted order.
51:45And then again, finally I compare these digits, and they get merged back in sorted order.
51:52And this brings us to the final merge, remember divide and conquer is all about
51:57dividing your problem into subproblems. And then merging the results together.
52:02So what we've done is we've just recursively merged all the results together from the
52:07recursive sub calls. And this is the final merge. And just to emphasize how this comparison works
52:14to ensure that these things get put back in sorted order, we do a linear comparison.
52:21And what that means is we basically have two pointers, starting with the left hand side
52:25and we say alright, which number is smaller, and we know negative one is smaller, so we put this
52:31in its spot and increment the pointer. And then we compare these two values will zero smaller here.
52:36So we put that in spot and increment the pointer. And we keep doing this as we compare values.
52:44And notice here, we've actually run out of values in the left hand array. And since
52:49we already know the right hand array is sorted, we just placed these back in the positions they
52:54belong. And as we look at the resultant array, we noticed that Merge Sort has sorted the input
53:00completely. And so this right here is the sort of solution. And now the question is, how do we build
53:09something like this? How do we devise a recursive algorithm that could construct a sorting,
53:15you know, solution to a problem like this, we're gonna look at some code to do that.
53:21So we have a blank slate here. And we want to consider how Merge Sort would work to satisfy the
53:27properties that we looked at. Now, the first thing I want to do is build the recursive call. And so
53:34remember, Merge Sort takes in an array, and it sorts it. And we're going to do this in place. So
53:40I'm going to build a function that's public, and static. And it's just going to be void. So we're
53:46going to modify the original input array. And what I'm going to take in this is going to be called
53:52merge sort. And it's going to take in just a one dimensional integer array, and we'll call it data.
53:58And it will have a start, and an end, which will represent the indices that we're working with.
54:06Now, for merge sort, this is going to be a recursive call, we need to consider the base
54:11cases. Remember, we work from the start to the end. And if those values overlap,
54:17then we've hit our base case. So we asked this question, if start is less than end,
54:21and we can continue doing work. But if the start passes, whatever the end pointer is,
54:27then there's no more work to continue. We've already sorted the data.
54:32And so remember, we're all about taking the array and splitting it in two halves, we want to
54:38divide the problem into two halves and solve them independently. And so the first thing that we can
54:42do is we can calculate the midpoint. And so what we do is we say in mid is going to be basically
54:48whatever the start index is of the array plus the end index, and we divide that by two,
54:54and that's going to be the midpoint that we're working with.
54:58And what do we want to do? Here, well, what we want to do is we want to divide the array
55:03in two parts. And so it would make sense for us to just call merge sort. We're dealing with the same
55:09data array. But our bounds are what has changed. And so the start is again, for the first half
55:17going to start at the same position, but the end is going to end at the midpoint.
55:24And that's going to be the left sub half. Now, if we think about the right sub half,
55:29the start is going to change, right? The start is going to be whatever the midpoint is plus one,
55:34all the way to the end. And this is how we can consider splitting this array into two different
55:40sub halves. But the question is, how do we how do we merge this data, right, what we're doing
55:47is we're just continuously dividing and dividing and dividing, but I want to be able to merge the
55:53data in sorted format. So let's build a function called merge. And what merge is going to do,
55:59it's going to take the original data array, and it's going to start taking the start the midpoint
56:05in the ending index. And remember that last animation that we just looked at
56:10does this kind of linear time comparison to replace the values in the correct spot
56:17when it's looking at the two sorted sub arrays, so I build a function here, it's going to be public,
56:25static void. And I'm just going to call this merge. And again, it's going to take in an
56:30integer array called data, a starting point, a midpoint and an end point.
56:39And now remember, we basically need to merge these values, but I don't want to modify the input array
56:45yet. So I'm going to build a temporary array. So it would make sense to build a temporary array
56:52to avoid modifying, can't type to avoid modifying the original contents. And so in order for me to
57:02do that, I can just build a simple temporary array here. And it will be a new int array.
57:08And the size is just going to be dependent on the indices, right, so I have n minus start, plus one.
57:17So this is going to build me a pre allocated buffer of memory to hold
57:23all the data for the sub arrays that I'm dealing with, from the start and end index.
57:31And now what I'm going to do is I'm just going to copy the values. So I want to I
57:36don't want to lose a reference to the start or midpoint. So I'm going to say int i equals start,
57:41we'll say j is equal to mid plus one, and k is equal to zero. and k is going to be this kind
57:48of tracker variable that we use to keep track of the values that we put into this temporary.
57:57So let's continue. Now recall back when we were merging the data together in that final sub call,
58:04that's a good way to kind of realize how this is working. So we're basically doing a linear time
58:10comparison, at the values in the left array, and the pointer on the right array, and we're saying
58:16which one is smaller, whichever one is smaller is going to be placed first in this temporary.
58:23And so I'm basically saying, while i is less than or equal to mid, which is going to be
58:29the left sub array. And we want to say, well, j is less than or equal to the end,
58:38then we can continue. And what is this saying? What this is saying is while both
58:44of the sub arrays have values, then try and merge them in sorted order.
58:51Right, and that's what we want to do. So we're starting with I, which is the left
58:55sub array up to the midpoint, and then j, which starts from the midpoint to the end,
59:01is going to be the right sub array. And we just want to compare these values.
59:05And so we ask a question, we say, Alright, well, if data sub i is less than or equal to data sub j,
59:15then we know what we know that the value in the left sub array is less than whatever the value
59:20is in the right sub array. So what we can do is we can say, Alright, in this temporary buffer,
59:25I'm going to put in at the index k data sub i. So the smaller value gets put
59:33next in the temporary. And now what I want to do is I want to increment i, since I've
59:38already placed it in the array, and I want to increment K, so I don't override this value.
59:45Now if this condition doesn't hold true, then what I can say is well, okay, so
59:49that would imply the opposite. So I would just say temp of K is going to equal data sub J.
1:00:07And then what we would do is we would say k plus plus, and j plus plus. And you can also get fancy,
1:00:14you can come in here and do something like k plus plus here. And you can do something like
1:00:18j plus plus here, it's both, it's going to be the same thing. So if you want to simplify your code,
1:00:23that way, you can do the post increment operator to reduce the amount of code.
1:00:30And this handles basically the comparison between the sub arrays. But remember the conditional here,
1:00:36the conditional says, we only do this while both values have values to compare against. And the
1:00:44example that we looked at, we actually ran out of data in the left sub array. And we just had to
1:00:50just blindly place all the data in the right sub array into the original array. And so we need to
1:00:56satisfy that case here. And in order to do that, we can just say, while i is less than or equal to
1:01:02the midpoint, so while there's basically data to traverse, still, we're just going to place
1:01:08it into the position of the temporary array where it belongs. This would be data, so I,
1:01:16and again, we would do k plus plus n i plus plus. And that handles exhausting
1:01:24the left sub array, if the right sub array has run out of values, so we say,
1:01:29add the rest of the values from the left sub array into the result. Now on the opposite side,
1:01:39if the left sub array has run out of values, but we still have data in the right sub array,
1:01:45then we just need to have the reverse conditional and we say, while j is less than or equal to end,
1:01:50then we're just gonna say temp sub k is equal to data sub j.
1:01:57And then again, we just increment K. And we increment J. And this is the same thing,
1:02:08we're adding the rest of the values from the right sub array into the result.
1:02:16You may ask, Are we done yet? And we're almost done. But we need to remember we built this
1:02:20temporary array, and this is void. And so we haven't really done any work yet. And so the
1:02:26question we need to ask is, how do we modify the original data array in memory. Now, we don't want
1:02:32to modify the entire array, we only want to modify the subsection that we're dealing with right now,
1:02:37in whatever recursive call that we're in. And so this brings us to the copy phase, how do
1:02:43we copy this data over from temp into the right positions of the data, which is the original data.
1:02:50And it turns out, we can just have a simple for loop where we say i is equal to start.
1:02:56And while i is less than end, right, so we're only taking the subsection that we're dealing with.
1:03:01So from start to end, right, which could be any, any bounds at any point of the recursion.
1:03:08So while I is equal to start n is less than or equal to end, we're just going to increment i.
1:03:14And in each iteration, we're going to load up the original data array at the index i
1:03:20to be equal to whatever's in the temporary array at the value of i minus start.
1:03:28So if the data array that we're dealing with, if the start is 12, then what we would do is we would
1:03:34say, all right, well, I equals 12. So 12 minus star is zero. So we're going to load data set 12,
1:03:41with whatever's at temp sub zero. And this is the copy phase. This is how we actually
1:03:46override values at each sub array. Let's actually run some input here,
1:03:55I'm going to have a new input array, we'll say, you know, data equals new int. And we'll just load
1:04:02it with some values, we'll say negative five, you know, 2010 320. And what I want to do is
1:04:11I want to sort this. So I'm going to call merge sort. And I'm going to give it the data array,
1:04:19the start is going to be the zeroeth index. And the end is going to be the length minus one.
1:04:27And so this should sort the array in place. And so what I can do is I can put a breakpoint
1:04:34to look at the array once it's been sorted. And then we'll look at the
1:04:37call stack to see what actually is happening behind the scenes.
1:04:44So I'm going to debug and we'll notice I get here and merge sort has completed. And
1:04:51what I can do is I can look at this stack frame and look at the data. And you notice that we
1:04:55have in the zeroeth index, negative 5023 10 and 20. And so this is the output in sorted order.
1:05:06But this doesn't really do us any good unless we understand what's happening at the level of
1:05:10the call stack. So let's take a look at that. By put a breakpoint in the merge sort function.
1:05:18Let's kind of look and see what's happening. If I dive in here, the first stack frame gets added
1:05:26to the call stack for merge sort. And I basically ask is start less than end? And the answer is no,
1:05:32we still have work to do. And so when I go in here, I calculate the midpoint. And I say I want
1:05:37to divide this array into two sub halves. And the midpoint here is two. And so what I do is I say,
1:05:44Alright, I'm going to divide everything from zero to two into its own set of sub arrays,
1:05:49and then I'll handle the right half. And remember, I can't even go to the right half until the left
1:05:54half has completed. So I dive into this. And now I'm looking at everything from zero to two.
1:06:02And I have to break this up even further. And so now I'm at this position where the midpoint
1:06:06is one. And again, I grow the call stack, and I'm still only on the left hand side.
1:06:12And I calculate the midpoint again, and I go again. And now we don't satisfy this,
1:06:17right, because zero and zero are equal. And so we actually pop this off the call stack.
1:06:25And now we return to the next recursive call. And the next recursive call says,
1:06:29Okay, now I want to handle the right hand side of this,
1:06:32right. And when I dive into this, I grow the call stack again. And again, we pop off, right, we
1:06:38don't satisfy this base case, and we kind of just continue this operation. And so now I've reached
1:06:44the basically the base case on the far left hand side of the first left sub half of this array.
1:06:51And what it's asking me to do is it's asking me to now merge these values in sorted order.
1:06:56So if I dive in here, and we look at the merge, let's analyze the start the mid and the end.
1:07:05Remember, I'm only dealing with basically two values here.
1:07:10And so if I go in here, we have a temporary array, and it's only of size two. And that's
1:07:15because my base case here for merge sort is only really comparing two values. And so we go in here,
1:07:21and we say, all right, which one's smaller, the left value, or the right value. And I come in
1:07:27here, and I say, Okay, well, here, the left value is smaller. So I load up K, I load up temp, and I
1:07:34put in negative five. And then I have another while loop. And remember, because I ran out of
1:07:40values to compare in the left sub array, I need to basically take all the values in the right sub
1:07:45array and put them in the positions they belong. So I come down here and I load up the values,
1:07:51increment the counters. And now we're done, because we've hit this base case.
1:07:59So now, I have this sorted sub array, negative five and 20. And what do I need to do I need to
1:08:05put these in the original spot, right? If we look at these values, I have, you know, I, J and K.
1:08:11What does that mean? Well, it means that from the position that I'm dealing with,
1:08:16in the original array, I need to override those values. So that's what this replacement is
1:08:20going to do. So coming here, I replaced value one, I replace value two. And now I'm done.
1:08:31And that is the process that we go through for a single iteration of merge sort. And
1:08:38this process will basically continue as we are dealing with bigger and bigger sub
1:08:43arrays as we recurse back from the bottom up, right, and now we're merging again.
1:08:49And notice, like, since we did the left sub half, which was just two values, now we're dealing with
1:08:55the right sub half, right. And now we have three values, and the right sub half of another sub
1:09:03problem. And so we just continue comparing and going up and going up. Now, we won't go through
1:09:08every stack frame. In this call. There are quite a few as we saw in the animation. But I encourage
1:09:15you to rewatch that animation because that is the order that the call stack will be evaluated.
1:09:21And that's the order in which things will recurs back up from the subproblems to get merged into
1:09:27some overall solution. And that's one of the key components of divide and conquer.
1:09:35linkless are really common data structures used to store data that is not necessarily contiguously
1:09:42stored in memory. And it turns out, you can do a lot of cool recursion on these sorts of things.
1:09:49We're going to look at link list reversal. And we'll look at an animation to walk through
1:09:54this code. Now the idea is that we have some sort of linked list. Let's say we have values
1:10:01in sorted order like this. And we'll just have a bunch of pointers. And the idea is that the head
1:10:08node changes from one pointing to two pointing to 345. Instead, we want six to point toward five,
1:10:14five, to point toward four, and so on. And when we look at this code, this reversal code, we asked
1:10:23this question, all right, if the head node is null, right, if we pass in a null value, or the
1:10:30next value from the head is null, then we just return the head. And this kind of brings us back
1:10:36to that idea of considering base cases. What's the smallest thing I could pass in? If I passed in?
1:10:42No, then I can just return null. And that would be a reversed list. Right? And in the same vein,
1:10:49if I passed in just a single node, where there was no next node, then I could just return head again.
1:10:55And those are good base cases for this solution. But the question is, how do I even start the
1:11:01reversal? What's the unit of work I need to do and that's what we're going to look at.
1:11:06So we start with one, the head node that we pass in on the first iteration is one. And we
1:11:12don't hit the base case. And so on line three, we see that we call reverse list head dot next. And
1:11:18that immediately pushes us to the next node. And we have one stack frame on the call stack.
1:11:25Now we're looking at two and this, this is not know either, and it also doesn't have a pointer
1:11:31pointing to null. And so we execute line three, again at another stack frame on the call stack.
1:11:37And that gets us to three. And this process continues all the way until we get to six.
1:11:44And when six gets passed in as a parameter, we say is it null? And the answer's no,
1:11:48but the next value is null. And so what do we return, what we do is we return
1:11:53head, which is just six, and six gets returned as the node to the previous value. So this is
1:12:01the base case. And we return this to five. And so now P has been evaluated to the number six.
1:12:10And what we're saying since since the number five is the current head node, we're saying
1:12:15five dot next dot next, equals five. And it turns out that what that means is we're basically just
1:12:22saying, Okay, well, what I want you to do is take six and have it point back to five,
1:12:28because head next to six, and head dot next, which is six dot next, is going to be pointing to five.
1:12:37And if that doesn't make sense, I encourage you to really slow down and read this code.
1:12:42And think five is the head node. And we want to say the next pointers, next position just
1:12:48points back to ourself. Now the problem here is that five is is also pointing to six.
1:12:55And if we were to trace this, this is this would be a cyclic dependency. And this would never end
1:13:00right. And so what we can do is we can just say fives dot next, can point to nothing, right? This
1:13:05is no, and so that gets dropped off. And what we return is we return six, because we want six to be
1:13:12the new head. And so six will just get propagated down the call stack to the original color to be
1:13:18the new head node. And that's why we return p here. And so now we return and we get to four.
1:13:28And when we look at four, we know that P is six. And what we're asking here is we're saying
1:13:36fours, next note is five, and I want five 2.4. And so again, we do the same thing,
1:13:43we take five, eight points to four. And to avoid the cyclic dependency, we drop this pointer here,
1:13:49this connection. And what do we return? What will you turn six, because again,
1:13:54six gets propagated through, and six is always going to be P in this case. And so now I return.
1:14:02And I know six is P, but head dot next is four.
1:14:06And so I want for 2.23. So I say head dot next dot next equals three. So I draw a pointer. And again,
1:14:14I dropped the cyclic dependency and I get rid of this connection. And now I return, P is still six,
1:14:21I return to two and I say two's next value, which is three, I want three dot next to point to two.
1:14:29So we do this, I dropped the pointer and I return. And then finally we do this again. I dropped
1:14:35the pointer and now we're done. So let's let's take the opportunity to look at the call stack
1:14:43and really understand how this is working in a little bit more detail.
1:14:47In order to save some time I've written some code. The first piece of code I want to look
1:14:52at is this idea of a node. Now this node is just an abstraction that holds a value
1:14:59and a pointer to The next node. And so this is the easiest way to build a singly linked list.
1:15:07Now, I also made a method called print link list. And this will just print all the values. And this
1:15:12is a verification that we can use to ensure that we've reversed the linked list correctly.
1:15:19And the final thing I want to look at is the actual code. So this is the same code
1:15:23that was on the slide. And I want to look at the call stack as we debug through this.
1:15:28So I have a singly linked list here 12345, just as we looked at, and they're all linked together.
1:15:36And what we want to do is we want to actually see how the reversal
1:15:39is working. So if I run and debug this, we're going to look at the call stack.
1:15:46So the first thing I hit is this call. And you'll notice in the stack frame, as I dive into this
1:15:51function, this is the initial stack frame that gets put onto the call stack. And ask myself,
1:15:57is the node that I'm looking at, which is one, is it No, and the answer is no. is the
1:16:02next value? No, the answer's no, it's two, right. And we can see that here.
1:16:07So I continue through. And I just call reverse list again, which is a recursive call. And as
1:16:13a dive into this, I add another stack frame to the call stack. And now you see my values too.
1:16:20And my next note is still not know. So I continue through.
1:16:25And I add another recursive call, which adds another stack to the stack frame
1:16:30to the call stack. And I continue. And this process is going to keep continuing.
1:16:37Now notice here, the value is five, but my next value is actually null. And that satisfies this
1:16:44base case here. So if we continue, you notice I just return null here. And this stops the
1:16:51recursion. So notice this stack frame should get popped off. So as I continue through, that stack
1:16:57frame gets removed. And now I'm looking at four. And it actually shows me what the result of this
1:17:04recursive call was for P. So as I step over, we can look at p and see that P is just five.
1:17:12And so I'm basically saying the node dot next, so let's evaluate that. So node dot next
1:17:20has a value of five. And I'm basically saying I want five two point. So I want five dot next 2.2,
1:17:29whatever my current value is, which is four, right? So we know no dot Val
1:17:37is four. So I'm changing the pointers here. So as I step over, now I have four
1:17:46pointing to know as I execute this, so we step over one more. So as I [email protected] dot next,
1:17:56there should be no which it is. And now the value P which was five should be pointing to for now.
1:18:05So P dot next, dot Val is four. Right. And so the whole idea here is that now
1:18:13we return the very last note again, and we pop this off the call stack.
1:18:20And the node that we're looking at at this point is three. And right now three is pointing to four,
1:18:28right? So if we look at no dot Val, which is three, we can say no dot next dot Val, and this
1:18:34is four. But this is wrong, right? Because we want for it to be pointing to three, not three
1:18:39pointing to four. And so that's what this line is doing. I'm saying I want four to point back
1:18:44to three. And so I do that, and then I drop the connection. And so now if I evaluate this,
1:18:52and we look at p, we can actually see the progress that we've made five points to four, and four
1:18:58points to three. Okay, so we're not done yet. But we're making progress. And as we return from here,
1:19:04we pop off the call stack. And we just keep doing this process. We return we pop up the call stack,
1:19:11we come appear we return and we pop up the call stack. And now we're back to the original call.
1:19:17And remember how we propagated the very last value throughout all these calls. So
1:19:24as we look at the reverse value, reverse dot Val, it's five and this is our new head node,
1:19:31which was the goal of this problem. And so if we come in we look at reverse, we say okay, we have
1:19:37five the next value is for the next value. There's three the next value, there's two and an x value.
1:19:43There's one, and then we're complete. And so this is how the call stack works for a linked list
1:19:50reversal. A really fun problem to consider with linked lists is how do you merge two sorted linked
1:19:54lists recursively. We're going to look at how the call stack works for this Let's analyze this small
1:20:01snippet of code and see if we can conceptualize what's happening on the call stack. We take in
1:20:06two head nodes. One was a list of values, and the other is a singly linked list of values as well.
1:20:13And we asked this question, the first question is, what's the smallest input I could pass in?
1:20:18And that's a good consideration for our base case, the same formula that we've been applying. If I
1:20:24pass in a head node for a, that's no, then I can just return b, because B would be merged with no,
1:20:33which would just be itself. And in the same vein, if b is null, and I merge that with a,
1:20:38then I can just return a. And if they're both No, then no merge with no is also just the null
1:20:46value. So this holds true. And that's the base case. But let's consider the other side of things.
1:20:53And this is kind of a similar comparison that we saw with merge sort.
1:20:57Right now we're considering, Okay, first of all, base case. But second of all, what's the
1:21:04unit of work that we need to do the recursion. And I think it'll help if we look at two lists.
1:21:11So we have two sorted lists of values. And we want to go through this recursive call.
1:21:17And the first thing that we do is we add a stack frame to the call stack.
1:21:22And it basically says, the head nodes that I have are one and four, so neither of them are null.
1:21:29And what I want to do is I want to say, all right, which which value is smaller,
1:21:34the value in the first node or the value in the second node A or B,
1:21:39A's data is one and B's data is four. So that first conditional is the one that will be
1:21:44recursive upon. And I basically say one dot next is going to be pointing to sorted sorted merge.
1:21:51And node A is going to be incremented by one value, so I add another stacker into the call
1:21:56stack. And so now I pass in eight. And now he is getting compared with four. And we still haven't
1:22:05hit our base case, right. And so I look at the L statement. And I compare eight and four and
1:22:10four is obviously smaller. And so this is going to be the next node that I consider.
1:22:16And I just continue this process. So now eight and 11 gets compared,
1:22:20instance eight is smaller, and I pass in 22. And I add another stack frame. And now 22, and 11,
1:22:27get compared. And since 11 is smaller, I pass in the node right after 11. And these get compared.
1:22:35And notice in the calls, the recursion needs to complete, but I'm actually setting these results
1:22:41as the next value. And so as we compare 22 and 1616 is smaller, so I pass in 20.
1:22:51And now 20 is smaller. But it's interesting because there is no node after 20.
1:22:57And so now I'm at this point where I have no. And now we consider the base case,
1:23:03if we have a null value, which is B in this case, then I just returned a. And if I return a then I'm
1:23:08just returning the reference to the node of 22. So here's the base case. And what I can do is I can
1:23:17just simply return 22 here, and this gets popped off the call stack.
1:23:22And this is where the unravelling starts to begin. So when I return 22 here,
1:23:30I actually change 20s dot next pointer, right, because I'm saying 20 dot next, is equal the
1:23:37result of sorted merge. And since sorted, merge returned 22, I can now modify this pointer.
1:23:46And from here, I return a. And when I return a I'm just returning 20.
1:23:51And this gets popped off the call stack.
1:23:55And now, you know we're looking at 16. And we're saying what should sixteens next pointer be? Well,
1:24:0216 should point to 20. But it already is pointing to 20. So we don't really need to do anything.
1:24:07And so I returned from here 16. And this gets popped off the call stack.
1:24:12And again in the same in the same case, 11 is already pointing to 16. So we don't
1:24:17need to modify anything. But we return 11 from here and this gets popped off the call stack.
1:24:24And now we have this question eight was pointing to 22. But since we returned to 11, we can now
1:24:30say that eight is going to point to 11. And that means we modify the pointer, which we've done.
1:24:37Right, and now we return eight from this stack frame, a smaller value,
1:24:43and this gets popped off the call stack. Now we compare eight and four four was
1:24:48pointing to 11. But since eight got returned from the recursive call,
1:24:52and we take four and we point it to eight now we return the smaller value From the stack frame.
1:25:03And what do we do here? Well, what happens here is we pop this off the call stack,
1:25:09and four is the smaller value. And so now what we want is we want one to point to the four node.
1:25:17And this is our final stack frame. And from here, we just return one, which is the head node,
1:25:24which is the smallest value from the two sorted lists. And from here, this gets popped off the
1:25:30stack frame. And if we follow these edges, or these pointers, we noticed one goes to four goes
1:25:37to eight goes to 11, to 16, to 20, to 22, to 40. And this ends up being our sorted list.
1:25:45And even for this, we can take a second to look at the code and understand the call stack.
1:25:53Alright, so I've gone ahead and I've actually built a couple linkless. So we have one here.
1:26:00So one, 513 14, and 550. And we have another completely independent link lists to 15 130
1:26:07203 50. And the idea here is how do we take these and merge them in their sorted order.
1:26:15And so we take the same code that we were just looking at,
1:26:19but now we want to analyze it from the call stacks perspective. And so I'm going to come over here,
1:26:24and I'm going to put a breakpoint on the initial call. And we're going to debug into this function.
1:26:35So as I dive into this function, you'll notice the call stack grows. And now we have two lists,
1:26:40this would be a and b from the example. So we have one and two. And this corresponds to the
1:26:45two initial nodes that we have here, two and one. And what we're doing is we're checking if you know
1:26:54the first list is null, then we return the second list. And if the second list is null, we return
1:26:59the first list. This, of course, does not hold true yet. So we continue and compare the values.
1:27:05Since one is less than two, we jump in here and we do another recursive call. And notice
1:27:12that we pass in the next value that one was pointing to, but two stays the same.
1:27:17And we continue this comparison. Now since five is greater than two, we go to the second conditional,
1:27:23and we do a recursive call. And notice the stack frames are just growing.
1:27:28They're just growing. And this stack frame is dependent on the result of this stack frame.
1:27:33And as I continue through and do these comparisons, I have another stack frame.
1:27:38And each subsequent stack frame has a dependency on the results of whichever one is above it.
1:27:45And so we keep doing this. And we do this until we hit one of these base cases.
1:27:50So I continue through. And now I've hit a base case,
1:27:54the value that we have is list one, which is 550. And I'm just going to return this. And when I
1:28:00return it, what happens? Well, it's the result of this function. So I say l to Next is 550. And when
1:28:08that gets evaluated, I just return here. And you notice that the stack frames will start shrinking
1:28:12now because we've hit a base case. And so as I continue through, and I'm returning these values,
1:28:19you'll notice that our call stack is shrinking in size. And we're basically reassigning the pointers
1:28:24to the next node. And it shrinks and shrinks and shrinks. And now finally, we get to a point where
1:28:32the sorted operation is complete. And so if we look at sorted merge, if we look at this value,
1:28:37we noticed that the first value is one, the next value is two 513. And it's now in sorted order. So
1:28:46we've taken two sorted lists and merge them in ascending order, which is the expected output.
1:28:53And this is just an example of taking two linked lists and showing how the merge operation works
1:28:59on the call stack. This brings me to one of my favorite topics, which is trees.
1:29:06And trees are one of the really fantastic data structures that work really well with recursion.
1:29:12And the first question we're going to look at is inserting a value into a binary search tree.
1:29:17Now a tree for especially a binary search tree is going to be a series of nodes and
1:29:22we're going to basically start from the top down, we're gonna have a bunch of connections,
1:29:27and the number of children at most that we can have from a single notice to
1:29:32and the least amount of nodes you can have is zero. And so what we're going to do is
1:29:35we're going to add a bunch of numbers here and analyze the properties of this tree.
1:29:41Notice that everything to the left of the root node 100 is less than 100. And everything to the
1:29:47right is greater than 100. Now this property it turns out holds true recursively. So if we look
1:29:54at at everything to the left is less than 80. Everything to the right is greater than eight
1:30:01But it's interesting because everything to the right is greater than 80,
1:30:05but also still less than 100. And so if you look, the largest value on the subtree of 80,
1:30:13on the right subtree is 95. And 95 is still less than 100. And so if you're not familiar with the
1:30:19properties of binary search trees, I encourage you to just do a quick, quick look and look at
1:30:25the rules for that. But this is pretty much the entire rule set for a binary search tree.
1:30:30And we're faced with this task and the task is to add this node, and the node is 108.
1:30:37And if we look at this value, we basically say, Okay, I'm going to start at the top of this tree,
1:30:41and I'm going to figure out where can I place 108. And I compare I say, is 108, greater than 100,
1:30:47or less than 100? or equal to 100? And I say it's greater than, so I go to the right.
1:30:53And I ask is 108 greater than 120, or less than less than or equal to 120?
1:31:00And we see it's less than so I go to the left sub half. And I asked the
1:31:04same question is 100, a greater than 110 or less than 110. And I see it the less than,
1:31:08and so now I go down here. And I draw connection. And this is the point where 108 belongs.
1:31:16And here you can see it's its sale still satisfies the rule set, right? 108 is greater than 100.
1:31:22So it satisfies that property, it's less than 120. It's less than 110. So this is the valid
1:31:28position for 108. And so let's look at the code. Turns out the code for this is extremely simple.
1:31:38And like I had said, before we consider the base case, what's the smallest thing I can pass in?
1:31:44Well, what if there is no root? Right? What if this is the first value that we're inserting
1:31:48into the tree? Well, if that's the case, then what I do is I just create a new node,
1:31:54I set the data, and I return that value. Right? And it turns out, that's a fairly good base case.
1:32:02Now, if we consider the other case, now we need to start thinking about, okay, well,
1:32:08what if I need to do some comparisons? And this is where I start comparing the data. So let's look
1:32:13at what's happening. The first question says, If I hit null,
1:32:17I've recurse to my end goal, according to the search tree properties of the binary search tree.
1:32:24Now remember, binary search tree node, insertions will always happen at the leaf level. So they
1:32:30always happen at the end. So if you've done all your comparisons until the very end,
1:32:35then you've hit a valid position to insert the data. Right? And that valid position
1:32:39would be when you have no more comparisons to do, which is implied by the head node B, no.
1:32:47Now the next conditional I look at is basically saying, Okay, I'm at a node,
1:32:52and I want to compare it to my current node. So remember, when we were comparing 108 to 100,
1:32:57I asked this question I say, is the node i want to insert greater or less than this value. If it's
1:33:03greater than I say, head dot right equals, and then I just make another recursive call. And I
1:33:10progress to either the left or right half of the subtree. The other side is just the opposite. So
1:33:18if I'm less than the current node, then I want to go down the left hand side of the sub tree.
1:33:25Now, this final piece right here, is, once I've done all this work, I've done all the insertions,
1:33:31I just want to return the original root node.
1:33:34And that original root node just says basically, here's the tree that you started with.
1:33:41Let's look at the call stack. During this insertion process.
1:33:48I call insert node. And I'm comparing 100 and 108. And I know 108 is greater than 100. So I
1:33:54recurse down the right hand side. Now when I get to this point, I add another stack frame. And I'm
1:34:00comparing 120 and 108. And I know 108 is now less than this. So I recurse down the left hand side.
1:34:09Now here, I'm comparing 108 and 110. Add another stack frame, I compare these values.
1:34:16And because it's less than I go to the left hand side.
1:34:19And this is interesting, because now my value that I compare against is no.
1:34:25And remember, when we look at the code here, no is just the base case. This is what we consider when
1:34:31we insert a node. And so I just create that 108 node and I return it right. And so here
1:34:38is where I would say, okay, new node had died data equals 108. And I would return this node.
1:34:45And so from this stack frame, I would actually return the 108 node and pop this off the stack.
1:34:52And what I would do here because I was saying 110 dot left, equals whatever that value was.
1:34:59Now I can draw connection to 108 and just start returning those values up the stack.
1:35:06And that's the process of inserting a value into a binary search tree.
1:35:12Let's look at another fun problem, which is also a kind of a fun depth first tree reversal problem.
1:35:20And the purpose here is to print all the leaf nodes. So we're looking at the same tree.
1:35:25But we want to build a function that prints out all the nodes
1:35:28that we see here in the order from left to right. So 30 6080 590-510-8115 and 150.
1:35:39Now if we think about the recursion for how this works, mechanically, we start at the root node,
1:35:44and we go all the way down. And we hit a leaf node here, so we would print it out.
1:35:50And what I would do is I would basically pop off the call stack and go to this node.
1:35:55But I would immediately go to this nodes, right subtree. And this would be another leaf node
1:35:59because it has no children. And I would print this and recurse up the stack. And then I would
1:36:04go back up to 80. And now go down, it's right half. And here, I'll go down its left sub half,
1:36:11find a leaf node return, go down the right sub half, find a leaf node return. And this process
1:36:16just continues. And the order of execution is really important to understand here. Remember,
1:36:22if I'm going down the left sub half, I can't even consider the right sub half until the left
1:36:27sub half has been fully explored. And that's part of the property that depth first search
1:36:33follows. And we'll look at another DFS example with a graph in just a second. So now I go down,
1:36:39I recurse down the left sub half, I find the leaf node I print it, I recurse back up and do this
1:36:45all the way until I'm basically out of leaf nodes to find which brings us here. And now we're done.
1:36:56So here's the code for this. And we'll look at this to understand
1:37:00how things get added on the call stack as well in the code. But again, our base cases,
1:37:07what happens if we pass in a null value, that's a pretty good base case, right?
1:37:11Because then we would just return there's nothing to print if you just pass a null.
1:37:17But we also have to think about the goal, the goal is to print the leaf node.
1:37:22And so we want to keep recursing until we hit a leaf node.
1:37:26And the properties of a node being a leaf node is that there are no children. And so this is where
1:37:32we start to ask, okay, if there are no children to the left, there are no children to the right,
1:37:37then I can actually evaluate the underlying value of that node and just return.
1:37:43Now, if we're not a leaf node, then we need to recurse down the left sub half of the tree,
1:37:49which is what we're doing here. And if we have a right sub half to recurse,
1:37:56then we go down the right sub half after the left sub half has been explored. So this allows
1:38:02us again, this is why we evaluate the left hand side first. And then we go down the right hand
1:38:07side recursively. And we do that for all recursive sub trees up until we're done. So let's look at
1:38:13the call stack and see how this is executing, or we're looking at here is the same program. So
1:38:20we have some code here, print leaves, and it's the same code that we looked at before. So if
1:38:26the input root node is null, we just return, we evaluate the left and right. And this basically
1:38:33checks if a given node is a belief. And we print it, and then we pop ourselves off the call stack.
1:38:43Now if we don't satisfy that, then we go down the left and right half the subtree.
1:38:48So using the same code that we looked at for insertion, I've actually built
1:38:51up a tree to use. So I have some input with a bunch of numbers. These are all the numbers
1:38:58that we were looking at before I believe. And it's just a random set of numbers. So nothing special.
1:39:03And we just insert them. So I have a function here from the previous example called insert node. And
1:39:08it just builds us a tree for us. And so now what I want to do is I want to print all the leaves here.
1:39:16So what I'm going to do is I'm going to add a breakpoint here. And we're going to debug straight
1:39:20into it. And the first question I asked is, is the root node? No. And the answer is no, it's not No.
1:39:27Right? So this first value. And so what do I do? Well, I recurse down the entire left half of the
1:39:34subtree. So remember, it starts at 100. And now I go down to the left. And since it's not No,
1:39:40I skip over this. And now I just recurse down the left half of the tree. And for that node, again,
1:39:47it's not know. And for that specific node i again recurse down to the left sub half of the tree.
1:39:54And I just keep going down the left half I don't even explore the right half
1:39:59until this level. Tap has been fully explored. And you notice we just printed out the first
1:40:04leaf node, which is 30. And it's only until I explored that entire sub trees left half, that I
1:40:11can now go to this other sub trees right half. So I dive in here. And now I go down the right half.
1:40:18It turns out that the right half again, is just another leaf node. And so I can
1:40:23just print this value. And if I put a breakpoint here, you'll notice that we just keep printing.
1:40:31You know, we hit Knowles, we hit Knowles, and we print the leaves.
1:40:35And you can see down here, this is the leaf node evaluation that we're doing.
1:40:40And the reason I wanted to walk through this animation is just further emphasize
1:40:44that when we're thinking about the call stack, I cannot even consider evaluating this expression
1:40:49until every recursive call, and every sub call has been fully evaluated.
1:40:56Once that holds true, then I can start unraveling the right sub trees and I work from the bottom up.
1:41:02And that's the idea for these kind of DFS traversals that we're dealing with.
1:41:09This brings us to our last section of algorithms that we'll be looking at. And we'll look at a
1:41:14simple example with graphs. And we'll just see how similar working with graphs is to something
1:41:19like trees. And we're going to look at a very popular algorithm known as depth first search.
1:41:25And the idea is that we start at a node like a, and we basically say we're searching for a node,
1:41:30let's say the node we're searching for is H. And so I start from a and I say, Okay, let me
1:41:34get all the neighbors and see is this my value, so a is not my value. So I go to my neighbor,
1:41:40and I say B, B is not my value, go to C, D is not my value, but I get all my neighbors. And this is
1:41:48at an interesting point, because I'm searching for H, right, which is in the far half. But when
1:41:54I get my neighbor's, let's say the first neighbor I get is E. And so I actually have to explore down
1:41:59the depths of E before I even consider going to H. And so I go down, and I see E. And now I go to F.
1:42:07And now I have to look at all of F's neighbors. So the first neighbor I go to is K.
1:42:12And if k had neighbors, I would explore all of those neighbors.
1:42:15But it doesn't, so I can just pop off. And now I go to J and back to F. Now I go to I am back to F,
1:42:24and I kind of recurse backup the call stack. So now that I've explored all the neighbors of
1:42:31right, I've explored one neighbor of D, I only have one unvisited neighbor left for
1:42:37me to explore. And it's g so I go to G and I say is this the value that I'm looking for?
1:42:42And it's not. So I look at the neighbors of G and I say is this the value I'm looking for?
1:42:46And it is. And this is the idea of depth first search. And so we're going to look at a piece
1:42:52of code and walk through it line by line and see how something like this would work recursively.
1:42:58We look at a piece of code like this, and we have the input node.
1:43:02And to avoid cycles, which can happen in graphs, which is different than trees will keep a set
1:43:09of visited values. So we never want to visit the same node more than once. And so that's what the
1:43:14visited set is going to do. And the goal integer here is just the node that we're looking for.
1:43:20So I know the graph we were just looking at was letters, but we're going to assume that we're
1:43:25working with a graph with integer values. And we ask our base case questions again. So think about
1:43:33the smallest thing you could pass in if you pass in an empty node, a normal node, then there's no
1:43:39way you could ever find the goal, because the goal is an integer value. And so here, we would
1:43:45just return false. So this is a base case. The other base case is if we've actually found the
1:43:51node. So let's assume the node you pass in is the gold node, then here we found the node. And so we
1:43:57would just return true here, and this would imply that we found the value that we're looking for.
1:44:02But let's assume that we haven't found the value, just like the example. The first thing
1:44:07that we need to do is we need to aggregate all of the neighbors from a given node. And so we're
1:44:12going to assume the node API has a function call that allows you to aggregate all the neighbors.
1:44:19And the first question we ask is have we have we visited this node before?
1:44:24Remember, we want to avoid cycles. And so we never want to visit a node more than once.
1:44:28And so if it's been visited, we just ignore it and we continue. But if it hasn't been visited,
1:44:34then we add it to the visited set. And we start the exploration. And we ask this question,
1:44:40have we found the node that we've been working with with this particular neighbor. If we've
1:44:46found the solution, then we can just return right away. Now if we haven't found the solution
1:44:54from this particular neighbor, then we'll continue recursing through the rest of the neighbors
1:45:00And it's at that point, if we found it, we would return true. And this brings us to our last base
1:45:06case, let's assume that we've traversed all of the neighbors. And we never found the solution.
1:45:13That would mean that the goal value that we're looking for was just never in the graph to begin
1:45:18with. And this brings us to our final base case of just returning false. And this is a way to say,
1:45:23hey, I've searched for this node, but it didn't exist in the graph. It's false,
1:45:29it did not show up in the search. And that's where we can terminate the algorithm.
1:45:36I think it's important to spend just a little bit of time talking about optimizations that
1:45:40you can make when using recursion. And the first that we're going to look at is
1:45:44memoir, zation. And caching, which we talked about briefly when writing Fibonacci.
1:45:49And the question that we're trying to answer here is how can we speed up our program by pretty much
1:45:54storing things that we've already re computed or computed for the first time. So if I've computed
1:46:00some very expensive operation, and I have to re compute it again, in a subsequent recursive call,
1:46:06I want to check to see if I've done that work already. And if I have,
1:46:09I'm just going to return the result instead of re computing that operation again.
1:46:14And the best way to kind of conceptualize This is looking at the Fibonacci tree sequence.
1:46:19Here, we see that I'm doing F of three twice, and I'm re computing F of two, three times.
1:46:24And the question is, why can't I just compute f of two once, and then just reuse that value,
1:46:30so I don't grow these sub trees. And it turns out, you can do that really easily.
1:46:35Let's look at the modified Fibonacci code. Notice I have a hashmap here and hashmaps have this
1:46:41property, such that we can retrieve values from the map in constant time access, so big O of one.
1:46:48And the reason is because the data that we put into the hashmap is hashed. And so we have
1:46:52constant time access to the memory addresses in which that data is stored. And so when I
1:46:58call the Fibonacci function, the first thing I always do is I say, Hey, does the cache have
1:47:03this value. And you can also notice that I've pre populated the cache with the base cases as well.
1:47:12Now in the instance, that the cache does not have the value, I still go about the recursive call,
1:47:18as I had done previously. But I ensure that once that recursive call has been evaluated,
1:47:23I put the result into the cache. And then I return my result.
1:47:28And this is a really key component because the cache is global, right. And so all the
1:47:33subsequent recursive calls are putting their results in the cache. And as things get added,
1:47:39and popped off the stack, I can just keep cross referencing the cache to see if I'm
1:47:43doing redundant work or not. And that saves me a lot of computational power. So that's the idea
1:47:49of memorization and caching. And you can do a lot of this in a lot of different situations.
1:47:59The next optimization I want to just discuss is this idea of tail call recursion optimization. And
1:48:06people usually refer to this as you know, tail call optimization, or tail recursion.
1:48:11And the idea here is that basically, the compiler in certain languages, especially functional
1:48:16programming languages, will optimize the number of stack frames that get added to the call stack to
1:48:23basically remove this idea of stack overflows in a lot of scenarios.
1:48:28Now, the way that the compiler does this analysis is it really looks at the last function call.
1:48:34And it has to be a recursive call. And we'll look at an idea of comparing these two things.
1:48:41And there was actually a response on the computer science Stack Exchange by this user,
1:48:46and he gave two examples. The first is this simple recursive factorial function.
1:48:53And notice that the final return value is a value multiplied by a recursive call. Now,
1:49:00this is not tail recursive, because the return value is not just the recursive call. And so in
1:49:08order for this to be tail recursive optimized, we need to modify to look something like this.
1:49:15Now, if you spend a second to look at this code, you'll realize that functionally it's
1:49:18doing the exact same thing. But we've had to modify the parameters to get to a point
1:49:24where we can build a function that's tail call optimized. And the reason it's optimized with this
1:49:31tail call recursive property is because the final return value is in itself just a recursive call.
1:49:38And it turns out in certain operating in certain languages, in their compilers, they've implemented
1:49:45some optimization techniques to exploit this property and reduce stack overflows.
1:49:52Now, I just want to make a couple notes on this. The rule of thumb is to always
1:49:56make your recursive calls be the last instruction Nothing gets added to it, just the recursive call.
1:50:04And the other thing to consider is that this is supported mostly by functional languages. But it's
1:50:10not inherent in languages like Python and Java and even JavaScript. There are certain browsers for
1:50:19ies 2016. They do support tail call recursion optimization for things like JavaScript,
1:50:25but it's not supported across the board. And so as you're considering this optimization technique,
1:50:32think about what language you're using. And think about, you know, the compiler that you're using
1:50:36and where your code is being executed to see if this sort of optimization is supported or not.
1:50:46So this brings us to our final slide. What's next? And when we ask this question, it's really
1:50:51to consider like how far do you want to go in your journey of recursion. And that brings us to
1:50:56another video that we'll have coming out, known as algorithmic mental models for backtracking.
1:51:02And this is the entire notion that we basically solve even more complex problems by looking at a
1:51:08decision space and recursively going through and seeing if our decision was good or bad,
1:51:13and backtracking to see if we can solve the solution in a different way.
1:51:17And that's the next phase that I think is important for understanding recursion.
1:51:21So thank you guys so much for watching. Be sure to check out my channel youtube.com slash the
1:51:25symbol engineer and connect with me on youtube or Twitter or LinkedIn. And I'd be happy to talk
1:51:31with you and answer any questions you may have. So thanks, guys for watching and have a good day.

About this transcript

This page contains the full transcript of Recursion in Programming - Full Course by freeCodeCamp.org, generated from the public captions YouTube serves with the video. The transcript has 19,459 words across 1,099 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.