## digitalmars.D.learn - Code from a Rosetta Code Task

• Meta (9/9) Aug 29 2013 uint fib(in uint n) pure nothrow {
• Robik (2/12) Aug 29 2013 {} in this case is just empty delegate function.
• H. S. Teoh (10/23) Aug 29 2013 That's clever, but I'm not sure I understand the bit about anonymous
• bearophile (5/7) Aug 29 2013 I know, but you must do what the tasks asks you:
• Meta (6/9) Aug 29 2013 Sorry, that came out all wrong. What I meant was that it's neat
• H. S. Teoh (34/56) Aug 29 2013 [...]
```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?
```
Aug 29 2013
```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.
```
Aug 29 2013
```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?
```
Aug 29 2013
```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
```
Aug 29 2013
```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...
```
Aug 29 2013    =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
```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
```
Aug 29 2013
```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.
```
Aug 29 2013
```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
```
Aug 29 2013
```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
```
Aug 29 2013
```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
```
Aug 30 2013