This page has materials for folks taking my two-hour tutorial, A Beginner's Guide to Tackling Recursion at PyOhio 2018 or following its video recording.
Note: I don't think I did a particularly good job with this tutorial. You may want to watch my North Bay Python talk on recursion instead.
To take this tutorial, you'll need:
- A computer with Python installed.
- To know how to launch the interactive shell, so you can follow along with the examples.
- To know how to launch a text editor, so you can save and run .py files.
- A beginner's level understanding of Python, including variables, loops, defining functions, lists, and dictionaries. That's it, really.
It's strongly recommended that you type the code as you follow along with this tutorial. This helps build the "muscle memory" of coding, and is much more effective for learning than simple watching the tutorial.
By the end of this tutorial, you'll learn:
- What recursion is, in terms of actual code.
- How recursion isn't a difficult so much as a poorly taught one.
- What are stacks and the callstack, and how does recursion use them?
- What is a stack overflow, and how does a base case prevent it?
- What are recursive and base cases?
- How recursive algorithms can't do anything that an iterative solution can do.
- How caching/memoization and tail call elimination prevent common problems in recursive algorithms.
- What are the types of problems where recursion is better than iteration.
Not all of the programs in this git repo are featured in the tutorial, but you can find code examples here: https://github.com/asweigart/recursion_examples
It isn't necessary to review this code before the tutorial.
The visualization tool used to explore these programs is http://pythontutor.com/