Recursion and Iteration Benchmarks needed

You could write some simple recursive functions vs iterative ones for different complexities of recursive functions

1. The factorial function
2. The Fibonacci series function
3. If you have the patience (directory tree parsing)


Just for a qualitative test on performance try this out. You can easilly modify the code I have given you to measure the time of each function over a number of tests.

The factorial function is easy to write so I left that to you. I would imagine that the performance of each of these would be comparable. Make sure you use a large integer for the sum because the number become big real fast.

You could optimise the iterative function if you like by splitting the while loop into two for loops to get rid of the if statement.

Have fun with it.

Edit: If you go for elegance though the recursive function wins

Well, those functions you have written don't implement the same algorithm.

A better recursive fib that implements the same algorithm as the iterative one:

int realfib(int n, int a, int b){   if(n<=0) return b;   return realfib(n-1,b,a+b);}int rfib(int n) {   return realfib(n-1,1,1);}

For tail recursive functions there probably is no performance difference when compiled with a good optimizing compiler.

Thanks for the replies. I've already created by own test, but the problem is that I'm required to have data from other people in order to compare my results.

Thanks,
Weastmann

Here's a random bit of info that may help you out. It's primarily about the space complexity of recursive procedures. I was actually planning to produce a full writeup about recursion vs iteration but I am just too sleepy right now. This also assumes you understand C's model of computation.

**

Every procedure call, recursive or not, has an 'activation record'.

The activation record has 3 primary purposes: to store the parameters (which explains the pass-by-value mechanism of C. A 'reference' can be given, which is really just a pointer to a location in the heap / value store), to store the frame pointer (identifies the location to 'return' to; this is the location of the previous frame), and the local variables of the procedure.

An advantage of the stack machine is that memory allocation is damn quick ... just a matter of building up the stack. And deallocation is literally just a jump (frame pointer) back to the previous frame.

Self tail recursive procedures can be easily optimized. Once we enter the procedure (and therefore an activation record has been constructed), we can avoid any additional activation records for the self tail-call. This is because the procedure overhead is a fixed size, and since the tail-call implies that there is no remaining computations, we have no concern for the data of the existing procedure call.

Factorial, for example:


The self tail call of fact_r can be optimized by the compiler to just modify the current activation record. Rather than create a new activation record, each self call would (in parallel):

set n = n - 1,
set c = c*n,
jump to stack ptr.

No allocations, no deallocations. A self tail call is just mutation and a jump.

For non-self tail recursive procedures, tail call optimization is a bit different. Two existing strategies are a) allocate all activation records on the heap, and let a GC clean them up, and b) allocate activation records on the stack until it becomes filled, and then spill over onto the heap. At first glance, the heap-allocating strategy of [a] seems to be ideal: it means that we have a uniform mechanism for tail-call optimization (basically: a series of tail calls should run in constant amortized space), and we have cheap continuations (a stack allows efficient downward continuations, but full-fledged continuations require expensive trampolining). Unfortunately, heap-allocating increases the overhead of all procedure calls (allocation is more expensive) and now we require a GC to clean house. The hybrid solution allows for fast frame allocation where possible, and still allows for TCO. The implementation of this is much more complicated.

Recursive procedures that do not contain tail-calls cannot be executed in constant space, unfortunately. This is because each non-tail-call has an implicit context ... the computation which will be evaluated when the call returns a value. The whole TCO business takes advantage of the fact that the context is the same for every recurse ... fact_r(4, 1) returns a value to some computation, therefore the tail call to fact_r(3, 4) would return a value to this same computation. Without tail calls, each procedure has a unique context.