「再帰」を編集中

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

再帰の例といえば、どの[[アルゴリズム]]や[[プログラミング]]の教科書も、「[[階乗]]」と「[[フィボナッチ数]]」、「[[クイックソート]]」と相場が決まっている。それに習って[[F Sharp|F#]]による[[階乗]]の記述例を書いてみる。
<source lang="fsharp">
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));;
</source>

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

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

== 関連項目 ==
* [[相互再帰]] - 「関数A → 関数B → 関数A → 関数B →」という環状の再帰のこと。
* [[末尾再帰]]
* [[アルゴリズム]]

== 参考文献 ==
<references/>

== 外部リンク ==

{{stub}}