関数型プログラミングにおける再帰関数の考え方

この記事はFP in Scala勉強会#2にて触発されました。
主催者のもがみんより再帰の記事説明してくださいと言われたので。
しかしコードはSMLで書きます。それが一番自分が説明楽なので。
読む方は自分の言語に適宜置き換えてください。（放棄）
また、ML Advent Calendar 2015の13日目です。

loopにforやwhileを使う言語から来た人が関数型プログラミングでよく躓く1つが再帰関数だと思います。
実際に勉強会でも例題を再帰関数で書く人は少なかったと思います。
そこで本記事では簡単な例ですが再帰関数初心者の設計の助けになればと思います。

再帰関数とは

自分の定義の中で自分自身を呼び出す関数です。
例えば以下のコードは何もしない無限ループですが、再帰関数です。

loop.sml

fun loop () = loop ()

再帰関数の使い方・考え方

対象とするデータ構造は？

代数的データ型が対象となります。
例えば一般的なリストは以下の様な代数的データ構造をしています。
簡単に言うと、nil（空のリスト）、または、要素とリストを::で組み合わせたものになります。
ちなみにSMLではリストの糖衣構文として[]も用意されています。

list.sml

datatype 'a list = nil
                 | :: of 'a * 'a list

list_example.sml

val list1 = nil
val list2 = 1 :: nil
val list3 = "a" :: "list" :: "is" :: "like" :: "this" :: nil

val list1' = []
val list2' = [1]
val list3' = ["a", "list", "is", "like", "this"]

再帰関数の設計

代数的データ型に対して各要素に操作をしたいときに、構造にしたがってパターンマッチと再帰を使います。
リストの定義は、終端であるnilと、自身の構造が再帰している::があります。
よってパターンマッチはnilと::で分けます。
さらに自身の構造が再帰している::では再帰関数を使うことになります。

例えばリストの全整数要素に対して+1するうな関数を書こうと思うときを考えます。
リストの構造でパターン分けをしています。
さらにパターンのうちh::tでは、tがさらにリストなのでaddOne tを使って再帰するはずです。

add1.sml

fun addOne list =
  case list of
    nil  => (* 何らかの式 *)
    h::t => (* 再帰 addOne t を使った何らかの式 *)

再帰関数の実装

個人的な考えですが、一番大事なことは、
「元の引数よりも構造が小さデータに対する再帰関数は正しい結果を返すと仮定して書く。」
だと思っています。

例えば先の例では、addOneという関数は、「全要素を+1する」という動作を実現しようとしています。
そこで、パターンh::tにおいてより小さな構造をしたtの再帰関数であるaddOne tは、「正しくリストtの全要素を+1する」として使えるのです。
よって、パターンh::t内では、残った要素hをどうやってaddOne tと結合するかだけを考えればよいのです。
今回の例では、hも+1してリストを組めば良いので、以下のようになります。

add1.sml

fun addOne list =
  case list of
    nil  => nil
    h::t => (h+1) :: addOne t

末尾再帰関数との関係

末尾再帰関数とは、関数内で再帰関数を呼び出す位置がその関数の最後の計算であるものです。
さらに、末尾再帰関数はコンパイラによって最適化がかかり、スタックオーバーフローを防いだり、高速に動いたり、となることがあります。

個人的な考えとしては、末尾再帰関数は必須ではありません。
まずは素直に上記の考えで実装を行い、速度やメモリ消費量に問題があるときに、末尾再帰化を考慮すればいいと思います。
※本記事では末尾最適化は取り扱いません。

まとめ

• 再帰関数は構造が再帰している代数的データ型を扱うときに使う
• 元の引数より小さな構造をしたデータへの再帰関数は正しい結果を返すと仮定して実装する
• 再帰関数は怖くない！

アペンディクス：ScalaのArrayでの例

話の元となった勉強会では以下の様な例題で、対象はArrayでした。
Listなどとは違い、Arrayのデータ構造は再帰的な定義ではありませんが、
forループで配列長を使って終了条件を判断するように、
ifで配列長を判定して再帰をするような記述ができると思います。

add.scala

def addOne(as: Array[Int]): Unit = {
  def loop(i: Int): Unit = {
    if (i >= as.length) ()
    else {
      as[i] = as[i] + 1
      loop(i+1)
    }
  }
  loop(0)
}