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.
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
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.
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.
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.
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.
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 contains code that brings functional programming mechanisms to Python, hence the
func part of the name.
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.
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.
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.
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.
Become a Member to join the conversation.