The Invent with Python Blog

Writings from the author of Automate the Boring Stuff.

PyOhio 2018 Recursion Tutorial

Fri 24 August 2018    Al Sweigart

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.

You can watch the recorded video of this tutorial on YouTube.

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.

Pre-Tutorial Setup

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.

Handout form

(Filled out handout form)

Slides

Objectives

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.

Code Examples

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/


Learn to program for free with my books for beginners:

Sign up for my "Automate the Boring Stuff with Python" online course with this discount link.

Email | Mastodon | Twitter | Twitch | YouTube | GitHub | Blog | Patreon | LinkedIn | Personal Site