再帰

再帰（recursive）とは、関数の概念をもつプログラミング言語において、ある関数が関数内で自分自身を呼び出すようになっているものをいう。

再帰の例といえば、どのアルゴリズムやプログラミングの教科書も、「階乗」と「フィボナッチ数」、「クイックソート」と相場が決まっている。それに習ってF#による階乗の記述例を書いてみる。

let rec fact x =            // F#で再帰を使う際にはrecと明示する
    if x < 1L then 1L       // 終了条件
    else x * fact (x - 1L)  // fact関数内でfact関数を呼び出す

(* 実行してみる。なおこの行はF#におけるブロックコメントだよ *)
[0L .. 16L] |> Seq.iter (fun x -> printfn "fact(%O) = %O" x (fact x));;

ここ最近でもないが近代的なコンピューターの大半はスタックマシンであり、プログラミング言語の大多数も関数の実装にコールスタックを使っているので、再帰が深くなるとスタックオーバーフローを引き起こす。この問題については末尾再帰最適化などの手法により回避するのが流行っている。関数呼び出しはコストも大きいのでベンチマークもかねて単体テストはしっかりやろう。

再帰にとって、もっとも重要なのは脱出条件であり、脱出条件を間違えるというバグは永久ループへと直結するので、やっぱり単体テストはしっかりやろう。

関連項目

• 相互再帰 - 「関数A → 関数B → 関数A → 関数B →」という環状の再帰のこと。
• 末尾再帰
• アルゴリズム