Recursive Functions and the true meaning of Zimaths

by Tawanda Gwena

Functions? Again! Sorry, but that's the main ingredient of mathematics. But today, instead of our standard plain functions, we do the recursive functions, definitely a lot more flavour in them.

First the word recursive. In general usage it means going back to oneself, a bit like a dog chasing its own tail, or like the story on our cover is a story about itself. Now in mathematics it means a function defined in terms of itself.

Let's try doing that. The easiest case is f(x)=f(x). This leads us nowhere, as every possible function satisfies that relation, e.g. sin(x)=sin(x). A less trivial one we now introduce is defined by two relations. They are f(0)=0 and f(n)=n+f(n-1). The first relation is there as a blocker, otherwise we might go off to negative infinity, because we do not know when to stop. As a first exercise we work out f(4):

	f(4)	=	4+f(3)
		=	4+3+f(2)
		=	4+3+2+f(1)
		=	4+3+2+1+f(0)
		=	4+3+2+1+0
		=	10

This turns out to be just the function f(n)=n(n+1)/2. Not too interesting because there is a simple formula to give you the value easily.

However a less trivial case is your popular factorial function. This is defined by g(0)=1 and g(n)=n.g(n-1). Now the idea of recursive functions becomes useful. To find g(5) (which is also written 5!) we carry out the working as follows

	g(5)	=	5g(4)
		=	5.4g(3)
		=	5.4.3g(2)
		=	5.4.3.2g(1)
		=	5.4.3.2.1g(0)
		=	5.4.3.2.1.1
		=	120

Another function defined recursively is the Fibonacci Sequence. This is defined as F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). In words, the next number is the sum of the previous two. This one, unlike the previous ones needs two initial values instead of one. So the first few values of the function are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

Immediately we run into the problems of such recursive functions.
Problem one : the speed of calculating. If we want to find g(100) we have to find g(99), then g(98), ... g(1). Even on an ultrafast supercomputer such things as speed do matter. That is why computer scientists still exist.
Problem two : What about the value of g(1/2)?

For the first problem we could try what we did for f(x), change it into a function independent of the previous values. The function x(x+1)/2 is called the closed form of the function f(x). The closed form of the Fibonacci function is

Incidentally, the quantity (root5 + 1)/2 is called the Golden ratio. Pretty, and it works. For the factorial the closed form is just plain complicated, usually going by the name gamma function, written as

For the second problem we could argue that the question might not make sense, such as choosing half a thing when working with permutations and combinations. But sometimes it is useful to know such things (maths people tend to work with otherwise insane looking things, ever heard of -2 loaves of bread?). The function f(x) is now defined for all numbers because of its closed form, so is the Fibonacci function and the factorial function. Some interesting things come out of this such as this beautiful result

Back to the title of the article (or is it the title of the title?), what does Zimaths really mean. Several of you readers, I assume, think it means Zimbabwe Mathematics or such similar approximations, but you are all wrong. It actually stands for ``Zimaths is maths applicable to high schools'', which can expand to ``(Zimaths is maths applicable to high schools) is (maths applicable to high schools) applicable to high schools'', which can expand to... ``(Zimaths is maths applicable to high schools) is (maths applicable to high schools) applicable to high schools) is ((maths applicable to high schools) applicable to high schools) applicable to high schools". You get the idea. You now have both the meaning of "maths" and "Zimaths", two bird with one stone.

I lie. Actually it stands for Zimaths is maths and Tawanda has spoken.

Humble, ain't I?