Follow

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 

@Absinthe

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;

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.