再帰関数とは、関数の中で自分自身の関数を呼び出す関数です。例えば、hoge関数の処理の中でhoge関数を呼び出している場合、それは再帰関数だと言えます。また、関数の中で自分自身の関数を呼び出すことを「関数の再帰呼び出し」と言います。
　再帰関数は let rec キーワードを用いて宣言します。

// ------------------
// [ 構文 ]
// ------------------
let rec function-name parameter-list = function-body
                

　構文は通常の関数宣言とほぼ変わりません。変わっている点は rec というキーワードがあるかどうかだけです。ただし、このキーワードがあるかどうかで再帰関数特有の機能が使えるかどうかが変わります。
　以下はシンプルな再帰関数の例になります。


　サンプルからわかるとおり、fib関数の中でfib関数を呼んでいることがわかります。これが「関数の再帰呼び出し」です。再帰呼び出しをするだけなら通常の関数でも可能です。ただし、通常の関数では 相互再帰関数 などの再帰関数特有の機能が使えなかったりします。
　上記のように通常の再帰関数であれば、普通の関数でも再帰呼び出しが可能です。そのため、普通の関数で代用できてしまいます。しかしそれはオススメしません。普通は、ただの関数宣言を見ただけでは再帰呼び出しが発生するとは露ほども考えません。そのため、通常の関数で再帰呼び出しを利用していると驚いてしまいます。これは「驚き最小の原則」に違反します。
　そのため、「再帰呼び出しをこの関数では行っていますよ」という宣言をしておくことで可読性が向上します。別の章でもお伝えしていますが、可読性は正義です。自分しか迷惑がかからない個人開発では可読性の低いコードだろうが、何だろうが構いませんが、チーム開発においては致命的です。基本的にそのコードが何をしているのかがわかるようにキーワード等を適切に用いていくべきです。再帰関数を宣言するならば rec キーワードを必ずつけるように心掛けましょう。

　2つ以上の関数が相互に再帰的に呼び出し合うことがあります。つまり、「ある関数が別の関数呼び出しを行い、呼び出された関数がさらに次の別の関数呼び出しが最初の関数を呼び出していく」というような、円状の関数呼び出しを形成します。この円状の関数呼び出しを行う関数を相互再帰関数と言います。
　相互再帰関数を宣言するには、let recキーワード と andキーワード を組み合わせる必要があります。以下のサンプルで確認してみましょう。


　サンプルでは、偶数かどうかを判定する even関数 と、奇数かどうか判定する odd関数 が相互に呼び合って一つの機能を実現しています。
　相互再帰関数はあまり多用するような機能ではありませんが、存在を知らないとコードを読むときに頭を悩ませてしまうかもしれません。そうならないためにも、流暢に相互再帰関数を書けるようになる必要はありませんが、読める程度にはなっておいた方がよいでしょう。
　

　まず末尾最適化の話をする前に、以下の簡単な再帰関数を見ていきます。


　上記のサンプルは int list の合計値を求めるための再帰関数 'sum' です。C#のfor文で同様の処理を書いた場合も同時に示しています。。F#でも同じことをfor文などの制御構文を用いることでも実現できますが、それでは関数型っぽくないですよね？そして何より、for文で書くよりも再帰関数は見た目が美しくなりやすいです。見た目の美しさは非常に重要です。醜悪なコードは読み手を不快にさせ、コードの理解をしようという気持ちを妨げます。また、読みにくいコードは3日後の自分を苦しめることもあります。そう、自分で書いたコードのはずなのに、その自分が読めなくなるのです。そのため、美しいコードを書くように心掛けるべきです。
　では、いつでも上記のような通常の再帰関数で書けるのでしょうか？以下を見てみてください。


　大き目の引数を sum関数 に渡すと何やら "Process is terminating due to StackOverflowException" というおぞましい例外が出力されて、アプリがダウンしてしまいました。
　そうなのです。通常の再帰関数では、この StackOverflowException から逃れることはできないのです。この例外は再帰関数内の計算過程をスタックメモリに残しておいてしまうことが原因で発生します。スタックメモリは一般的に狭い領域しかありません。それをゴリゴリと使いまくるのが通常の再帰関数です。
　では美しさを諦めて制御構文を使うしかないのでしょうか？いいえ、そんなことはありません。StackOverflowExceptionを回避するための方法が存在します。その手法を 末尾最適化 といいます。これは途中の計算結果を一時保存して関数呼び出しの時に受け渡していくことによって例外を回避する方法になります。
　末尾最適化された再帰関数 sum の例を見てみましょう。


　無事、StackOverflowExceptionから逃れることができました。しかし、sum関数のインターフェースが変わってしまいました。これはあまり好ましくありません。sum関数は合計対象のlistだけ受け取ってくれるのが望ましい形(= あるべき姿)です。では、このあるべき姿にしましょう。


　これでコードの美しさを保ちつつ、StackOverflowExceptionからも回避できました。
　実際のところ、C/C++ や C# などに慣れ親しんでいる方からすると、制御構文でループ処理を書いたほうが万倍速く書けると思います。しかし、関数型プログラミングを追い求めるとなると、やはり末尾最適化されている再帰関数で解決することを優先するべきでしょう。また、初めてプログラミングを始めた方からすると再帰関数自体が意味不明かもしれません。そういったときは、簡単な再帰関数を書いてみて実際の動きをみることで、理解を深めることができると思います。