Here is one I have been playing with.
Factorials and Fibonacci numbers are traditionally used as examples of recursive functions.
Let's see them done without recursion with reasonable timing.
Octave solution & discussion
Pretty straightforward. Might be possible to improve on the factorial one by counting factors, because computers can generally calculate x^n faster than just multiplying it out, so if you figure out that the answer would be 2^a * 3^b * 5^c... it could outpace the naive 1 * 2 * 3 * ... * n method.
That said, I tried such an approach and while it does scale better than linear, the upfront cost is high enough that the breakeven point is way past anything my computer can represent in floating point. So for practical use, this is what I'd put forward.
function term = fibonacci(index)
root = sqrt(5);
term = (((1 + root)/2).^index - ((1 - root)/2).^index) ./ root; end;
function number = factorial(argument)
number = ones(size(argument));
for factor = 1:max(argument)
number(argument >= factor) *= factor; end; end;
