This introduction to recursive algorithms and their complexity is suitable for CS1 and CS2 students. It can be used as a reference book for basic algorithms on recursive data structures and for basic program analysis techniques. Its stated purpose is as an auxiliary textbook for existing computer science courses, but it could easily be used as a textbook for a specialized course. The chapters are well structured, each with a summary and exercises. Detailed examples appear throughout.
Chapter 1 introduces recursion for readers who are familiar only with iteration and describes several recursive algorithms over integers and arrays. Chapter 2 analyzes the complexity of recursive algorithms in terms of recurrence relations and describes elementary techniques for solving these relations. Chapter 3 discusses the implementation of recursion via stacks. Chapter 4 introduces recursively defined data types (lists and trees), recursive sorting algorithms, and their complexity analysis. Chapter 5 handles more advanced sorting algorithms, as well as set algorithms.