Search
View source code
Display the source code in std/range/package.d from which this page was generated on github.
Report a bug
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

# `std.range.Recurrence/recurrence` - multiple declarations

## Function recurrence

Creates a mathematical sequence given the initial values and a recurrence function that computes the next value from the existing values. The sequence comes in the form of an infinite forward range. The type `Recurrence` itself is seldom used directly; most often, recurrences are obtained by calling the function `recurrence`.

``` Recurrence!(fun,CommonType!State,State.length) recurrence(alias fun, State...) (   State initial ); ```

When calling `recurrence`, the function that computes the next value is specified as a template argument, and the initial values in the recurrence are passed as regular arguments. For example, in a Fibonacci sequence, there are two initial values (and therefore a state size of 2) because computing the next Fibonacci value needs the past two values.

The signature of this function should be:

``auto fun(R)(R state, size_t n)``

where `n` will be the index of the current value, and `state` will be an opaque state vector that can be indexed with array-indexing notation `state[i]`, where valid values of `i` range from `(n - 1)` to `(n - State.length)`.

If the function is passed in string form, the state has name `"a"` and the zero-based index in the recurrence has name `"n"`. The given string must return the desired value for `a[n]` given `a[n - 1]`, `a[n - 2]`, `a[n - 3]`,..., `a[n - stateSize]`. The state size is dictated by the number of arguments passed to the call to `recurrence`. The `Recurrence` struct itself takes care of managing the recurrence's state and shifting it appropriately.

### Example

``````import std.algorithm.comparison : equal;

// The Fibonacci numbers, using function in string form:
// a = 1, a = 1, and compute a[n+1] = a[n-1] + a[n]
auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1);
assert(fib.take(10).equal([1, 1, 2, 3, 5, 8, 13, 21, 34, 55]));

// The factorials, using function in lambda form:
auto fac = recurrence!((a,n) => a[n-1] * n)(1);
assert(take(fac, 10).equal([
1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880
]));

// The triangular numbers, using function in explicit form:
static size_t genTriangular(R)(R state, size_t n)
{
return state[n-1] + n;
}
auto tri = recurrence!genTriangular(0);
assert(take(tri, 10).equal([0, 1, 3, 6, 10, 15, 21, 28, 36, 45]));
``````

## Struct Recurrence

Creates a mathematical sequence given the initial values and a recurrence function that computes the next value from the existing values. The sequence comes in the form of an infinite forward range. The type `Recurrence` itself is seldom used directly; most often, recurrences are obtained by calling the function `recurrence`.

``` struct Recurrence(alias fun, StateType, ulong stateSize) ; ```

When calling `recurrence`, the function that computes the next value is specified as a template argument, and the initial values in the recurrence are passed as regular arguments. For example, in a Fibonacci sequence, there are two initial values (and therefore a state size of 2) because computing the next Fibonacci value needs the past two values.

The signature of this function should be:

``auto fun(R)(R state, size_t n)``

where `n` will be the index of the current value, and `state` will be an opaque state vector that can be indexed with array-indexing notation `state[i]`, where valid values of `i` range from `(n - 1)` to `(n - State.length)`.

If the function is passed in string form, the state has name `"a"` and the zero-based index in the recurrence has name `"n"`. The given string must return the desired value for `a[n]` given `a[n - 1]`, `a[n - 2]`, `a[n - 3]`,..., `a[n - stateSize]`. The state size is dictated by the number of arguments passed to the call to `recurrence`. The `Recurrence` struct itself takes care of managing the recurrence's state and shifting it appropriately.

### Example

``````import std.algorithm.comparison : equal;

// The Fibonacci numbers, using function in string form:
// a = 1, a = 1, and compute a[n+1] = a[n-1] + a[n]
auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1);
assert(fib.take(10).equal([1, 1, 2, 3, 5, 8, 13, 21, 34, 55]));

// The factorials, using function in lambda form:
auto fac = recurrence!((a,n) => a[n-1] * n)(1);
assert(take(fac, 10).equal([
1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880
]));

// The triangular numbers, using function in explicit form:
static size_t genTriangular(R)(R state, size_t n)
{
return state[n-1] + n;
}
auto tri = recurrence!genTriangular(0);
assert(take(tri, 10).equal([0, 1, 3, 6, 10, 15, 21, 28, 36, 45]));
``````

## Authors

Andrei Alexandrescu, David Simcha, Jonathan M Davis, and Jack Stouffer. Credit for some of the ideas in building this module goes to Leonardo Maffi.