std.range should support recursion (Was: One-line FFT, nice!)

[jerro]

>
> I think there is one thing in this code that will hurt 
> performance much, much, more than allocations. This code will 
> compute elements of the result lazily. So each time you want to 
> read an element from the resulting range, O(log(n)) functions 
> passed to map() will need to be computed. The problem is that 
> each of those functions computes sine and cosine, so sine and 
> cosine need to be computed O(log(n)) times for each element. To 
> get all n elements, you will need to compute them O(n log(n)). 
> Because computing sine and cosine is about two orders of 
> magnitude slower than multiplication and division, this will be 
> very slow.

I was wrong about the complexity. Because each element of the 
result depends on all the elements of the argument range, you 
actually need O(n) function calls to compute each element of the 
result and O(n*n) function calls(and sine and cosine 
computations) to compute all of them. You would need to use 
memoization to get reasonable complexity.