D Recurrences

[Andrei Alexandrescu]

On 6/9/11 10:19 AM, Ben Grabham wrote:
> Hey,
>
> Shouldn't both these programs output the fibonnacci numbers? Only the
> first one does.
>
> import std.range;
> import std.stdio;
> int main() {
> auto a = recurrence!("a[n-1] + a[n-2]")(0,1);
> int i = 0;
> foreach(int n; a) {
> if(i++ > 20) break;
> writefln("%d", n);
> }
> return 0;
> }
>
>
>
> import std.range;
> import std.stdio;
> int main() {
> auto a = recurrence!("a[n-1] + (n < 2 ? 0 : a[n-2])")(1);
> int i = 0;
> foreach(int n; a) {
> if(i++ > 20) break;
> writefln("%d", n);
> }
> return 0;
> }

The second implementation is in error. The state of the recurrence is 
defined by the number of parameters, so it will consist of one number. 
Fibonacci needs the last two numbers.

The code doesn't fail because recurrence uses modulus with all indices, 
which means a[n-1] and a[n-2] will refer to the same (and only) element 
in the recurrence state.

It would be be possible to detect this at run time, but it would slow 
things down a bit.


Andrei