Recursion via Pascal. (English) Zbl 0547.68003

Cambridge Computer Science Texts, 19. Cambridge etc.: Cambridge University Press. X, 192 p. hbk: £17.50; $ 34.50; pbk: £7.50; $ 14.95 (1984).
The book is one of a few books concerning recursive programming techniques. Pascal is chosen as a programming language for representation of basic notions and of both examples and exercises. Chapter 1 (Introduction to recursion) contains some simple examples such as the factorial function; here the author introduces several main notions - a linear recursion (in these procedures there is only one static call), a binary recursion (two recursive calls), an n-ary recursion (an indefinite number of calls, within a loop, for example). Some implementations of recursions are discussed, the notions of stack and depth of recursion are defined. The problems of both the storage cost and the time cost of recursion realizations are considered. To analyze the cost of recursion the author introduces suitable recurrence relations. Chapter 2 (Recursion with linked-linear lists) considers such data structures as lists and basic recursive procedures for its manipulations. Chapter 3 (Recursion with binary trees) describes some binary search trees and basic procedures for these trees (insert, delete, search); expression trees presenting arithmetic expressions also are considered. Chapter 4 (Binary recursion without trees) contains the analysis of the classical examples - towers of Hanoi, merge-sort, quick sort. Chapter 5 (Double recursion, mutual recursion, recursive calls) is devoted to such situations as a chain of procedures calls \(A\to B\to C\to...\to X\to A\); this situation is called indirect (or mutual) recursion in contrast with the direct recursion. Chapter 6 (Recursion with n-ary trees and graphs) considers more general data structures such as B-trees and directed graphs. Chapter 7 (Simulating nested loops) gives some examples of n-ary recursions - permutation generator, topological sorting, combination generator, partition generator, Latin squares. Chapter 8 (The elimination of recursion) considers how recursion may be eliminated. Some techniques are described (the tail recursion rule, direct simulation of the stack, direct use of the stack, body substitution). Every chapter is concluded with a number of examples.
Reviewer: Yu.M.Voloshin


68-02 Research exposition (monographs, survey articles) pertaining to computer science
68N01 General topics in the theory of software
Full Text: DOI