Introduction to Recursive Programming

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.

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

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/.