Quick Recursion  book cover
1st Edition

Quick Recursion




  • Available for pre-order. Item will ship after February 22, 2023
ISBN 9781032417585
February 22, 2023 Forthcoming by Chapman and Hall/CRC
96 Pages 14 B/W Illustrations

FREE Standard Shipping
USD $22.95

Prices & shipping based on shipping country


Preview

Book Description

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.

Table of Contents

Preface

1. Understanding Recursion

1-1. A Note on Languages

1-2. Recursive Definitions

1-3. A Simple Recursive Procedure

1-4. Factorial

1-5. The Principle of Information Hiding

1-6. When To Use Recursion

1-7. When Not To Use Recursion

1-8. The Four Rules

1-8-1. Rule 1. Handle the Base Cases First

1-8-2. Rule 2. Recur Only With a Simpler Case

1-8-2-1. An Aside: The Collatz Conjecture

1-8-3. Rule 3. Don’t use external variables

1-8-3-1. Deep Copies

1-8-4. Rule 4. Don't Look Down

1-9. What the Computer Does

1-10. Removing Recursion

1-11. Tail Recursion

1-12. Recursive Drawings

1-13. Fortran and Lisp

2. Data Structures

2-1. Arrays

2-1-1. Array Maximum

2-1-2. Quicksort

2-2. Lists

2-2-1. Lists in Java

2-2-2. Lists in Python

2-2-3. Accumulators

2-3. Binary Trees

2-3-1. Printing Binary Trees

2-3-2. Counting Nodes

2-4. Trees

2-4-1. Parse Trees

2-4-2. Indirect Recursion

3. Backtracking

3-1. The Backtracking Algorithm

3-2. Non-Recursive Backtracking

3-3. Keeping Backtracking Simple*

3-4. Pruning and Four Coloring

3-5. Binary Tree Search I

3-6. Binary Tree Search II

3-7. Tree and Graph Searches

3-8. Debugging Techniques

3-9. The Frog Puzzle

3-10. Frogs Accumulator

In Conclusion

Appendixes

Appendix A. Quicksort in Java

Appendix B. Quicksort in Python

Appendix C. Binary Tree Search in Java

Appendix D. Binary Tree Search in Python

Appendix E. Java Debugging

Appendix F. Python Debugging

Appendix G. Frog Puzzle in Java

Appendix H. Frog Puzzle in Python

Appendix I. Map Coloring in Java

Appendix J. Map Coloring in Python

Appendix K. Lists in Python

Appendix L. Trees in Java

...
View More

Author(s)

Biography

David L. Matuszek was Director of the Masters in Computer and Information Technology course at the University of Pennsylvania, USA (2001-2017). With 40 years teaching experience, and 45 years programming experience, David is skilled in both the design of innovative software systems and in teaching others how to master programming languages in an accessible and engaging way.