Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo

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

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

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
Citation/Attribution

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 permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a 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 digital format, then you must 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

© Jul 30, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo 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.