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.
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.
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:
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
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: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.
Become a Member to join the conversation.