Introduction to Recursive Programming

Manuel Rubio-Sanchez

• Publisher: CRC Press
• Year: 2017
• ISBN:
  9781351647175
• Edition: 1
• Topic: Informatica
• Subtopic: Programmazione di giochi

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.

CHAPTER 1

---

Basic Concepts of Recursive Programming

---

To iterate is human, to recurse divine.

—Laurence Peter Deutsch

RECURSION is a broad concept that is used in diverse disciplines such as mathematics, bioinformatics, or linguistics, and is even present in art or in nature. In the context of computer programming, recursion should be understood as a powerful problem-solving strategy that allows us to design simple, succinct, and elegant algorithms for solving computational problems. This chapter presents key terms and notation, and introduces fundamental concepts related to recursive programming and thinking that will be further developed throughout the book.

1.1 RECOGNIZING RECURSION

---

An entity or concept is said to be recursive when simpler or smaller self-similar instances form part of its constituents. Nature provides numerous examples where we can observe this property (see Figure 1.1). For instance, a branch of a tree can be understood as a stem, plus a set of smaller branches that emanate from it, which in turn contain other smaller branches, and so on, until reaching a bud, leaf, or flower. Blood vessels or rivers exhibit similar branching patterns, where the larger structure appears to contain instances of itself at smaller scales. Another related recursive example is a romanesco broccoli, where it is apparent that the individual florets resemble the entire plant. Other examples include mountain ranges, clouds, or animal skin patterns.

Figure 1.1 Examples of recursive entities.

Recursion also appears in art. A well-known example is the Droste effect, which consists of a picture appearing within itself. In theory the process could be repeated indefinitely, but naturally stops in practice when the smallest picture to be drawn is sufficiently small (for example, if it occupies a single pixel in a digital image). A computer-generated fractal is another type of recursive image. For instance, Sierpiński’s triangle is composed of three smaller identical triangles that are subsequently decomposed into yet smaller ones. Assuming that the process is infinitely repeated, each small triangle will exhibit the same structure as the original’s. Lastly, a classical example used to illustrate the concept of recursion is a collection of matryoshka dolls. In this craftwork each doll has a different size and can fit inside a larger one. Note that the recursive object is not a single hollow doll, but a full nested collection. Thus, when thinking recursively, a collection of dolls can be described as a single (largest) doll that contains a smaller collection of dolls.

While the recursive entities in the previous examples were clearly tangible, recursion also appears in a wide variety of abstract concepts. In this regard, recursion can be understood as the process of defining concepts by using the definition itself. Many mathematical formulas and definitions can be expressed this way. Clear explicit examples include sequences for which the n-th term is defined through some formula or procedure involving earlier terms. Consider the following recursive definition:

(1.1)

s n = s n - 1 + s n - 2 .

The formula states that a term in a sequence ( s n ) is simply the sum of the two previous terms ( s n - 1 and s n - 2 ). We can immediately observe that the formula is recursive, since the entity it defines, s, appears on both sides of the equation. Thus, the elements of the sequence are clearly defined in terms of themselves. Furthermore, note that the recursive formula in (1.1) does not describe a particular sequence, but an entire family of sequences in which a term is the sum of the two previous ones. In order to characterize a specific sequence we need to provide more information. In this case, it is enough to indicate any two terms in the sequence. Typically, the first two terms are used to define this type of sequence. For instance, if s 1 = s 2 = 1 the sequence is:

1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ,...