Introduction to Recursion

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. In computer science, recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

Next: Calculating the Sum of a List of Numbers

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