Introduction to Python Programming

# 12.1Recursion 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.

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

## 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

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.