Recursive Function
A recursive function is a function whose domain is generated by previous values of the function. A recursive function is typically defined by giving some initial value and then stating a recursion rule which defines how a given function value depends on a previous value, or values, of the function. For example, here is a recursive function: f(0) = 2 and f(n) = f(n - 1) + 3 where n is a natural number (positive integer). This function starts with an initial value of 2, after which each new function value is generated by adding 3 to the function value preceding it. So this function will generate the set {2,5,8,11,...}. Another example is: f(0) = 1 and f(n) = nf(n - 1), where n is a natural number. This recursive function generates the set {1,1,2,6,24,120,...} and is called the factorial function. It is usually defined using the factorial symbol (!) as follows: 0! = 1 and n! = n(n - 1)!, where n is a natural number. This is just one of many important mathematical functions which are defined recursively.
Recursive functions are often used in modeling real world processes such as the accumulation of money in a bank account, creating tables for paying off a loan over time, population growth, radioactive decay, and many others. Consider a $1000 certificate of deposit that is to earn 6% interest compounded annually. This means that $1000 is deposited initially and at the end of one year 6% of $1000 or $60 interest is added to the original $1000. At the end of the second year 6% of $1060 or $63.60 is added to the $1060 for a total of $1123.60, and this process repeats itself over and over for the life of the certificate. Processes that repeat themselves using previous values of the process are good candidates for modeling with recursive functions. In this case, let us define A(n) to be the amount in the account after n years and A(0) will be the initial amount deposited. Then a recursive function for this process may be defined as: A(0) = 1000 and A(n) = A(n - 1) + .06A(n - 1) for n = 1, 2, 3,.... Note that an equivalent and slightly simpler form for A(n) is 1.06A(n - 1), but the version originally given more clearly demonstrates the process which is being repeated again and again. Let us say that the term of this certificate is 5 years. Then with the recursive function defined we can calculate how much money is in the account at the end of each year: A(1) = $1060, A(2) = $1123.60, A(3) = $1191.02, A(4) = $1262.48, and A(5) = $1338.23. Most modern graphing calculators have a "sequence" mode that allows the user to input an initial value and a recursion formula to generate tables of values for recursive functions. Most computer languages either have built-in recursion capability or allow the programmer to create "loops" in which a function calls itself repeatedly using previous values of the function. Real world systems that change in discrete time units are called discrete dynamical systems. Such systems are frequently modeled by recursive functions, which, in this context, are called finite difference equations to emphasize that they are the discrete counterparts of the continuous differential equations of the calculus. One can think of a differential equation as resulting from taking the limit of a difference equation as the time intervals between each step approach 0.
So far we have looked only at recursion functions in which each new value of the function depends upon only one previous value, namely, the one immediately preceding it. Such functions are the simplest type and are sometimes called "first order" recursive functions; but it is also possible to define higher order recursive functions. In fact, a very famous sequence can be generated by a second order recursive function as follows: f(0) = 1, f(1) = 1, and f(n) = f(n - 1) + f(n - 2), where n is a natural number. The famous sequence so generated is {1,1,2,3,5,8,13,21,34,...}, the so-called Fibonacci sequence named for Leonardo of Pisa (c.1170-1240) who had the nickname Fibonacci. Notice that for a second order recursive function we need two "initial" values because the function has to "call" two previous values of itself on each iteration. This is true in general: for an nth order recursive function, we need n "initial" values.
Recursion is not merely an effective technique for modeling certain natural processes; it is also indispensable in the logical development of the natural number system. The Italian mathematician Giuseppe Peano (1858-1932) showed how to generate all natural numbers from a set of simple axioms and recursion. He started with axioms asserting that 0 is a number; that a recursive function s, called "the successor of" exists; and that the successor of any number is a number. Let s(k)=the successor of the number k. Then starting with 0, we recursively obtain s(0), the successor of 0; s(s(0)), the successor of the successor of 0; s(s(s(0))), the successor of the successor of the successor of 0; and so on. Now all of these successors are numbers because the successor of a number is a number. Furthermore, we can give these numbers names: s(0) we will call 1; s(s(0)) we will call 2; s(s(s(0))) we will call 3; and so on. Thus we may generate the natural numbers with this recursive process. Here we could define the recursive function as s(0) = 1 and s(n) = s(s(n - 1)).
This is the complete article, containing 918 words
(approx. 3 pages at 300 words per page).
