Recursive functions

Summary: Recursive functions describe the output value of a function in terms of other output values of the function.

Recursive functions, by iterating certain defined procedures, can provide a succinct way of describing a multistep algorithm or calculating an intricately defined number. Long used in mathematical problem solving, recursive functions became indispensable with the advent of computer programming, as they provide a method of concisely encoding repetitive processes.

Many mathematicians explored ideas related to recursive functions, including nineteenth-century mathematicians Richard Dedekind and Giuseppe Peano. In the early and middle part of the twentieth century, the development of recursion theory is tied to questions about computability and the foundations of mathematics.

Alan Turing and Kurt Gödel preferred the term “computable” over “recursive” but the latter terminology has been common since the 1930s. Mathematician Rosza Peter is noted as a founding mother of recursion theory who, along with other researchers like Alonzo Church, Gödel, Jacques Herbrand, Stephen Keene, Andrey Markov, Emil Post, and Turing, developed the area. In the twenty-first century, high school students explore recursive functions in mathematics classes, and college students apply ideas from a related topic, the principle of mathematical induction, in proofs.

What Is a Recursive Function?

Recursive functions describe the output value of the function in terms of other output values of the function, usually for smaller input values. In this case, to avoid an infinite recursion loop, one must explicitly specify at least one specific output value. For instance, one could say that the value of a certain function at some counting number is equal to that input value multiplied by the value of the function at the next smaller input value—algebraically,

f(n) = n × f (n − 1).

Then one would need to define a specific value of the function. Say, at 0, the function is equal to 1; that is, f(0)=1. This specification effectively defines the value of f at each whole number, although it may require a few steps to get there. For example, if one wanted to determine f(3), one would first see that

f(3) = 3 × f(2).

However, f(2)=2×f(1)=f(1), and f(1)=1×f(0)=1.

So, working backwards, f(1)=1, f(2)=2, and f(3)=6. This example, known as the “factorial function,” plays a key role in combinatorics and probability, where f(n) is written n! and equals the number of ways to arrange n objects in an ordered list.

Early Uses of Recursion

Dating from ancient Egypt (c. 1650 b.c.e.), Problem 79 of the Rhind (or Ahmes) Papyrus describes an estate containing 7 houses, 49 cats, 343 mice, 2401 heads of wheat, and 16,807 hekat measures (of grain) and gives the total of all these numbers as 19,607. The list contains powers of the number 7. In 1907, Moritz Cantor interpreted this list as a possible precursor of a modern nursery rhyme. He proposed: an estate has 7 houses; each house has 7 cats; each cat can catch 7 mice; each mouse eats 7 heads of wheat; and each head of wheat produces 7 hekats of grain. What is the total of these numbers? Or, for a different question, because of all the mouse-eating cats in all the houses, how many hekats of grain were saved on the estate? This calls to mind the familiar “As I was going to St. Ives” nursery rhyme, with its final question, “. . . kits, cats, sacks, wives, / How many were going to St. Ives?” [The answer is one.]

The Rhind Papyrus problem can be posed as a simple recursive function via iteration in which the output of a function is used as the same function’s next input value and this process is repeated a preordained number of times. In this case, one could use the function that multiplies the input value by 7: f(x)=7x. To obtain the number of houses, input the number of estates into the function, obtaining f(1)=7. Then, to determine the number of cats, input the number of houses into the function: f(7)=49.

Thinking recursively, this is calculating f(f(1)). The number of mice is then

f(f(f(1)))=f(f(7))=f(49)=343, and so on.

Simply put, to obtain the next term in the sequence, perform the function on the previous term.

A similar problem appeared in Leonardo Fibonacci’s 1202 work, Liber Abaci. In the same work, he also posed another famous problem to determine how many pairs of rabbits there would be at the end of 12 months, starting with one mature breeding pair and assuming that each mature pair breeds one pair of offspring each month and that the new offspring must wait one month until they become a mature breeding pair. The sequence of the total numbers of pairs of rabbits in each month proceeds 1, 1, 2, 3, 5, 8, 13,… . Fibonacci noted that the number of rabbit pairs, from the third month on, is equal to the sum of the number of pairs in each of the two previous months. Today, this sequence is called the “Fibonacci sequence” and its entries are called “Fibonacci numbers.”

Often, the Fibonacci sequence is defined as a recursive function, this time with two starting values: f(1)=1 and f(2)=1. Then, the Fibonacci sequence is

f(n = f(n + 1) + f(n − 2)

for all positive integer values of n greater than 2. The Fibonacci sequence has appeared in botany, specifically in phyllotaxis, the method of leaf formation. The number of spirals in a sunflower head, a pineapple, or a pinecone are often Fibonacci numbers.

Recursion in Computer Programming

Recursive functions play a key role in computer programming, as they allow the programmer to encode a possibly lengthy algorithm in a relatively short number of steps. For instance, to calculate the factorial function mentioned above using a computer, the “non-recursive” approach could be to store several values of the function in memory and return those values when needed.

This approach could take an unlimited amount of memory, because each value of the function would require its own memory space. The recursive approach is simpler—the factorial of a number can be encoded in two statements, thus allowing the computer to calculate the factorial function for any positive integer efficiently. Some sample “pseudocode” follows:

Function Factorial(input):

If input = 0, then Factorial(0) = 1;

Else, Factorial(n) = n × Factorial(n – 1);

End Factorial.

Some computer games require players to demonstrate recursive programming skills. For example, Robozzle asks the player to program a spaceship to collect all the stars on the screen but to do so with a limited number of commands. The Tower of Hanoi puzzle, marketed by French mathematician Edouard Lucas in 1883, is often used as an example of recursion in classrooms. Often, recursion is necessary to complete the task. For instance, to move the rocket ship forward indefinitely using recursion, one could simply enter a command to move the ship forward and a command to go back to the beginning of the program, which would then move the ship forward and then go back to the beginning of the program again and again. It is often surprising to see the intricate patterns that can be programmed relatively succinctly using recursive functions.

Bibliography

Hayashi, Elmer. “Fibonacci Numbers, Recursion, Complexity, and Induction Proofs.” College Mathematics Journal 23, no. 5 (1992).

Lannin, John. “Developing Mathematical Power by Using Explicit and Recursive Reasoning.” Mathematics Teacher 98, no. 4 (2004).

Morris, Edie, and Leon Harkleroad. “Rózsa Péter: Recursive Function Theory’s Founding Mother.” Mathematical Intelligencer 12, no. 1 (1990).

Smith, Robert T., and Roland B. Minton. Calculus: Early Transcendental Functions. New York: McGraw-Hill Science, 2006.

Soare, Robert. “Computability and Recursion.” Bulletin of Symbolic Logic 2 (1996). http://www.people.cs.uchicago.edu/~soare/History/compute.pdf.