[OCaml]#2 再帰関数を定義する

[OCaml]#1 OCamlで関数や変数を定義するでは関数をlet　変数（関数）名　引数1　引数2・・・のように定義したが、再帰関数を定義する場合にはrecというオプションが必要となる。

例を挙げて説明すると、
n xの2引数をとり、xのn乗を計算する再帰関数powerは、

# let rec power n x =
  if(n=0) then 1
  else if(n mod 2 = 0) then power (n/2) (x*x)
  else x * power (n/2) (x*x)
;;
val power : int -> int -> int = <fun>

のようにletと関数名の間にrecを入れる。そして、単にxをn回掛けるとO(n)の手間になってしまうので、再帰をうまく使いO(logn)で出来るようにした。
これは、例えば、x^10はx^10 = (x^5)^2 = (x*(x^2)^2)^2 とすると、掛け算の処理は4回で済む。
このようにx^2を(x^(n/2))^2とする時に、nが偶数か奇数かで分類している。


もうひとつ例を挙げると、フィボナッチ数列の第n項を求める関数を考える。

# let rec fib n =
  if n<=2 then 1
  else fib (n-1) + fib (n-2)
  ;;
val fib : int -> int = <fun>

とやってしまうと、fib (n-1) + fib (n-2)を求める過程で同じ計算を何度もしてしまうことになり効率が悪い。 これをO(n)で計算するためには、第n項から第1項に向かって順に求めていくのはなく、
実際にあなたがフィボナッチ数列を求めるように、第1項から第n項に向かって計算していけばよい。
つまり、

# let rec fib2 a b n cnt =
 if(n=cnt) then b
   else fib2 b (a+b) n (cnt+1)
;;
val fib2 : int -> int -> int -> int -> int = <fun>
# let fib n =
    fib2 1 1 n 2
;;
val fib : int -> int = <fun>

とすればよい。fib2でのcntはbが第何項かを保持している
ここで、recオプションを用いた再帰関数や、そのうち書くつもりだがandを用いて関数を同時に宣言する以外では、関数内で用いる関数は、その関数の定義時には既に定義されていなければならない。なので、補助関数fib2はfib内で使われているので、fib以前に定義しなければならない。