末尾再帰とは

auです。

プログラミングにおける最適化の一つとして、「末尾再帰」というものがあります。

どんな最適化なのか調べてみました。

末尾再帰とは

末尾再帰(Tail Call)とは、返り値が再帰関数の引数になるような再帰を指します。

普通の再帰だと、スタックのように計算が溜まっていくが、末尾再帰だと計算結果をそのまま引数にするので、スタックオーバーフローが起きません。

再帰
let rec pow a n = 
    if n <= 0 then 1 else a * pow a (n - 1);;

末尾再帰
let pow a n =
  let rec pow_iter result n = 
    if n <= 0 then result
    else
      let result' = result * a in
      pow_iter result' (n - 1)
  in pow_iter 1 n;;