The Fibonacci series. You know don't know what it is until you understand why this works:
PHI = 1.6180339887498948482045868 fib = lambda do |n| ( ( PHI**n - ( 1 - PHI )**n ) / Math.sqrt(5) ). floor end
With this Ruby code, simply call fib[n] where n is any number to get the corresponding element of the (classical) Fibonacci series.
Why does this work? Because the constant PHI is itself recursively defined. The lesson here is that if you can isolate the recursion in a constant value, you can write a non-recursive mathematical expression.
(The difficulty, of course, is choosing the proper constant. But such is the art of mathematical analysis!)
NOTE: grab the first 2000 Fibonacci numbers here: http://oeis.org/A000045/b000045.txt