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 an important problem-solving skill that is considered to be one of the most difficult topics to master by CS1/2 students. This book helps students assimilate its fundamental concepts by analyzing a large number of problems of different nature, covering classical problems found in the literature, as well as richer related problems.

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