Base Condition Location

[00:00:00]
>> Kyle Simpson: Now there's one little part of this particular recursive algorithm that I want to call out. This is sort of a little nuance, but it actually can sometimes lead to better solutions. So I wanna at least call this out. There's one thing that's always kinda bugged me about recursive solutions the base condition here is at that very last time.

[00:00:19]
Remember we've got a string that's 100 characters long, and we pass in that final empty string. We make a function call. We pass in an empty string just so that we get zero back out. What has annoyed me always is that always felt like a completely wasted function call.

[00:00:37]
If I could just look ahead one character, I could know that I don't need to make that final function call in that particular case. It's not that that final function call is the difference between a performance solution and not, okay. So I'm not making a performance question here.

[00:00:54]
This is more of almost like an obsessive kind of thing, like, no, I don't want any more function calls than I ought to have. I wanna design an algorithm that only does the bare minimum necessary function calls. So is there some way for us to preserve the declarativeness of this but still avoid that final base condition?

[00:01:14]
And this is the pattern, it's a slight tweak on this pattern that I want you to consider. Instead of checking our base condition first, we can reorient ourselves to simply checking everything on this first character and only doing the recursion if there's actually more work to do. It's not as complex as that may sound.

[00:01:32]
So let's take a look. Here I'm going to compute first variable, that first variable, I'm gonna compute it first. And then my base condition is gonna look different. My base condition is going to check for a string length less than or equal to 1 rather than for 0.

[00:01:51]
Because I've already computed for a single character string, I've already computed my 0 or my 1. And now I'm simply saying I only need to do more work if there's actually other stuff in the string. If I'm in an empty string or a single character string, there is no more work to do.

[00:02:10]
So let's not even make the recursive colon that case, simply return the 0 or the 1. And if we've passed that return statement on line 3, we know there is more work to do. And we simply do the same work we did before which is first + the rest of the string, the count to the rest of the string.

[00:02:27]
It's just a slight tweak on the way of thinking, but it says, do the work now, think about the work now, and then decide if there's anymore work to do. Rather than sort of thinking about it in terms of deferring the work until later. It just changes the position of the basic condition.

[00:02:43]
And I've often found that that little tweak, even though it's sort of servicing my obsessiveness of not doing extra function calls. Actually that little tweak sometimes, unlocks better optimizations for recursion. So it's something to keep in your mind. It's something to make sure you're aware of.