The Invent with Python Blog

Fri 24 August 2018

PyOhio 2018 Recursion Tutorial

Posted by Al Sweigart in misc   

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: The video of the tutorial will be uploaded here a few days after July 28th, 2018.

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/