Function that calculates in compile time when it can

[Tobias Pankrath]

On Monday, 6 August 2012 at 15:18:22 UTC, Minas Mina wrote:
> That's what I tried to calculate:
> static x = fib(40);
>
> ulong fib(ulong n)
> {
> 	if(n < 2)
> 		return n;
> 	else
> 		return fib(n-1) +  fib(n-2);
> }
>
> Maybe because it has a lot of recursion?

That algorithm makes O(2^n) calls to fib. I think templates get 
only expanded
once for every set of parameters, so you get memoization build in 
and thus it's faster in this case.