UID:
almafu_9960120043102883
Format:
1 online resource (x, 191 pages) :
,
digital, PDF file(s).
ISBN:
1-139-17179-8
Series Statement:
Cambridge computer science texts ; 19
Content:
This book is devoted to recursion in programming, the technique by which the solution to a problem is expressed partly in terms of the solution to a simpler version of the same problem. Ultimately the solution to the simplest version must be given explicitly. In functional programming, recursion has received its full due since it is quite often the only repetitive construct. However, the programming language used here is Pascal and the examples have been chosen accordingly. It makes an interesting contrast with the use of recursion in functional and logic programming. The early chapters consider simple linear recursion using examples such as finding the highest common factor of a pair of numbers, and processing linked lists. Subsequent chapters move up through binary recursion, with examples which include the Towers of Hanoi problem and symbolic differentiation, to general recursion. The book contains well over 100 examples.
Note:
Title from publisher's bibliographic system (viewed on 01 Feb 2016).
,
Cover -- Frontmatter -- Contents -- Preface -- Introduction to recursion -- 1.1 Some simple examples -- 1.2 How does recursion work? -- 1.3 The storage cost of recursion -- 1.4 The time cost of recursion -- 1.5 Recurrence relations -- 1.6 The choice of the explicitly defined case -- 1.7 Two-level procedures -- 1.8 Developing the power example: a cautionary tale -- 1.9 Searching -- 1.10 Recursion and reversal -- 1.11 Using recursion indirectly -- Exercises -- Recursion with linked-linear lists -- 2.1 Some simple and general examples -- 2.2 Copying a list -- 2.3 Lists used to hold sequences -- 2.4 Lists as ordered sequences -- 2.5 An example: polynomials -- 2.6 Lists as sets -- 2.7 A large example: multi-length arithmetic -- 2.8 Iteration and linear recursion -- 2.9 More complex data structures -- Exercises -- Recursion with binary trees -- 3.1 Binary search trees -- 3.2 The importance of search trees: balanced trees -- 3.3 Preorder, inorder and postorder procedures -- 3.4 Some general binary recursive tree processing procedures -- 3.5 Expression trees -- 3.6 Writing expression trees -- 3.7 An example: symbolic differentiation -- 3.8 Another example: evaluating an expression -- 3.9 Binary decision trees -- Exercises -- Binary recursion without trees -- 4.1 An illustration: Towers of Hanoi -- 4.2 Analysis of Hanoi -- 4.3 Verifying the solution of recurrence relations -- 4.4 A variation on Hanoi -- 4.5 Trees of procedure calls -- 4.6 Adaptive integration -- 4.7 A sorting procedure: MergeSort -- 4.8 The analysis of MergeSort -- 4.9 Investigating variations of MergeSort -- 4.10 QuickSort -- 4.11 Heaps and HeapSort -- 4.12 Recurrence relations: another cautionary tale -- 4.13 Generating binary code sequences -- Exercises -- Double recursion, mutual recursion, recursive calls -- 5.1 An example of double recursion: determining tautology.
,
5.2 An example of mutual recursion: creating expression trees -- 5.3 Another example: Sierpinski curves -- 5.4 Variants of Sierpinski and its analysis -- 5.5 Ackermann's function -- 5.6 Recursive calls -- 5.7 Substitution parameters -- Exercises -- Recursion with n-ary trees and graphs -- 6.1 B-trees -- 6.2 The basic operations on B-trees -- 6.3 A discussion of B-trees -- 6.4 N-ary expression trees -- 6.5 The storage of n-ary expression trees -- 6.6 Directed graphs -- 6.7 Syntax analysis -- Exercises -- Simulating nested loops -- 7.1 The basic algorithm -- 7.2 Analysis of the basic algorithm -- 7.3 Permutations -- 7.4 Proof of the permutation generating procedure -- 7.5 An improved permutation generator -- 7.6 Analysis of the permutation generator -- 7.7 An application: topological sorting -- 7.8 Combinations -- 7.9 Subsets -- 7.10 An application: the set covering problem (SCP) -- 7.11 Compositions and partitions -- 7.12 An application: generating contingency tables -- 7.13 An example of double recursion: Latin squares -- 7.14 Approaching combinatorial problems -- Exercises -- The elimination of recursion -- 8.1 The tail recursion rule -- 8.2 Direct simulation of the stack -- 8.3 Direct use of the stack -- 8.4 Body substitution -- 8.5 Parameters called as variables -- 8.6 Some problems in conforming to the schema -- Exercises -- Further reading and references -- Index of procedures.
,
English
Additional Edition:
ISBN 0-521-26934-2
Additional Edition:
ISBN 0-521-26329-8
Language:
English
URL:
https://doi.org/10.1017/CBO9781139171793
Bookmarklink
