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?

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.

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.

T

-- 
Leather is waterproof.  Ever see a cow with an umbrella?

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

H. S. Teoh:

> Also, this is a pretty poor algorithm for generating the Fibonacci series,

I know, but you must do what the tasks asks you:

http://rosettacode.org/wiki/Anonymous_recursion

Bye,
bearophile

On Fri, Aug 30, 2013 at 01:37:39AM +0200, bearophile wrote:
> H. S. Teoh:
> 
> >Also, this is a pretty poor algorithm for generating the Fibonacci series,
> 
> I know, but you must do what the tasks asks you:
> 
> http://rosettacode.org/wiki/Anonymous_recursion
[...]

OK I see.

I wish we could reeducate people that recursive Fibonacci algorithms are Bad(tm). :) There are better examples of recursion that don't have poor performance characteristics, or where no better alternative exists. Like parsing expression trees, for example (even though the parser can be recursive, it is only linear in the size of the input, so it's not bad).


T

-- 
I think the conspiracy theorists are out to get us...

On 08/29/2013 04:37 PM, bearophile wrote:

> H. S. Teoh:
>
>> Also, this is a pretty poor algorithm for generating the Fibonacci
>> series,
>
> I know, but you must do what the tasks asks you:
>
> http://rosettacode.org/wiki/Anonymous_recursion
>
> Bye,
> bearophile

Hm... Like some of the other language implementations, D's is not correct. There is a misunderstanding. Note that they say "which checks for a negative argument before doing the actual recursion."

The problem that is described is this case (note that the parameter is negative to make the problem meaningful):

// Actual recursive function
int fib_R(int n) pure nothrow {
    // Please ignore the algorithmic complexity issue. :)
    return (n < 2) ? n : fib_R(n - 1) + fib_R(n - 2);
}

// The non-recursive API function that calls the recursive one
int fib(int n) pure {
    enforce(n >= 0);
    return fib_R(n);
}

So the problem is asking for a solution for the problem of having to write two separate functions.

Ali

On Thursday, 29 August 2013 at 22:01:38 UTC, H. S. Teoh wrote:
> That's clever, but I'm not sure I understand the bit about anonymous functions? You don't need anonymous functions to have recursion.

Sorry, that came out all wrong. What I meant was that it's neat to be able to do anonymous recursion without having to resort to tricks like the Y-Combinator. However, after some fiddling, it seems that this is actually not usable with anonymous functions, or at least, I couldn't find a way to do it.

On 08/29/2013 08:53 PM, Meta wrote:

> However, after some fiddling, it seems that this is actually not usable with
> anonymous functions, or at least, I couldn't find a way to do it.

Borrowing the "self" trick from the existing solution, the following satisfies all of the requirements:

int fib(int arg) pure {
    enforce(arg >= 0);

    return function int (int n) pure nothrow {
        auto self = __traits(parent, {});
        return (n < 2) ? n : self(n - 1) + self(n - 2);
    }(arg);
}

Ali

On 30-8-2013 0:40, H. S. Teoh wrote:
(...)
> 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.
>
(...)

http://www.wolframalpha.com/input/?i=fib(100)


void main() {
    import std.bigint, std.range;
    BigInt fib(in uint fibN) pure {
        return recurrence!((a,n) => a[n-2] + a[n-1])(BigInt(1), BigInt(1))
            .drop(fibN-1)
            .front;
    }
    assert(fib(100) == BigInt("354_224_848_179_261_915_075"));
}


nice