再帰関数

再帰関数はその本体で自分自身を呼び出すような関数です。 したがって、再帰しない関数は再帰関数の単なる特殊形であるとも言えます: この種の関数はその本体で自分自身を決して呼び出しません。 再帰はプログラミング言語が提供しているもっとも効果的な機能だと、私は考えています。 再帰を使うことで、再帰的な戦略で問題解決をすることができます: すぐに解法を見つけることが困難な問題を解決するために、 問題を同様な単純な問題に減少させ、 さらに解法が明白になるまでその減少プロセスを繰り返します。 ここでは このような減少戦略を使った問題解決の具体的な例を見てみましょう。

与えられた整数を n とするとき、1 から n までの範囲の整数を全て足すことを考えましょう。 これは次のような再帰関数 sum1 にたやすく実装することができます:

fun sum1
  (n: int): int =
  if n >= 1 then sum1 (n-1) + n else 0
// end of [sum1]

与えられた範囲の整数の和を得るような次の再帰関数 sum2 を実装して問題解決することもできます:

fun sum2
  (m: int, n: int): int =
  if m <= n then m + sum2 (m+1, n) else 0
// end of [sum2]

整数 m と n が与えられた時、m から n までの全ての整数の和を取るために、また別の戦略があります: それは、もし m が n を超えないとすると、 m から (m+n)/2-1 までの全ての整数の和を取り、 さらに (m+n)/2+1 から n までの全ての整数の和を取り、最後に左記2つの和と (m+n)/2 の和を取ることです。 次の再帰関数 sum3 はこの戦略に忠実に実装されています:

fun sum3
  (m: int, n: int): int =
  if m <= n
    then let
      val mn2 = (m+n)/2
    in
      sum3 (m, mn2-1) + mn2 + sum3 (mn2+1, n)
    end // end of [then]
    else 0 // end of [else]
// end of [sum3]