The Three Laws of Recursion

Like the robots of Asimov, all recursive algorithms must obey three important laws:

  1. A recursive algorithm must have a base case.
  2. A recursive algorithm must change its state and move toward the base case.
  3. A recursive algorithm must call itself, recursively.

Let’s look at each one of these laws in more detail and see how it was used in the sum_of algorithm. First, a base case is the condition that allows the algorithm to stop recursing. A base case is typically a problem that is small enough to solve directly. In the sum_of algorithm the base case is a list of length 1.

To obey the second law, we must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way. In the sum_of algorithm our primary data structure is a list, so we must focus our state-changing efforts on the list. Since the base case is a list of length 1, a natural progression toward the base case is to shorten the list. This is exactly what happens in the sum_of algorithm when we call sum_of with a shorter list.

The final law is that the algorithm must call itself. This is the very definition of recursion. Recursion is a confusing concept to many beginning programmers. As a novice programmer, you have learned that functions are good because you can take a large problem and break it up into smaller problems. The smaller problems can be solved by writing a function to solve each problem. When we talk about recursion it may seem that we are talking ourselves in circles. We have a problem to solve with a function, but that function solves the problem by calling itself! But the logic is not circular at all; the logic of recursion is an elegant expression of solving a problem by breaking it down into a smaller and easier problems.

In the remainder of this chapter we will look at more examples of recursion. In each case we will focus on designing a solution to a problem by using the three laws of recursion.

Next: Converting an Integer to Any Base

Practical Algorithms and Data Structures

Introduction

Analysis

  1. The Big Picture
  2. Big O Notation
  3. An Anagram Detection Example
  4. Performance of Python Types

Stacks

  1. Introduction to Stacks
  2. A Stack Implementation
  3. Balanced Parentheses
  4. Converting Number Bases
  5. Infix, Prefix and Postfix Expressions

Queues

  1. Introduction to Queues
  2. A Queue Implementation
  3. Simulating Hot Potato

Deques

  1. Introduction to Deques
  2. A Deque Implementation
  3. Palindrome Checker

Lists

  1. Introduction to Lists
  2. Implementing an Unordered List
  3. Implementing an Ordered List

Recursion

  1. Introduction to Recursion
  2. Calculating the Sum of a List of Numbers
  3. The Three Laws of Recursion
  4. Converting an Integer to Any Base
  5. Tower of Hanoi
  6. Dynamic Programming

Searching

  1. Searching
  2. The Sequential Search
  3. The Binary Search
  4. Hashing

Trees

  1. Introduction to Trees
  2. Representing a Tree
  3. Parse Trees
  4. Tree Traversals
  5. Priority Queues with Binary Heaps
  6. Binary Search Trees
  7. AVL Trees

Graphs

  1. Introduction to Graphs
  2. Representing a Graph
  3. Word Ladders
  4. A Knight’s Tour
  5. General Depth First Search
  6. Topological Sorting
  7. Shortest Path with Dijkstra’s Algorithm
  8. Strongly Connected Components
  9. Prim’s Spanning Tree Algorithm