book

Introduction to Recursive Programming

Name: Introduction to Recursive Programming
Author: Manuel Rubio-Sanchez
ISBN: 9781351647175

by Manuel Rubio-Sanchez

October 2017

Beginner

451 pages

10h 33m

English

CRC Press

Read now

Unlock full access

Cover
Half Title
Title Page
Copyright Page
Table of Contents
Preface
List of Figures
List of Tables
List of Listings
Chapter 1 ▪ Basic Concepts of Recursive Programming
1.1 Recognizing recursion1.2 Problem decomposition1.3 Recursive code1.4 Induction1.4.1 Mathematical proofs by induction1.4.2 Recursive leap of faith1.4.3 Imperative vs. declarative programming1.5 Recursion vs. iteration1.6 Types of recursion1.6.1 Linear recursion1.6.2 Tail recursion1.6.3 Multiple recursion1.6.4 Mutual recursion1.6.5 Nested recursion1.7 Exercises

Chapter 2 ▪ Methodology for Recursive Thinking
2.1 Template for designing recursive algorithms2.2 Size of the problem2.3 Base cases2.4 Problem decomposition2.5 Recursive cases, induction, and diagrams2.5.1 Thinking recursively through diagrams2.5.2 Concrete instances2.5.3 Alternative notations2.5.4 Procedures2.5.5 Several subproblems2.6 Testing2.7 Exercises
Chapter 3 ▪ Runtime Analysis of Recursive Algorithms
3.1 Mathematical preliminaries3.1.1 Powers and logarithms3.1.2 Binomial coefficients3.1.3 Limits and L’Hopital’s rule3.1.4 Sums and products3.1.5 Floors and ceilings3.1.6 Trigonometry3.1.7 Vectors and matrices3.2 Computational time complexity3.2.1 Order of growth of functions3.2.2 Asymptotic notation3.3 Recurrence relations
3.3.1 Expansion method
3.3.2 General method for solving difference equations3.4 Exercises
Chapter 4 ▪ Linear Recursion I: Basic Algorithms
4.1 Arithmetic operations4.1.1 Power function4.1.2 Slow addition4.1.3 Double sum4.2 Base conversion4.2.1 Binary representation of a nonnegative integer4.2.2 Decimal to base b conversion4.3 Strings4.3.1 Reversing a string4.3.2 Is a string a palindrome?4.4 Additional problems4.4.1 Selection sort4.4.2 Horner’s method for evaluating polynomials4.4.3 A row of Pascal’s triangle4.4.4 Ladder of resistors4.5 Exercises
Chapter 5 ▪ Linear Recursion II: Tail Recursion
5.1 Boolean functions5.1.1 Does a nonnegative integer contain a particular digit?5.1.2 Equal strings?5.2 Searching algorithms for lists5.2.1 Linear search5.2.2 Binary search in a sorted list5.3 Binary search trees5.3.1 Searching for an item5.3.2 Inserting an item5.4 Partitioning schemes5.4.1 Basic partitioning scheme5.4.2 Hoare’s partitioning method5.5 The quickselect algorithm5.6 Bisection algorithm for root finding5.7 The woodcutter problem5.8 Euclid’s algorithm5.9 Exercises
Chapter 6 ▪ Multiple Recursion I: Divide and Conquer
6.1 Is a list sorted in ascending order?6.2 Sorting6.2.1 The merge sort algorithm6.2.2 The quicksort algorithm6.3 Majority element in a list6.4 Fast integer multiplication6.5 Matrix multiplication6.5.1 Divide and conquer matrix multiplication6.5.2 Strassen’s matrix multiplication algorithm6.6 The Tromino Tiling Problem6.7 The skyline problem6.8 Exercises
Chapter 7 ▪ Multiple Recursion II: Puzzles, Fractals, and More...
7.1 Swamp traversal7.2 Towers of Hanoi7.3 Tree traversals7.3.1 Inorder traversal7.3.2 Preorder and postorder traversals7.4 Longest palindrome substring7.5 Fractals7.5.1 Koch snowflake7.5.2 Sierpiński’s carpet7.6 Exercises
Chapter 8 ▪ Counting Problems
8.1 Permutations8.2 Variations with repetition8.3 Combinations8.4 Staircase climbing8.5 Manhattan paths8.6 Convex polygon triangulations8.7 Circle pyramids8.8 Exercises
Chapter 9 ▪ Mutual Recursion
9.1 Parity of a number9.2 Multiplayer games9.3 Rabbit population growth9.3.1 Adult and baby rabbit pairs9.3.2 Rabbit family tree9.4 Water treatment plants puzzle9.4.1 Water flow between cities9.4.2 Water discharge at each city9.5 Cyclic towers of Hanoi9.6 Grammars and recursive descent parsers9.6.1 Tokenization of the input string9.6.2 Recursive descent parser9.7 Exercises
Chapter 10 ▪ Program Execution
10.1 Control flow between subroutines10.2 Recursion trees10.2.1 Runtime analysis10.3 The program stack10.3.1 Stack frames10.3.2 Stack traces10.3.3 Computational space complexity10.3.4 Maximum recursion depth and stack overflow errors10.3.5 Recursion as an alternative to a stack data structure10.4 Memoization and dynamic programming10.4.1 Memoization10.4.2 Dependency graph and dynamic programming10.5 Exercises
Chapter 11 ▪ Tail Recursion Revisited and Nested Recursion
11.1 Tail recursion vs. iteration11.2 Tail recursion by thinking iteratively11.2.1 Factorial11.2.2 Decimal to base b conversion11.3 Nested recursion11.3.1 The Ackermann function11.3.2 The McCarthy 91 function11.3.3 The digital root11.4 Tail and nested recursion through function generalization11.4.1 Factorial11.4.2 Decimal to base b conversion11.5 Exercises
Chapter 12 ▪ Multiple Recursion III: Backtracking
12.1 Introduction12.1.1 Partial and complete solutions12.1.2 Recursive structure12.2 Generating combinatorial entities12.2.1 Subsets12.2.2 Permutations12.3 The n-queens problem12.3.1 Finding every solution12.3.2 Finding one solution12.4 Subset sum problem12.5 Path through a maze12.6 The sudoku puzzle12.7 0-1 knapsack problem12.7.1 Standard backtracking algorithm12.7.2 Branch and bound algorithm12.8 Exercises
Further reading
Index

Content preview from Introduction to Recursive Programming

The expansion method, also known as the “iteration” or “backward substitution” method, can be used primarily to solve recurrence relations whose recursive case contains one reference to the recursive function (in some cases it can be applied to recurrences where the recursive function appears several times in the recursive definitions). The idea consists of simplifying the recurrence relation progressively step by step, until noticing a general pattern at some i-th stage. Subsequently, the function can take concrete values by considering that the base case is reached at that i-th step. The following examples illustrate the procedure. Finally, Section 10.2.1 illustrates a related visual approach called the “tree method.” ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Hands-On Data Structures and Algorithms with Python - Second Edition

Publisher Resources

ISBN: 9781351647175

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Introduction to Recursive Programming

by Manuel Rubio-Sanchez

3.3.1 Expansion method

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.