Design and analysis of Algorithms, 2nd Edition

8

Design Using Recursion

Objectives

After reading this chapter, you should understand:

• The design of recursive algorithms
• Execution trace and its use in understanding control flow of programs
• How to express the execution trace using regular expressions
• Iterative and recursive functions
• The Ackermann’s function

To define recursion, we must first define recursion.

—Author unknown

To iterate is human; to recurse, divine.

—Author unknown

Chapter Outline

8.1 Introduction

8.2 Execution Trace

8.2.1 Regular Expressions

8.2.2 An Interesting Recursive Function

8.3 Another Look at Iteration and Recursion

Summary | Key Terms | Exercises | Web Resources

8.1  Introduction

We are already familiar with recursive algorithms and their implementation. It is ...