Introduction to Recursive Programming: 1st Edition (Hardback) book cover

Introduction to Recursive Programming

1st Edition

By Manuel Rubio-Sanchez

CRC Press

411 pages | 168 B/W Illus.

Purchasing Options:$ = USD
Paperback: 9781498735285
pub: 2017-09-06
$82.95
x
Hardback: 9781138105218
pub: 2017-09-21
$165.00
x
eBook (VitalSource) : 9781315120850
pub: 2017-10-05
from $39.98


FREE Standard Shipping!

Description

Recursion is one of the most fundamental concepts in computer science and a key programming technique that allows computations to be carried out repeatedly. Despite the importance of recursion for algorithm design, most programming books do not cover the topic in detail, despite the fact that numerous computer programming professors and researchers in the field of computer science education agree that recursion is difficult for novice students.

Introduction to Recursive Programming provides a detailed and comprehensive introduction to recursion. This text will serve as a useful guide for anyone who wants to learn how to think and program recursively, by analyzing a wide variety of computational problems of diverse difficulty.

It contains specific chapters on the most common types of recursion (linear, tail, and multiple), as well as on algorithm design paradigms in which recursion is prevalent (divide and conquer, and backtracking). Therefore, it can be used in introductory programming courses, and in more advanced classes on algorithm design. The book also covers lower-level topics related to iteration and program execution, and includes a rich chapter on the theoretical analysis of the computational cost of recursive programs, offering readers the possibility to learn some basic mathematics along the way.

It also incorporates several elements aimed at helping students master the material. First, it contains a larger collection of simple problems in order to provide a solid foundation of the core concepts, before diving into more complex material. In addition, one of the book's main assets is the use of a step-by-step methodology, together with specially designed diagrams, for guiding and illustrating the process of developing recursive algorithms. Furthermore, the book covers combinatorial problems and mutual recursion. These topics can broaden students' understanding of recursion by forcing them to apply the learned concepts differently, or in a more sophisticated manner.

The code examples have been written in Python 3, but should be straightforward to understand for students with experience in other programming languages. Finally, worked out solutions to over 120 end-of-chapter exercises are available for instructors.

Reviews

Recursion is a fundamental topic in computer science, but one that is frequently taught in a fragmented way as part of an introductory course and then set aside for such electives as discrete programming and difference equations. Rubio-Sánchez (Universidad Rey Juan Carlos, Spain) believes that there are better ways to approach a concept so powerfully connected to computation. His book provides a comprehensive and approachable treatment of recursive programming. The text contains mathematical proofs, as well as clear methods that students can follow to derive new results and expand their knowledge in areas the book may not cover. Many of the fundamental problems that recursion can solve are presented and discussed; more advanced problems are addressed through decomposition and analysis. The book also contains a section on algorithm analysis, which helps form the basis for more advanced material on computational complexity. This book is useful as a textbook for introductory programming courses when an instructor adopts a more fundamental approach than imperative programming, but it can also serve as a useful reference for those who wish to explore recursive programming on their own, or for algorithm designers in the industry.

--L. Benedicenti, University of New Brunswick (CHOICE)

Table of Contents

Basic Concepts of Recursive Programming

Recognizing Recursion

Problem Decomposition

Recursive Code

Induction

Recursion Vs. Iteration

Types of Recursion

Exercises

Methodology for Recursive Thinking

Template for Designing Recursive Algorithms

Size of The Problem

Base Cases

Problem Decomposition

Recursive Cases, Induction, And Diagrams

Testing

Exercises

Runtime Analysis of Recursive Algorithms

Mathematical Preliminaries

Computational Time Complexity

Recurrence Relations

Exercises

Linear Recursion I

Arithmetic Operations

Digits, Bits, And Strings

Additional Problems

Exercises

Linear Recursion II: Tail Recursion

Searching Algorithms for Lists

Partitioning Schemes

The Quickselect Algorithm

Bisection AlgorithmfFor Root Finding

The Woodcutter Problem

Euclid's Algorithm

Exercises

Multiple Recursion I: Divide and Conquer

Is A List Sorted in Ascending Order?

Sorting

Majority Element in A List

Fast Integer Multiplication

Matrix Multiplication

The Tromino Tiling Problem

The Skyline Problem

Exercises

Multiple Recursion II: Puzzles and Fractals

Swamp Traversal

Towers of Hanoi

Longest Palindrome Substring

Fractals

EXERCISES

Counting Problems

Permutations

Variations with Repetition

Combinations

Staircase Climbing

Manhattan Paths

Convex Polygon Triangulations

Circle Pyramids

Exercises

Mutual Recursion

Parity of A Number

Strategic Games

Rabbit Population Growth

Water Treatment Plants Puzzle

Cyclic Towers of Hanoi

Grammars and Recursive Descent Parsers

Exercises

Program Execution

Control Flow Between Subroutines

Recursion Trees

The Program Stack

Memoization and Dynamic Programming

Exercises

Tail Recursion Revisited and Nested Recursion

Tail Recursion Vs. Iteration

Tail Recursion by Thinking Iteratively

Nested Recursion

Tail and Nested Recursion Through Function Generalization

Exercises

Backtracking

Introduction

Generating Combinatorial Entities

The N-Queens Problem

Subset Sum Problem

Path Through a Maze

The Sudoku Puzzle

Knapsack Problem

Exercises

About the Author

Manuel Rubio-Sánchez received MS and PhD degrees in computer science from Universidad Politécnica de Madrid in 1997 and 2004, respectively. Since, he has had a faculty position at Universidad Rey Juan Carlos (Madrid, Spain), where he is currently an associate professor in the Superior Technical School of Computer Science. His teaching has focused on computer programming, ranging from introductory CS1 courses to more advanced courses on algorithms and data structures. He has published several research studies related to recursion in the computer science education conferences. His other research interests include machine learning, and exploratory data analysis and visualization. Finally, he has been a lecturer at St. Louis University (Madrid campus), and has carried out research visits at Université de Cergy-Pontoise (Paris), and the University of California, San Diego.

For more information on the author, please visit https://sites.google.com/view/recursiveprogrammingintro/.

Subject Categories

BISAC Subject Codes/Headings:
COM051010
COMPUTERS / Programming Languages / General
MAT000000
MATHEMATICS / General
MAT004000
MATHEMATICS / Arithmetic