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.

01:06 This one doesn’t. After a while, Python sees that this isn’t going to end and throws a RecursionError. If you’re curious why that -993 shows up after the exception, it’s because print() buffers output.

01:20 The exception triggers the print buffer to be flushed, but it doesn’t happen until after the stack trace is output. 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.