宿題スレでこんなのがあったぞ。

751 名前: デフォルトの名無しさん Mail: sage 投稿日: 2009/05/13(水) 09:23:27
じゃあ同じO(n)でももっと変態な方法を

typedef struct { int a, b; } intx2;

intx2 fib2(int n) {
if (n == 0) {
return (intx2){ 0, 1 };
} else {
intx2 s = fib2(n - 1);
return (intx2){ s.b, s.a + s.b };
}
}

int fib(int n) {
return fib2(n).a;
}