Overview

Sometimes the most natural way to solve a problem is to first solve smaller versions of the same problem and then build on that solution. As strange as it might seem, in Python functions are allowed to call themselves to accomplish just this sort of problem-solving approach. This is called recursion and it can be a bit tricky to wrap your head around at first.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the high-level idea of recursion
  • Explain how a function can call itself
  • Explain what a base case is

Advanced Learning Objectives

After class, you should be able to:

  • Write a recursive function to solve a problem

Reading

You should read/watch the following and complete the embedded checks:

  • Runestone (new book!) 4.2-4.4
  • Runestone (new book) 4.7

These are from the new book that we are using, Problem Solving with Algorithms and Data Structures using Python by Brad Miller and David Ranum.