Recursive Traversal

[00:00:00]
>> Fair warning, might stretch your brain a little bit if you're not super familiar with the notions of recursion, if that's newer to you. It's another one of those stretch your brain things, but it really is actually the same concept as what we've seen before already a couple of times, which is take a bigger problem and divided down into smaller problems.

[00:00:20]
Almost all recursion is like that. If I asked, the countPaths function takes as its first input the starting digit and as its second input the number of hops to take. So if I called countPaths(4,6), what I'm asking is how many possible paths can I take starting from 4, where my path length is 6, my hopCount is 6?

[00:00:48]
Technically, I guess the path length would be 7 since the hops are 6, okay? How many paths can I take of length 7 where I've taken six possible hops? That's what is being asked. So how could we break this down into smaller problems? If you pull up on your screens a picture of the dial pad, you can tell me what are the three possible digits that I could go to from the digit 4?

[00:01:21]
Somebody say them out loud, what are the three digits that I can get to from the digit 4?
>> 3, 9, and 0.
>> 3, 9 and 0. So we could say that the number of places that I could get to from 4 with a hopCount of 6 is exactly equal to the number of places that I could get to from 3 with a hopCount of 5, whatever that is.

[00:01:49]
Plus the number of places that I could get to from 9 with a hopCount of 5, whatever that is, plus the number of places that I could get to from 0 with a hopCount of 5, whatever that is. Whatever those three things are, if you add them up, they have to be equal to whatever countPaths(4, 6) is.

[00:02:08]
There's a mathematical leap that I'm asking you to make, that some of you, that will be an easy leap, and others, you will be like, whoa, I don't believe that. But I want you to spend a moment if you are doubting that, look at that path and convince yourself that it has to be true, because there's nowhere else that we could go from 4 other than to go to 3, 9, and 0.

[00:02:35]
So this has to be accounting for all of those possible paths. Again, we referenced this earlier in the course. This is one of those fundamental principles that when you study something like discrete math, you just start getting really good at. You start getting almost this spider sense intuition of, I know that this is equal to that,because it couldn't possibly be divided any further.

[00:03:05]
There are no other options, so it has to be this, or the reverse of that has to be this. We get these intuition points from a study of discrete math, so it is worth thinking about and looking into, that's a good foundation for a lot of your algorithmic work.

[00:03:24]
Now, we have not yet answered how do I figure out what countPaths(3,5) is, (9,5), or (0,5). We haven't answered that yet. We're gonna answer that in just a moment. But whatever that answer is, do we now agree that if I add those three numbers together, that it has to give me the answer to countPaths (4,6)?

[00:03:46]
If you're still doubting it, just keep looking at that dial pad and looking at the possible ways that you could go, and convince yourself, is there anything else that I would need to account for other counts? And hopefully, you'll eventually get that light-bulb moment where you realize, yep, this has to account for all of them.

[00:04:09]
So how would I answer the countPaths(3, 5)? By the way, these are what those actual numbers are. The 168 possible paths that I can take from digit 4 making 6 hops. And here's the breakdown of those, 52, 52, and 64. How do I figure out something like countPaths(3,5)?

[00:04:35]
How I figure out countPaths(3,5) is I look at all the places I can go from digit 3. What are the places that I can go from digit 3?
>> 4 and 8.
>> 4 and 8. And I'm gonna take one fewer hopCount from those places, right? So starting from digit 4 with hopCount of 4 and starting from digit 8 with hopCount of 4, the amount of paths that I can do there has to be equal.

[00:05:06]
The two together have to be equal to the (3, 5). And so on, we could continue. We could say (4, 4) would break down into what its three constituent ones would be. And countPaths would break down into what its two constituent paths would be. We could keep going until, when would we stop?

[00:05:30]
When hop count was 0, because there's nowhere else to go. [LAUGH] We've made all the hops. You follow me? In other words, if I were to call countPaths(3,0), what should the return value be? This is a very critical point. Think to yourself, if I call countPaths(3,0) starting from digit 3 with no hops, how many possible paths are there?

[00:06:03]
>> 0.
>> There's only two rational answers, 0 or 1. I'm going to suggest to you why 1 is the right answer, because if they were all 0s at the end, we would never add anything up. So we have to define the base case as if I am on the key and I can't move anywhere, there is only one path for me to take, which is to stay right put.

[00:06:29]
So we define that base case as 1. If we define it as 0, all of our math is gonna add up to 0. [LAUGH] You follow me? So we actually already now have the constituent and it's not that much code. We already have the constituent pieces that we need to be able to calculate this.

[00:06:53]
We have the constituent pieces, because we see the recurrence relationship, which is the countPaths of any starting digit with a hopCount is equal to the 2 or 3 possible sub-countPaths with one fewer hopCount. That is the countPaths for all of my reachable teams with one fewer hopCount. And we know that the base case is that when hopCount comes in as 0, what do we do?

[00:07:19]
We return 1. So from that conceptual basis alone, we now have what we need to be able to solve this. I'm wanna give you one further set of diagrams for you to understand what's happening. In this diagram that I'm about to do that's gonna animate out, f is the countPath, but I just replaced countPath with f, because there's a bunch of stuff and I needed to save space, okay?

[00:07:49]
But when you see f(4, 6), that means countPaths (4,6). There are two kinds of ways that we could traverse through all of the possible paths to do the counting. We've referred to these before. We've referred to breadth-first and depth-first. You may have seen those terms before, but this animation shows you the difference in ordering.

[00:08:10]
So this would be a breadth-first traversal through all of those possible counts. And, You can see that we are going to the leaf level and going all the way through the possible leaves, and then going to the next level and checking out all of their leaves, and then going to the next level and checking out all of their leaves.

[00:08:34]
We are going wide before we go deep, and that's why this is called a breadth-first traversal. But you see there that the countPath (4.6) is the same thing. I wish I had a red mouse cursor here. But the countPath (4,6), this root node, is the same thing as visiting the countPath (3,5) plus the countPath(9,5) plus the countPath (0,5), who, in turn, are the same thing as f(3,5) is the same thing as visiting f(4,4) and f(8,4).

[00:09:08]
f(9,5) is the same thing as visiting f(2,4) and f(4,4) and so on. Does everybody see that? This isn't an actual physical tree, it's a conceptual tree for the call stack. These are all the function calls that we would make, recursively, as we went through it. Because counting addition is commutative, it doesn't matter what order we go through in this tree.

[00:09:38]
But that would be the breadth-first traversal, is looking at all of those and looking at all of those. As it turns out, it's going to be much, much easier to write a depth-first computation of this, far fewer lines of code. So here's the animation for the depth-first traversal.

[00:09:56]
By the way, we could write this, we would write it as a for loop with a queue. Breadth-first traversal is an iterative for loop with a queue. And I hinted at that when we talked about the problem before, you remember, okay? We're not gonna write that code, but you could write a version of this with an iterative and queue, it's just more work.

[00:10:16]
So the depth-first traversal looks like this, look at where we go first. We go from (4, 6) down to (3, 5), down to (4, 4), down to (3, 3), all the way down to the leaf. And then we backtrack up and then we go down to the leaves again and then we backtrack up, and we go down to the leaves again and so on.

[00:10:33]
And that's why you can see with that animation that we're going depth-first rather than breadth-first. Both traversals would visit every node, and therefore both traversals would make every function call, and therefore the entire resolution of this would be the same, which is 168. These are two different ways of conceptualizing the problem.

[00:11:04]
And it turns out that even though they would both give the same answer, one of them is drastically easier to code than the other. Follow me? But they are isomorphic, you could write them in either way, since the recursion is gonna be a lot easier, make a lot more sense.

[00:11:23]
So we're gonna do this approach with recursion. So hopefully you now are getting enough of the sense of that, that we can, Tackle writing the recursive version of countPaths. And while that was a lot of words for me to describe the algorithm, it might be somewhat anticlimactic that it's only gonna be a handful of lines of code, okay?

[00:11:48]
Remember in recursion, we always need a base case. What was our base case? What did I say we were going to simply define as happening at some point?
>> Return 1 where there's no hops.
>> When the hopCount was 0, we defined it as?
>> [INAUDIBLE] 1.
>> A path count of 1, right?

[00:12:23]
We just stay in place. So if hopCount is 0, return 1. I now need a variable that I will increment. I'll start it at 0, and I'm gonna call this pathCount, and that is going to be the thing that I return. Now, from a given starting digit, how do I know which nodes in the conceptual call stack tree I need to visit?

[00:13:04]
What thing tells me the answer to that question? Given a starting digit of, say, 4, how do I know where I need to visit? I need to visit a certain set of digits from what?
>> The reachable keys?
>> It's calling the reachable keys function, yes, but we don't even need to call that function in this case.

[00:13:29]
We can literally just do nearby keys of starting digit, right, cuz they're the same thing. Let's just skip the function call. Yes, the JavaScript engine would probably inline it, but there's no reason for us to call it unnecessarily. So if we were starting on digit 4, then this loop would do three different iterations, right?

[00:13:53]
It would do an iteration with 3, an iteration with 9, and an iteration with 0. And so digit would be 3, 9, and 0. So you ready for the big reveal? pathCount incremented by, CountPaths with the digit that we're looking at, in this case, 3, 9, and 0, and hopCount -1.

[00:14:25]
So hopCount starts out at 6, and then on the next recursive call stack, it's 5 and then it's 4 and then it's 3. And eventually, it gets to 0, and what do we do?
>> Return.
>> We return 1. I had to spend 15 minutes explaining through slides and diagrams and all kinds of complicated animations that which only took us a grand total of six lines of code to write.

[00:15:08]
Still, if you were presented this problem in a job interview, and you wrote those six lines of code correctly, I think it's probably an instant hire. [LAUGH] Because 99.9% of people would stare blankly at the screen, they'd fumble around, and maybe eventually get something kind of on the path.

[00:15:33]
But this illustrates how important it is as a skill that we engineers need that we be able to think this way. Because once I taught you to think this way, it didn't actually take much effort to code that way, didn't it? What was the real challenge? Helping you to understand the mental model, right?

[00:15:58]
If you can think algorithmically, you can code algorithmically. You follow me? Let's test it. Let's go back over to the browser, refresh the page. And we said that we wanted to take 6 hops, and we wanted to start from 4, and we know that the answer should be 168, right?

[00:16:27]
Let's try, and there we got our 168.