Quick Recursion (David Matuszek) (Z-Library)

📄 File Format: PDF

💾 File Size: 6.5 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Quick Recursion Recursion is the best tool for working with trees and graphs. But perhaps you’ve studied recursion and decided it’s too complicated. You just can’t think that way. That limits the kind of programming you can do. Good news! Recursion is actually easy. It’s just badly taught. See, many instructors talk about how the computer does it. They go on and on about what happens at each level of the recursion and how each level relates to other levels. The problem is that you can’t think in multiple levels. Nobody can. And you don’t have to. This book will show you how you can write recursive programs. Once you understand a few simple rules, you will wonder why you ever thought recursion was complicated. You’ll be able to write recursive programs quickly and easily. Well, as quick and easy as programming ever is, anyway.

📄 Page 3

(This page has no text content)

📄 Page 4

Quick Recursion David Matuszek

📄 Page 5

First edition published 2023 by CRC Press 6000 Broken Sound Parkway NW, Suite 300, Boca Raton, FL 33487-2742 and by CRC Press 4 Park Square, Milton Park, Abingdon, Oxon, OX14 4RN CRC Press is an imprint of Taylor & Francis Group, LLC © 2023 David Matuszek Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, access www.copyright. com or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. For works that are not available on CCC please contact mpkbookspermissions@tandf.co.uk Trademark notice: Product or corporate names may be trademarks or registered trademarks and are used only for identification and explanation without intent to infringe. Library of Congress Cataloguing-in-Publication Data Names: Matuszek, David L., author. Title: Quick recursion / David Matuszek. Description: First edition. | Boca Raton : Taylor and Francis, 2023. | Series: Quick programming | Includes bibliographical references and index. Identifiers: LCCN 2022041466 (print) | LCCN 2022041467 (ebook) | ISBN 9781032417585 (paperback) | ISBN 9781032417592 (hardback) | ISBN 9781003359616 (ebook) Subjects: LCSH: Recursive programming. | Recursion theory. Classification: LCC QA76.6 .M369 2023 (print) | LCC QA76.6 (ebook) | DDC 005.13/1--dc23/ eng/20221107 LC record available at https://lccn.loc.gov/2022041466 LC ebook record available at https://lccn.loc.gov/2022041467 ISBN: 978-1-032-41759-2 (hbk) ISBN: 978-1-032-41758-5 (pbk) ISBN: 978-1-003-35961-6 (ebk) DOI: 10.1201/9781003359616 Typeset in Minion by MPS Limited, Dehradun

📄 Page 6

To all my students past, present, and future

📄 Page 7

(This page has no text content)

📄 Page 8

Contents Author, xi Preface, xiii Chapter 1 ■ Understanding Recursion 1 1.1 A Note on Languages 1 1.2 Recursive Definitions 1 1.3 A Simple Recursive Procedure 5 1.4 Factorial 8 1.5 The Principle of Information Hiding 9 1.6 When to Use Recursion 15 1.7 When Not to Use Recursion 16 1.8 The Four Rules 16 1.8.1 Rule 1. Handle the Base Cases First 17 1.8.2 Rule 2. Recur Only with a Simpler Case 17 1.8.2.1 An Aside: The Collatz Conjecture 19 1.8.3 Rule 3. Don’t Use External Variables 20 1.8.3.1 Deep Copies 23 1.8.4 Rule 4. Don’t Look Down 25 vii

📄 Page 9

1.9 What the Computer Does 27 1.10 Removing Recursion 28 1.11 Tail Recursion 30 1.12 Recursive Drawings 31 1.13 Fortran and Lisp 33 Chapter 2 ■ Data Structures 35 2.1 Arrays 35 2.1.1 Array Maximum 35 2.1.2 Quicksort 37 2.2 Lists 40 2.2.1 Lists in Java 41 2.2.2 Lists in Python 43 2.2.3 Accumulators 45 2.3 Binary Trees 46 2.3.1 Printing Binary Trees 50 2.3.2 Counting Nodes 51 2.4 Trees 53 2.4.1 Parse Trees 54 2.4.2 Indirect Recursion 55 Chapter 3 ■ Backtracking 57 3.1 The Backtracking Algorithm 58 3.2 Nonrecursive Backtracking 60 3.3 Keeping Backtracking Simple 62 3.4 Pruning and Four Coloring 63 3.5 Binary Tree Search I 68 3.6 Binary Tree Search II 72 3.7 Tree and Graph Searches 75 3.8 Debugging Techniques 77 viii ▪ Contents

📄 Page 10

3.9 The Frog Puzzle 83 3.10 Frogs Accumulator 88 ■ Afterword 91 Appendix A: Quicksort in Java, 93 Appendix B: Quicksort in Python, 95 Appendix C: Binary Tree Search in Java, 97 Appendix D: Binary Tree Search in Python, 101 Appendix E: Java Debugging, 103 Appendix F: Python Debugging, 107 Appendix G: Frog Puzzle in Java, 111 Appendix H: Frog Puzzle in Python, 117 Appendix I: Map Coloring in Java, 121 Appendix J: Map Coloring in Python, 125 Appendix K: Lists in Python, 129 Appendix L: Trees in Java, 133 Index, 141 Contents ▪ ix

📄 Page 11

(This page has no text content)

📄 Page 12

Author I ’M DAVID MATUSZEK, known to most of my students as “Dr. Dave.” I wrote my first program on punched cards in 1963, and immediately got hooked. I taught my first computer classes in 1970, as a graduate student in Computer Science at The University of Texas in Austin. I eventually got my PhD from there, and I’ve been teaching ever since. Admittedly, I spent over a dozen years in industry, but even then I taught as an adjunct for Villanova university. I finally escaped from industry and joined the Villanova faculty full time for a few years, then moved to the University of Pennsylvania, where I directed a master’s program (MCIT, master’s in computer and information technology) for students coming into computer science from another discipline. Throughout my career, my main interests have been in artificial intelligence (AI) and programming languages. I’ve used a lot of programming languages. I retired in 2017, but I can’t stop teaching, so I’m writing a series of “quick start” books on programming and programming languages. I’ve also written two science fiction novels, Ice Jockey and All True Value, and I expect to write more. Check them out! xi

📄 Page 13

If you find this book useful, it would be wonderful if you would post a review. Reviews, even critical ones, help to sell books. And hey, if you’re a former student or colleague of mine, drop me a note. I’d love to hear from you! david.matuszek@gmail.com xii ▪ Author

📄 Page 14

Preface R ECURSION IS CONSIDERED TO BE AN “ADVANCED” TOPIC. It shouldn’t be. When my oldest daughter was in high school, she was deeply involved in a multiplayer dungeon (MUD) game. She implemented an email system for it, using a language called Forth, which uses recursion extensively. When she went to college, she took a programming class. After a week or so she called home and asked me, “Daddy, what are loops for?” When I explained, she said, “Why not just use recursion? It’s so much simpler.” I agree. xiii

📄 Page 15

(This page has no text content)

📄 Page 16

C H A P T E R 1 Understanding Recursion 1.1 A NOTE ON LANGUAGES Any programming book needs examples, and examples have to be in some language. This book uses two well-known languages, Java and Python 3. The code is kept simple, without any language-specific “tricks,” so it should be accessible even to programmers who know nei- ther of these languages. That said, it is impossible to avoid all language-specific features and still have working code. Python uses indentation to show nesting of statements, while Java uses braces. To remove leading blanks, Python uses strip() while Java uses trim(). Differences such as these should not greatly obscure the examples. 1.2 RECURSIVE DEFINITIONS A recursive definition is a definition in which the thing being defined occurs as part of its own definition. DOI: 10.1201/9781003359616-1 1

📄 Page 17

Sounds circular, doesn’t it? Circular definitions, in computer science as elsewhere, are valueless and should be avoided. The distinction between a recursive and a circular definition lies in the use of the work “part.” Any recursive definition has two parts: 1. a noncircular part, or basis, which is like an ordinary de- finition, and directly specifies some objects that fit the definition; and 2. a recursive (circular) part, which allows you to use the objects that fit the definition in determining whether new objects also fit the definition. Some examples should clarify these ideas. Here is an ordinary definition: Vowel: one of the letters “a,” “e,” “i,” “o,” “u,” or “y.” Clearly, there are exactly six things that fit the above definition of a vowel. Now consider the following circular definition: Yowl: any yowl followed by a vowel. By this definition, any yowl followed by a vowel is also a yowl; thus, if we could find one thing which is a yowl, then any things formed by adding vowels to that yowl would themselves be yowls. The problem is in finding that first yowl. Since we have no place to start, the definition is circular, and valueless. Now consider the following definition: Howl: 1. the letter “h,” or 2. any howl followed by a vowel. 2 ▪ Quick Recursion

📄 Page 18

This definition is recursive. The first part is an ordinary definition, and tells us that the letter “h” is a howl; this gives us a basis, or place to start. The second part is the recursive part; it tells us that, since “h” is a howl, so are “ha,” “he,” “hi,” “ho,” “hu,” and “hy.” But since these are howls too, so also must be “haa,” “hae,” …, “hyy,” …. “haaeeuooeea,” etc. Note that this is a “good” definition in the sense that some things are howls, some things are not howls, and it is easy to tell from the definition which are which. The “circularity” of the second part of the definition causes no harm because the first part provides a basis. Recursion abounds in computer science. A typical definition of “identifier” (or “variable name”), for example, is as follows. Identifier: 1. a letter, or 2. an identifier followed by a letter, digit, or underscore. Notice that the definitions of both “howl” and “identifier” allow arbitrarily long strings. It is possible to write recursive definitions which limit the size of the things being defined, but in general this is neither easy nor desirable. Instead, if there must be limits, they are set by some external agency. Some programming lan- guages, for example, allow arbitrarily long identifiers, but require that two different identifiers must differ in the first k characters, where k is set by the implementation. In the same way, the maximum length of a howl might be determined by your lung capacity. You have probably noticed that the above definitions don’t have to be recursive; they could be made into ordinary definitions by Understanding Recursion ▪ 3

📄 Page 19

using the phrase “any number of …,” which can be implemented with a loop. This is true—we don’t need recursion. In fact, re- cursion is never absolutely necessary, merely useful. The definitions we have considered so far have all been examples of direct recursion. For an example of indirect recursion, con- sider the following pair of definitions (adapted from Lisp): S-expression: an identifier or a list. List: a sequence consisting of 1. a left parenthesis, 2. zero or more S-expressions separated by blanks, and 3. a right parenthesis. Thus, the following things are lists (and also S-expressions): () (ZIP ZAP ZOT) (ONE (TWO THREE) ((FOUR)) FIVE) (() IXOHOXI ()) These definitions are mutually recursive: each is defined in terms of the other. The basis for the S-expression is an identifier, while the basis for the list is the sequence (). To show that these definitions “work,” consider the S-expression (NOT (HARD)). 1. (NOT (HARD)) is an S-expression because it is a list. 4 ▪ Quick Recursion

📄 Page 20

2. (NOT (HARD)) is a list because it consists of a left par- enthesis, the two S-expressions NOT and (HARD), and a right parenthesis. 3. NOT is an S-expression because it is an identifier. 4. (HARD) is an S-expression because it is a list. 5. (HARD) is a list because it consists of a left parenthesis, the S-expression HARD, and a right parenthesis. 6. HARD is an S-expression because it is an identifier. Q.E.D. Of course you don’t have to go through this complete process every time you see an S-expression, but we were being very formal. Now is a good time to put in a plug for the usefulness of re- cursion. The definition of “list” given above may seem confusing at first (if you’re not used to recursive definitions), but I chal- lenge anyone to write a reasonable definition of “list” which is equivalent to the one given above, yet does not use any form of recursion. 1.3 A SIMPLE RECURSIVE PROCEDURE A recursive procedure (or function, or method, or subroutine) is a procedure that calls itself to do part of the work. Again, the trick is in the use of the word “part.” If it called itself to do all of the work, the result would be an infinite recursion (the recursive equivalent of an infinite loop). Just as a loop does some part of the work during each iteration of the loop, so must a recursive procedure do some part of the work at each level of recursion, until eventually all the work is done. Understanding Recursion ▪ 5