Recursive Functions

Recursion Defined | Uses of Recursion | Recursive Functions | The Novel

What is a Function?

In mathematics, a function describes a relationship between two things. For example, there is a function that relates the weight of a chicken to its cooking time. (My mother taught me that function is 20 minutes per pound plus an extra twenty minutes.)

Function Notation

Mathematicians use various ways to represent functions. One of the most useful was devised by Euler. In Euler's notation, the time taken to cook a chicken depends on the weight of the chicken, so we could say

f(w) = 20 * w + 20 where w is the weight of the chicken in pounds

This function converts Fahrenheit to centigrade

c(x) = (x-32) * 5/9

and this one converts it back again

f(x) = x *9/5 +32

Recursive Functions

You can form recursive functions, functions that call themselves, quite easily.

For example: f(x) = 1 + f(x-1)

You have to be careful, of course, the above function calls itself for ever. It’s a little like the meaning of the recursive acronym, GNU: GNU’s Not Unix, or (GNU’s Not Unix)’s Not Unix. Or ((GNU’s Not Unix)’s Not Unix)’s Not Unix. Or...

Recursive functions are only usually useful if they have an end. We can define and ending quite easily; in the example above we could say for example, f(0) = 0.

f(1) = 1+ f(0) =1

f(2) = 1 + f(1) = 2

f(3) = 1 + f(2) = 3

Which is not very interesting...

Here's another function

f(x) = f(x-1) + f(x-2); f(0) = 1, f(1) =1

f(0) = 1

f(1) = 1

f(2) = 2

f(3) = 3

f(4) = 5

f(5) = 8

f(6) = 13

This is the Fibonnacci sequence which describes everything from the way rabbits breed to the pattern on pine cones.

The next function comes from the book Godel Escher Bach, by Douglas Hofstadter, a book which contains all manner of information about recursion and much, much more.

The Q function is defined as

Q(n) =Q(n - Q(n-1))+ Q(n-Q(n-2)) for n>2

Q(1) = Q(2) = 1

Here are the first few terms: (Click here to see the first few hundred)

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, ...

You work out the next term as follows

1) Look at the last term you found, in this case 8, and then count that many places back from the three dots to get the number 3

2) Repeat the process with the second from last term, 6, to get the number 5

3) Add together 3 and 5 to get the next term, 8.

This is similar to the Fibonacci sequence, except the results are chaotic. After a relatively orderly start, there seems to be no logic to the sequence produced. There would seem to be no way of predicting the next term, except of course by using the deceptively simple recursive function above.

Recursion Defined | Uses of Recursion | Recursive Functions | The Novel