Defining a Recursive Function

00:00 Let’s talk about defining a recursive function. A recursive function is a function that is defined in terms of itself via self-referential expression. That means the function calls itself and repeats the behavior until some condition is met, and then that will either return a result or in the case of the Santa Claus example, just print some value. All recursive functions share a common structure made up of two parts.

00:27 You need to make sure to have both of these parts or else either, one, it won’t be a recursive function or, two, it will be a recursive function but not work correctly. The first part is the recursive case.

00:38 A recursive function has to call itself, but it has to call itself on a smaller version of the same problem.

00:46 The base case is that stopping condition so our function doesn’t call itself forever. This is the smallest instance of the same problem. Going back to the Santa Claus example, the recursive case was splitting the problem into two subproblems where each elf did half of the work, and then the base case was when the number of houses was equal to one and the elf delivered the present to that house. Let’s go through another example.

01:13 The factorial symbol (!) is defined as for any number n, n! is equal to n * (n - 1) * (n - 2) * (n - 3) * (n - 4), et cetera, all the way to 1.

01:31 We can also write this as n! = n * (n - 1)! because this part of it can be simplified into (n - 1)!. Well, look at that. The factorial symbol is on both sides of the equation.

01:48 That leads to a very natural recursive solution, because one of our subproblems is actually the smaller version of our larger problem. Before we jump into the solution, let’s run through what 5! would look like. Well, 5! is 5 * 4 * 3 * 2 * 1.

02:06 It’s also 5! = 5 * 4!. Okay. Let’s write a function factorial_recursive() and just write this right here, n * factorial_recursive(n - 1).

02:25 Save that. I have a autoformatter, so whenever it saves, it formats according to PEP 8 style guide. It’s a nice plugin in VS Code called Python. Let’s load our file interactively by using IPython, which is a nice interactive Python interpreter, like this.

02:47 I’ll use Command + K to bring it all the way to the top, and do factorial_recursive(5).

02:55 Uh oh, it says maximum recursion depth exceeded. Well, that means we kept calling this function over and over and over again until forever. Well, what were we missing? We were missing the base case.

03:10 So what is the smallest or the simplest factorial value? And also—we can look up here—what is the smallest value here? Well, that is 1. So when n == 1, return 1.

03:24 Save that, exit here, load it again, Up arrow. And it worked. We got 120, which is the correct answer for 5!. So, what actually happened there? Well, we called factorial_recursive() on 5.

03:42 What did this do? This returned 5 * factorial_recursive(4). What did that do? I’m going to bring this terminal, get this terminal out of here.

03:54 return 4 * factorial_recursive(3),

04:01 return 3 * factorial_recursive(2),

04:09 return 2 * factorial_recursive(1), and then this returned 1. And this became 1. 2 * 1 is 2, this became 2. This became 6, this became 24, and 120. Also notice how the 5 * 4 * 3 * 2 * 1 appeared right here. So that was the power—or that is the power of recursion—is we defined it just like this.

04:42 Our solution is only three lines long, but it actually called a bunch of times and got us to the correct value.

04:50 There’s one edge case we forgot here, and this is always important in writing functions in general, is think of all the possible inputs that n could be. Well, we define factorials to only allow for positive numbers and for zero, so we define 0! is just equal to 1, that’s just a rule.

05:09 So if we were to pass a 0 in here, it would not hit our if case, and it would do 0 * factorial_recursive(-1), which would go -2, and it would error.

05:20 So we actually just need a case here to return 1. Or an even cleaner solution would be turn this to n <= 1 and remove this.

05:32 So now it works for zero. And I guess for negative numbers there is no definition for factorial, so we can assume that n won’t be negative.