Recursion Basics

00:00 In the previous lesson, I gave an overview of the course. In this lesson, I’ll be introducing you to the concept of recursive functions and how they work.

00:10 To understand recursion, first you must understand recursion. I really wish I could take credit for that. I used to actually have it on a T-shirt. I don’t know the source of the original quote.

00:23 In mathematics, a recursive relationship is one defined based on itself. The definitions of many fractal functions are recursive. An example of this in real life is the definition of your ancestors.

00:37 Your ancestors are your parents, plus your parents’ ancestors. Ancestors is in both the definition and the algorithm for calculating the value. In programming, you do this through the use of a function that calls itself.

00:56 Consider the countdown() function. It takes an argument, n, prints it out, and then calls itself with 1 less than n. It is recursive.

01:05 So just how does that work? Well, when you call the function with an argument like 2, this gets encapsulated in a little chunk of memory called the stack.

01:16 The stack is separate from where most things get allocated. The place for everything else is called the heap. The stack is only used to track the calling order of functions and their local space. As a new function is called, a new frame is added to the stack.

01:32 When a function finishes, the frame gets popped off, and the program returns to the calling place of the parent function. This is a bit of an oversimplification, as Python uses references, and the stack can contain things pointed to the heap, but it’s close enough for our purposes.

01:50 When countdown() is called with 2 as an argument, a new stack frame is created with space for local variables and the arguments to the function. As countdown doesn’t have any local variables, that’s empty, but it does have an argument: n is 2.

02:05 The function runs, and the first instruction is called, print(). That prints the value of n, which at the moment is 2.

02:15 Next, the if checks if n is bigger than 0. It is, so countdown() is called again, this time with the argument of n - 1, which would be 1.

02:26 This causes the stack to get pushed down, and a new frame is created.

02:33 In the new frame, the arguments list contains n equals 1. The function proceeds the same as before. It doesn’t care who the caller is, just the local state. And n gets printed.

02:47 It’s still bigger than 0, and so countdown(n - 1) is called.

02:54 Once again, a new stack frame is created, and again, print() is run, outputting 0. This time, though, n is not greater than 0, so countdown doesn’t get called again.

03:07 This is the end condition for the recursion. If there had been code at this point, it would’ve run, but there wasn’t, so the function finishes and returns. Even if you don’t have a return statement, the same thing happens. It just returns None automatically.

03:24 When the function returns, the stack frame gets popped, and you’re back where you came from. There’s no code after that, so once again it returns. Then the stack frame gets popped.

03:38 You’re back where you came from. Once more, you’re done. And then in this case, control is returned to the REPL because that’s what called the original countdown(2) in the first place. Okay, so that was the how. What about the why? Well, there are a family of problems in computer science where recursive algorithms are easier to read and write than their non-recursive equivalents. For example, traversing tree-like structures, sorting, and fractals.

04:10 In fact, there are programming languages that use this mechanism as the basis for their building blocks. Lisp is one such language. Anything you can code in recursion can be done instead with loops.

04:22 The code might be easier or harder to read, but you can do it. And the reverse is true as well. Anything you can do with a loop you can rewrite with recursion.

04:32 For my CS geeks out there, Lisp and languages like it are Turing complete, so anything you can code in Lisp with recursion can be done in any other Turing complete language. It’s kind of the definition of Turing complete.

04:44 What about Python itself? Primarily, I find I end up using recursion for traversing tree-like structures. Sorting is built in, so you don’t have to implement it yourself, and it has functional programming features as well.

04:58 So the primary use I find I have to code is traversing tree structures.

05:05 Let’s shake off the abstract stuff and write some Python. Next up, I’ll show you how to code a function that calculates factorials.