CHAPTER 10
Recursion
10.1 Introduction to Recursion
10.5 Case Study: Tower of Hanoi
Solutions to Practice Problems
IN THIS CHAPTER, we learn recursion, a powerful problem-solving technique, and run time analysis.
Recursion is a problem-solving technique that expresses the solution to a problem in terms of solutions to subproblems of the original problem. Recursion can be used to solve problems that might otherwise be quite challenging. The functions developed by solving a problem recursively will naturally call themselves, and we refer to them as recursive functions. We also show how namespaces and the program stack support the execution of recursive functions.
We demonstrate the wide use of recursion in number patterns, fractals, virus scanners, and searching. We make use of recursion in this chapter's case study to develop a tool to solve, and visualize the solution to, the Tower of Hanoi problem. We also use recursion in Chapter 10 when developing web crawlers.
As we discuss when recursion should and should not be used, the issue of program run time comes up. So far we have not worried much about the efficiency of our programs. We now rectify this situation and use the opportunity to analyze several fundamental search tasks.
10.1 Introduction to Recursion
A recursive function is a function that calls itself. In this section we explain what this means and how recursive functions ...
Get Introduction to Computing Using Python: An Application Development Focus now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
