The recursive solution is terrible, because it takes exponential time. The iterative solution isn't bad - this takes O(n) time. It's possible to do O(log n) time using Binet's formula.

int fib_rec(int n) { switch(n) { case 0: return 0; case 1: return 1; } return fib_rec(n-2) + fib_rec(n-1); } int fib_iter(int n) { switch(n) { case 0: return 0; case 1: return 1; } int f0=0; int f1=1; for(int i=2;i<=n;++i) { int f2=f0+f1; f0=f1; f1=f2; } return f1; }