TABLE OF CONTENTS Some very important and classical problems in mathematics and computer science are defined, or have solutions in terms of recursive definitions. A function is defined using recursion if in its definition, it makes calls to itself. This programming paradigm is easily implemented in Mathematica in a manner that is both natural and quite efficient. In fact, many of the built-in operations of Mathematica could be written in Mathematica itself using recursion. In this chapter, we will present many examples of recursion and explain how recursive functions are written.
Recursive definitions of mathematical quantities were used by mathematicians for centuries before computers even existed. One famous example is the definition of a special sequence of numbers first studied by the thirteenth-century Italian mathematician Leonardo Fibonacci. The Fibonacci numbers have since been studied extensively, finding application in many areas; see (Knuth 1997) for a detailed discussion.
The Fibonacci numbers are obtained as follows: write down two 1s, then continue writing numbers computed by adding the last two numbers you have written down.
The simplest way to define these numbers is with recursion.
If we think of this sequence as a function, we would just change this to a functional definition.
In this form, we can translate the definition directly into Mathematica.
<i class="emphasis">In[1]:=</i> <b class="bold">F[1] = 1;</b> <b class="bold">F[2] = 1;</b> ...
