Skip to ContentGo to accessibility page
OpenStax Logo
Introduction to Python Programming

12.1 Recursion basics

Introduction to Python Programming12.1 Recursion basics

12.1 Recursion basics

Learning objectives

By the end of this section you should be able to

  • Describe the concept of recursion.
  • Demonstrate how recursion uses simple solutions to build a better solution.

Recursion

Recursion is a problem solving technique that uses the solution to a simpler version of the problem to solve the bigger problem. In turn, the same technique can be applied to the simpler version.

Checkpoint

Three Towers

3 towers; ch 12, video 1

Concepts in Practice

Three Towers and recursion

1.
How is the problem of moving two rings solved using recursion?
  1. Move the small ring to the middle tower, move the bigger ring to the target tower, and move the small ring to the target tower.
  2. Move two rings from the source tower to the target tower.
  3. Cannot be solved with recursion.
2.
How is the problem of moving three rings solved using recursion?
  1. Move three rings from the source tower to the target tower.
  2. Move two rings to the middle tower, then move the biggest ring to the target tower, and finally, move two rings to the target tower.
  3. Cannot be solved with recursion.
3.
How many times is the two-ring solution used with three rings?
  1. 1
  2. 2
  3. 0

Recursion to find a complete solution

The recursion process continues until the problem is small enough, at which point the solution is known or can easily be found. The larger solution can then be built systematically by successively building ever larger solutions until the complete problem is solved.

Checkpoint

Solving Three Towers

Solving 3 towers; ch 12, video 2

Concepts in Practice

Solving Three Towers

4.
How many total steps does it take to solve two rings?
  1. 1
  2. 2
  3. 3
5.
How many total steps does it take to solve three rings?
  1. 3
  2. 4
  3. 7
6.
How many total steps does it take to solve four rings?
  1. 15
  2. 7
  3. 3
PreviousNext
Citation/Attribution
Reuse and redistribution of this content in digital or print format:
  • This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's prior written permission.
  • This book uses the Creative Commons Attribution-NonCommercial-ShareAlike License, which means that you can reuse and modify the material only for noncommercial purposes, must attribute OpenStax, and must distribute any derivative works under the same license.
  • Any commercial printing of this textbook, including using a local or custom printer, must be approved by OpenStax, and proper citation provided.
  • OpenStax-copyrighted images, activities, assessments, and similar components of this book are subject to the same licensing – CC-BY-NC-SA. They can be used for noncommercial purposes with attribution. Commercial use requires permission.
  • Permission requests: Anyone who intends to incorporate this content (including text, images, and other components) into large language models, use it in AI offerings, use it commercially (including in print), and/or has questions about another use case is welcome to complete our reuse request form.
Attribution information
  • If you are redistributing all or part of this book in a noncommercial print format, then you must include on every physical page the following attribution:

    Access for free at https://openstax.org/books/introduction-python-programming/pages/1-introduction

  • If you are redistributing all or part of this book in a noncommercial digital format, then for every page that includes OpenStax content, you must license the derivative work under the same CC-BY-NC-SA license as the original, and include on every digital page view the following attribution:

    Access for free at https://openstax.org/books/introduction-python-programming/pages/1-introduction

Citation information

The information below includes the information needed to generate citations in most major styles (APA, MLA, etc.); you must reformat and organize the information as needed to fit the requirements of the style. Use the information below to generate a citation. We recommend using a citation tool such as this one.

© Apr 23, 2026 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike License. The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo, and Rice University name, and Rice University logo trademarks, or wordmarks are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.

This book utilizes the OpenStax Python Code Runner. The code runner is developed by Wiley and is All Rights Reserved.