Factorials

00:00 In the previous lesson, I showed you how a recursive function works. In this lesson, I’ll be using recursion to define a function that calculates factorials.

00:10 Before getting to the fractal code, let’s talk about the limits of a stack. Unfortunately, computer memory isn’t infinite, and in fact, typically, the call stack is given very little space, as you want most of your memory to be used for your heap.

00:24 If your recursive algorithm doesn’t implement a stop condition correctly, it can run forever, kind of like a while True. But Python’s got your back.

00:33 It imposes a limit and throws an exception if you exceed it. Let’s go see this in the REPL. I’m here in the REPL. Let me write a function.

00:52 Seem familiar? Almost like before, but this one’s got a bug in it. There’s no exit condition. What happens if I run it? The correct version from the previous lesson ensured that the counter stopped at zero. This one doesn’t. After a while, Python sees that this isn’t going to end and throws a RecursionError.

01:14 If you’re curious why that -993 shows up after the exception, it’s because print() buffers output. The exception triggers the print buffer to be flushed, but it doesn’t happen until after the stack trace is output.

01:26 You can determine the current limit of the stack from the sys module.

01:39 The default value is 1000. The sys module also has a way of setting the limit.

01:50 You can tell this is some old code, as it doesn’t use the naming convention that is done now, with underscores between the words—lovingly known as snake case.

01:59 Calling set,

02:04 I can set the value. And when I rerun the function, it blows up far faster.

02:14 Okay, factorials it is then. What’s a factorial? Well, it’s a math thing where n! is defined as the multiplication of all values between 1 and n. For example, 5! is 1 times 2 times 3 times 4 times 5, also known as 120 to its friends.

02:36 Factorials get really big really fast. One of the common places that they show up is in probabilities. Consider how most lotteries work. You have a bunch of numbers, and you pick some subset. For some reason, having 49 numbers and picking 6 of them is a popular combination.

02:54 There is a probability function called choose that is the number of combinations you can can select from a set of numbers out of a larger set, without duplicates.

03:03 This function is denoted C(n, r) or sometimes nCr, where n is the set of the population, and r is the subset being chosen. It is also denoted as n over r in parentheses.

03:18 There’s lots of choices for choice. The formula for the number of combinations is n! divided by r! times (n - r)!. My home province has two lotteries, one of which is the common 6-49.

03:34 Let’s plug in those numbers to see how many combinations there are. 49! on top and 6!(49-6)! on the bottom. The trick if you’re doing this by hand is to remember that 49! is actually 43! times 49 through 44.

03:55 Once you see that, you can cross out the 43! in both the numerator and denominator, giving you a much easier problem to calculate. Or you can use the nCr function on your scientific calculator if you prefer.

04:10 All told, there are 13,983,816 ways of choosing 6 values from a set of 49. That means winning the jackpot where you selected the same 6 choices as the lottery’s has about a 1 in 14 million chance. Probability is fun.

04:30 If a 6-49 lottery ran every single day, and you played every single day, on average, it would take you over 19 thousand years to hit the jackpot. If the tickets cost a dollar, you need the jackpot to be almost 7 million just to break even, and the important part of that last statement was on average. Of course, there’s no guarantee. By comparison, I found a bunch of different statistics on the likelihood of being killed by a meteor. Depending on whose numbers you believe, you’re somewhere between 10 and 20 times more likely to die from a meteor strike than win the jackpot. I mentioned my province runs two lotteries.

05:09 The other one is 7 choose 50. That’s almost 1 in 100 million. To put that in perspective, you’re 20 times more likely to be killed by lightning on one of your birthdays in your lifetime. Yep, man, I still occasionally play. Price of a fantasy rather than a tax on not understanding the math. Let’s go play with factorials in the REPL.

05:35 I’ll start by writing a factorial function …

05:40 and print() statement to help me see what’s going on …

05:47 and this rather compact statement is the actual work. If n is less than or equal to 1, return 1. Otherwise, return n times a recursive call to factorial(n-1).

06:02 Another print() statement to see what’s going on … and return the result. Let me try this out. Notice what happens here. Because the recursion is called before the second print(), you keep getting the first print() called until the end condition is met.

06:23 Once the end condition is met, the stack unravels, and then each function returns to its calling point. It is from there that the second print() gets invoked.

06:33 The deepest call returns 1, the second deepest returns 1 times 2, the third returns 2 times 3, and the last returns 6 times 4.

06:50 This file contains three different ways of achieving the factorial, allowing me to compare the performance of each. The first is the one you just saw, but without the print() statements.

07:01 This is the recursive version. The second uses a loop instead, looping over the range of values from 2 through to n, accumulating the result. And the third uses reduce() from the functools library. functools contains code that brings functional programming mechanisms to Python, hence the func part of the name.

07:22 The reduce() function implements a mechanism known as reduction, or sometimes folding. It takes a callable and an iterable. It calls the callable on the first two items of the iterable, stores the partial result, then calls the callable on the partial and the next item in the iterable. Sounds an awful lot like what was just written in the recursive version, right? To use reduce() for a factorial, the cullable is a lambda that takes two values and multiplies them together.

07:53 The iterable is the numbers in the factorial, specified here by range(). And just in case range() is empty, that or clause makes sure that a value of 1 can be used instead.

08:05 Let me open up the REPL, and I’ll try these out. Importing all three of them …

08:13 calling the recursive one … the loop … and finally reduce(). No surprises here, they all work. Let’s see how they do performance-wise. The timeit() function is a helper that lets you time the execution of code.

08:33 It’s a little weird. It takes two strings, the first containing the code to execute, and the second some setup. timeit doesn’t import anything from the namespace, so for our purposes, I need to use the setup to explicitly import the function being tested from the REPL.

08:50 Let me show you how that works.

09:02 The first argument is a string containing the call to recursive(). The second argument is also a string, which imports recursive from the __main__ namespace.

09:13 Don’t worry too much if this feels like black magic. It kind of is. The third argument there is how many times to invoke the function and time the whole thing. Running the call to recursive() 100 thousand times took 0.021 seconds. Let me do this again with the looping version.

09:37 A little slower, but not by much. Now, how about reduce()?

09:47 Half as fast. Hmm, guess this isn’t the place to be using functional programming. You know what? All this may have been educational, but it was also a waste of time.

10:00 Batteries are included. Python comes with a factorial function. Yep, it works,

10:15 and it’s almost 10 times faster. Also, the functions in the math module are written in compiled code under the hood. Hence, you get a big speed up.

10:28 Next up, I’ll show you how to use recursion to traverse tree data structures.