## 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:
- H. S. Teoh (11/19) Aug 29 2013 [...]
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (19/26) Aug 29 2013 Hm... Like some of the other language implementations, D's is not
- Meta (6/9) Aug 29 2013 Sorry, that came out all wrong. What I meant was that it's neat
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (12/14) Aug 29 2013 Borrowing the "self" trick from the existing solution, the following
- H. S. Teoh (34/56) Aug 29 2013 [...]
- Jos van Uden (14/29) Aug 30 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: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?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

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:[...] 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...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

Aug 29 2013

On 08/29/2013 04:37 PM, bearophile wrote:H. S. Teoh: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. AliAlso, 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 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 notusable withanonymous 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:[...] 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. -- AnonymousOn Thursday, 29 August 2013 at 18:57:58 UTC, Meta 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. 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.

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