Recursion is a fundamental, advanced construct for program design. In this section we introduce recursion on a three-folded basis. Firstly, we briefly define recursion and identify its main elements. Secondly, we show alternative ways of explaining recursion by an instructor. Finally, we present the most common students’ errors on understanding recursion.
Recursion
A recursive definition defines something in terms of itself. This property is strongly discouraged for definitions in general, and dictionaries try to avoid it. Recursion can be direct but also indirect, being this form of recursion harder to recognize. For instance, the definition of a word in a dictionary depends on other words, and this dependence chain is potentially infinite. It is not rare that, following a chain of dependencies, the definition of the original word depends on itself.
However, in mathematics and computer programming, recursion is a valuable tool for definitions and for problem solving. Some recursive definitions are surprisingly clear. For instance, the factorial of a natural number n can be symbolized as n!, meaning that n!=n·(n-1)·…·1. An alternative, recursive definition follows:
The term at the left-hand side is called the definition head. A recursive definition consists of two or more cases, at its right-hand side. A case for which the concept being defined does not depend on itself is called a base case. A case which depends on the concept being defined is called a recursive case; the recursive occurrence of the term defined is called a recursive call.
Many additional, typical examples exist. For instance the Fibonacci numbers are typically defined as follows:
As in the dictionary example, recursion can be indirect. The following is an alternative, mutually recursive definition of the Fibonacci numbers:
There are many particular cases of recursion with different features: lineal vs. multiple recursion, final vs. non-final (lineal) recursion, direct vs. mutual recursion, etc. We do not deepen into the definition and explanation of recursion, as it is common in programming or mathematical logic textbooks. However, we summarize the constraints a well-formed recursive definition must respect:
- •
It must contain at least one base case and one recursive case.
- •
The term used in any recursive call must be smaller that the term used at the definition head. Otherwise, the computation does not terminate. For instance, the recursive call in the factorial function is applied to the term n-1, which is smaller than n.
- •
Some definitions only make sense if we assume that the variables or parameters at the definition head satisfy some condition (called the precondition). For instance, the factorial function is only valid for natural numbers, i.e. for n≥0. Any recursive call must make sure that all the recursive calls satisfy this precondition, provided the condition of the case is satisfied by the definition variables.