Code from a Rosetta Code Task

[H. S. Teoh]

On Thu, Aug 29, 2013 at 03:00:09PM -0700, H. S. Teoh wrote:
> On Thu, Aug 29, 2013 at 11:00:49PM +0200, Robik wrote:
> > On Thursday, 29 August 2013 at 18:57:58 UTC, Meta wrote:
> > >uint fib(in uint n) pure nothrow {
> > >    immutable self = &__traits(parent, {});
> > >    return (n < 2) ? n : self(n - 1) + self(n - 2);
> > >}
> > >
> > >I came across this while browsing Rosetta Code. It's really cool
> > >how you can do recursion without anonymous functions (and this
> > >will actually not work if you make fib a delegate). However, I'm
> > >confused about the __traits(parent, {}) part, specifically , the
> > >{} passed to parent. Does {} just mean the outer scope?
> > 
> > {} in this case is just empty delegate function.
> 
> That's clever, but I'm not sure I understand the bit about anonymous
> functions? You don't need anonymous functions to have recursion.
> 
> Also, this is a pretty poor algorithm for generating the Fibonacci
> series, as it has exponential time complexity in addition to linear
> space complexity. It's even worse than the recursive factorial function,
> which at least doesn't have exponential time complexity.
[...]

A far better implementation is to use std.range.recurrence:

	uint fib(in uint n) pure nothrow {
		return recurrence!((a,n) => a[n-2] + a[n-1])(1, 1)
			.drop(n-1)
			.front;
	}

This implementation has linear time complexity and constant space
complexity (vs. exponential time complexity vs. linear space complexity
in the original).

To illustrate how bad it is, I wrote a program that calls fib(50) for
each of the above implementations, and observed how long it takes each
one to return an answer. The version using recurrence completes in a
fraction of a second, the second takes two *minutes*. I bumped it up to
fib(100), and the recurrence version still runs under a fraction of a
second, but I ran out of patience waiting for the second one.

I would like to promote the use of std.range.recurrence instead of
monstrous exponential-time algorithms like the recursive fib(), or the
horrible linear-space recursive factorial. The latter can also be
reduced to linear time complexity + constant space complexity thanks to
std.range.recurrence:

	uint factorial(in uint n) pure nothrow {
		return recurrence!((a,n) => n * a[n-1])(1)
			.drop(n-1)
			.front;
	}

*This* should be the selling point of D: the fact that you can write
nice mathematical recurrences like that and still have it generate
highly-efficient code, not the fact that you can do some clever tricks
with __traits but end up with horrible exponential-time algorithms.


T

-- 
The irony is that Bill Gates claims to be making a stable operating system and Linus Torvalds claims to be trying to take over the world. -- Anonymous