Common Lisp, the upgrading/downgrading to/from fixnums/bignums is transparent (unless you don't want it to happen), and you have many options of implementing it depending on your needs, such as recursive, tail-recursive, iterative, memoized (it's easy to turn a normal function into a memoized one), dynamic programming and others.
For something like the famous Fibonacci problem, I would recommend a program such as Ruby. No bells or smells, no recursion, no iteration, no bells or smells, just Fibonacci.