Raw recursion speed can be slow

[corywalker]

If a function is recursive and not bound on any other complexity, the performance suffers by an order of magnitude.

DownValues[fib]={HoldPattern[fib[0]]->0,HoldPattern[fib[1]]->1,HoldPattern[fib[x_]]:>fib[x-1]+fib[x-2]}
fib[30]//Timing

Should only take about 3 seconds. Note that we avoid memoization here to stress test the recursion speed.