Introduction to Recursive Programming

Introduction to Recursive Programming

by Manuel Rubio-Sanchez
Released October 2017
Publisher(s): CRC Press
ISBN: 9781351647175

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

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

 

Table of contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright Page
  5. Table of Contents
  6. Preface
  7. List of Figures
  8. List of Tables
  9. List of Listings
  10. Chapter 1 ▪ Basic Concepts of Recursive Programming
    1. 1.1 Recognizing recursion
    2. 1.2 Problem decomposition
    3. 1.3 Recursive code
    4. 1.4 Induction
      1. 1.4.1 Mathematical proofs by induction
      2. 1.4.2 Recursive leap of faith
      3. 1.4.3 Imperative vs. declarative programming
    5. 1.5 Recursion vs. iteration
    6. 1.6 Types of recursion
      1. 1.6.1 Linear recursion
      2. 1.6.2 Tail recursion
      3. 1.6.3 Multiple recursion
      4. 1.6.4 Mutual recursion
      5. 1.6.5 Nested recursion
    7. 1.7 Exercises
  11. Chapter 2 ▪ Methodology for Recursive Thinking
    1. 2.1 Template for designing recursive algorithms
    2. 2.2 Size of the problem
    3. 2.3 Base cases
    4. 2.4 Problem decomposition
    5. 2.5 Recursive cases, induction, and diagrams
      1. 2.5.1 Thinking recursively through diagrams
      2. 2.5.2 Concrete instances
      3. 2.5.3 Alternative notations
      4. 2.5.4 Procedures
      5. 2.5.5 Several subproblems
    6. 2.6 Testing
    7. 2.7 Exercises
  12. Chapter 3 ▪ Runtime Analysis of Recursive Algorithms
    1. 3.1 Mathematical preliminaries
      1. 3.1.1 Powers and logarithms
      2. 3.1.2 Binomial coefficients
      3. 3.1.3 Limits and L’Hopital’s rule
      4. 3.1.4 Sums and products
      5. 3.1.5 Floors and ceilings
      6. 3.1.6 Trigonometry
      7. 3.1.7 Vectors and matrices
    2. 3.2 Computational time complexity
      1. 3.2.1 Order of growth of functions
      2. 3.2.2 Asymptotic notation
    3. 3.3 Recurrence relations
      1. 3.3.1 Expansion method
      2. 3.3.2 General method for solving difference equations
    4. 3.4 Exercises
  13. Chapter 4 ▪ Linear Recursion I: Basic Algorithms
    1. 4.1 Arithmetic operations
      1. 4.1.1 Power function
      2. 4.1.2 Slow addition
      3. 4.1.3 Double sum
    2. 4.2 Base conversion
      1. 4.2.1 Binary representation of a nonnegative integer
      2. 4.2.2 Decimal to base b conversion
    3. 4.3 Strings
      1. 4.3.1 Reversing a string
      2. 4.3.2 Is a string a palindrome?
    4. 4.4 Additional problems
      1. 4.4.1 Selection sort
      2. 4.4.2 Horner’s method for evaluating polynomials
      3. 4.4.3 A row of Pascal’s triangle
      4. 4.4.4 Ladder of resistors
    5. 4.5 Exercises
  14. Chapter 5 ▪ Linear Recursion II: Tail Recursion
    1. 5.1 Boolean functions
      1. 5.1.1 Does a nonnegative integer contain a particular digit?
      2. 5.1.2 Equal strings?
    2. 5.2 Searching algorithms for lists
      1. 5.2.1 Linear search
      2. 5.2.2 Binary search in a sorted list
    3. 5.3 Binary search trees
      1. 5.3.1 Searching for an item
      2. 5.3.2 Inserting an item
    4. 5.4 Partitioning schemes
      1. 5.4.1 Basic partitioning scheme
      2. 5.4.2 Hoare’s partitioning method
    5. 5.5 The quickselect algorithm
    6. 5.6 Bisection algorithm for root finding
    7. 5.7 The woodcutter problem
    8. 5.8 Euclid’s algorithm
    9. 5.9 Exercises
  15. Chapter 6 ▪ Multiple Recursion I: Divide and Conquer
    1. 6.1 Is a list sorted in ascending order?
    2. 6.2 Sorting
      1. 6.2.1 The merge sort algorithm
      2. 6.2.2 The quicksort algorithm
    3. 6.3 Majority element in a list
    4. 6.4 Fast integer multiplication
    5. 6.5 Matrix multiplication
      1. 6.5.1 Divide and conquer matrix multiplication
      2. 6.5.2 Strassen’s matrix multiplication algorithm
    6. 6.6 The Tromino Tiling Problem
    7. 6.7 The skyline problem
    8. 6.8 Exercises
  16. Chapter 7 ▪ Multiple Recursion II: Puzzles, Fractals, and More...
    1. 7.1 Swamp traversal
    2. 7.2 Towers of Hanoi
    3. 7.3 Tree traversals
      1. 7.3.1 Inorder traversal
      2. 7.3.2 Preorder and postorder traversals
    4. 7.4 Longest palindrome substring
    5. 7.5 Fractals
      1. 7.5.1 Koch snowflake
      2. 7.5.2 Sierpiński’s carpet
    6. 7.6 Exercises
  17. Chapter 8 ▪ Counting Problems
    1. 8.1 Permutations
    2. 8.2 Variations with repetition
    3. 8.3 Combinations
    4. 8.4 Staircase climbing
    5. 8.5 Manhattan paths
    6. 8.6 Convex polygon triangulations
    7. 8.7 Circle pyramids
    8. 8.8 Exercises
  18. Chapter 9 ▪ Mutual Recursion
    1. 9.1 Parity of a number
    2. 9.2 Multiplayer games
    3. 9.3 Rabbit population growth
      1. 9.3.1 Adult and baby rabbit pairs
      2. 9.3.2 Rabbit family tree
    4. 9.4 Water treatment plants puzzle
      1. 9.4.1 Water flow between cities
      2. 9.4.2 Water discharge at each city
    5. 9.5 Cyclic towers of Hanoi
    6. 9.6 Grammars and recursive descent parsers
      1. 9.6.1 Tokenization of the input string
      2. 9.6.2 Recursive descent parser
    7. 9.7 Exercises
    8. Chapter 10 ▪ Program Execution
    9. 10.1 Control flow between subroutines
    10. 10.2 Recursion trees
      1. 10.2.1 Runtime analysis
    11. 10.3 The program stack
      1. 10.3.1 Stack frames
      2. 10.3.2 Stack traces
      3. 10.3.3 Computational space complexity
      4. 10.3.4 Maximum recursion depth and stack overflow errors
      5. 10.3.5 Recursion as an alternative to a stack data structure
    12. 10.4 Memoization and dynamic programming
      1. 10.4.1 Memoization
      2. 10.4.2 Dependency graph and dynamic programming
    13. 10.5 Exercises
  19. Chapter 11 ▪ Tail Recursion Revisited and Nested Recursion
    1. 11.1 Tail recursion vs. iteration
    2. 11.2 Tail recursion by thinking iteratively
      1. 11.2.1 Factorial
      2. 11.2.2 Decimal to base b conversion
    3. 11.3 Nested recursion
      1. 11.3.1 The Ackermann function
      2. 11.3.2 The McCarthy 91 function
      3. 11.3.3 The digital root
    4. 11.4 Tail and nested recursion through function generalization
      1. 11.4.1 Factorial
      2. 11.4.2 Decimal to base b conversion
    5. 11.5 Exercises
  20. Chapter 12 ▪ Multiple Recursion III: Backtracking
    1. 12.1 Introduction
      1. 12.1.1 Partial and complete solutions
      2. 12.1.2 Recursive structure
    2. 12.2 Generating combinatorial entities
      1. 12.2.1 Subsets
      2. 12.2.2 Permutations
    3. 12.3 The n-queens problem
      1. 12.3.1 Finding every solution
      2. 12.3.2 Finding one solution
    4. 12.4 Subset sum problem
    5. 12.5 Path through a maze
    6. 12.6 The sudoku puzzle
    7. 12.7 0-1 knapsack problem
      1. 12.7.1 Standard backtracking algorithm
      2. 12.7.2 Branch and bound algorithm
    8. 12.8 Exercises
  21. Further reading
  22. Index

Product information

  • Title: Introduction to Recursive Programming
  • Author(s): Manuel Rubio-Sanchez
  • Release date: October 2017
  • Publisher(s): CRC Press
  • ISBN: 9781351647175