Design and Analysis of Algorithms

Chapter 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

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 known that generally a nonrecursive version of the algorithm will execute efficiently in terms of execution time and ...