メモ - Tail Recursive Fibonacci in OCaml

let fib = let rec f x y n = if n=1 then x else f (x+y) x (n-1) in f 1 1;;

けっこう時間かかってくやしい。ふつうに fib(n) = fib(n-1)+fib(n-2)みたいなノリで書くと計算量が 2^n で増えていくからいろいろよろしくない。かといってHaskellみたいに遅延評価でメモ化するとデバッグ大変だろなとか思う。かといって一般項求めてやると、Fibonacciの一般項は浮動小数点が入るから誤差がどーとか嬉しくないはず。
「関数の引数で送る」っていう感覚を実体化するのに苦労した。
実際この効果はすごくて、fib 10;;くらいだと全然差が出ないけどfib 100;;やってみるともうアカンたい

アホの子に根気よく教えてくださった @camlspotterさん, @_2F_1さん、ありがとうございました。あと機会を設けてくれた@ymotongpoo君も、ありがとう。

ちなみにC版

int fib(int n){
  int sum, tmp;
  sum = tmp = 1;
  while( n-- > 0 ){
    int s = sum;
    sum += tmp;
    tmp = s;
  }
  return sum;
}

学部生のときにCとかJavaで再帰習ってたけど、あんなのアホのすることだよね。なんであんなの教えるんだろ。