To run the programs referred to below you will need access to a C compiler (for factorial and ackermann) and to a suitable interpreter, e.g. GhostScript/Ghostview, for the Fibonacci-related PostScript examples.
We start with the classic example of "factorial" : Note that "factorial" is not tail recursive, because there is a `deferred multiply' in each stack frame, which gets performed as the stack frames are popped.
"factorial" coded recursively and iteratively in C
We now turn to the Fibonacci sequence: F(n+1) = F(n) + F(n-1)
Note that there will be a lot of unnecessarily repeated calculations if we program recursively in
the above form. One way around this is to have the value of F(n-1) available before F(n) is
calculated. PostScript makes this easy because the stack can be explicitly manipulated so as to
carry around F(n) and F(n-1) at the top of the stack as is done here:
PostScript program to print out Fibonacci values on the graphic display screen
Fibonacci accumulates the answer for F(n+1) in the final stack frame. Nothing remains to be done in the underlying stack frames, so this function is tail recursive and a smart compiler/interpreter is free to do `tail optimisation' and return directly to the main program.
Next we show a logarithmic spiral approximated as a sequence of linked semi-circular arcs inscribed in Fibonacci-sized boxes.
Finally here is a version that tries to annotate each box with its Fibonacci number. It is left as an exercise to improve the automated pointsize and placement of these numbers ....
Fibonnaci spiral with annotated boxes
A C program to calculate Ackermann's function is given here. This function grows very quickly indeed (`super-exponentially') even for modest values of its two arguments. You will find, if you run the program, that ack(4,1) takes a few minutes (or maybe even a few seconds if you have a superfast computer) to calculate and its value is 65533. But computing the value of ack(4,2) takes much longer than that. And it's not -- as you might guess -- 65,533 times as long but 265533 times as long!
Ackermann is an example of a function that is recursive, but not primitive recursive, which means that unlike fibonacci and factorial it can't be `de-recursed' and turned into for loops. However, if you examine the recursive calling structure carefully, you will see that recursive sub-calls steadily decrease the values of its two arguments until they reach zero. This enables us to reason about the program and to say that given enough memory, massively extended precision on integer arithmetic and almost infinite patience it would eventually deliver an integer answer.
Therefore, although you won't be around long enough to read some of the answers it is not an uncomputable function. There is a perfectly good algorithm for doing the calculation and it provably terminates (see previous paragraph).