(9-1)[ML] 補足:再帰的関数の考え方

[ トップ | 目次 | 前ページ | 次ページ ]


再帰的な定義機構は,Cのメモリー変数を用いた定義やJavaのクラスに基づくオブジェクトメソッドの定義などに比べても,けっして難解なものではない.プログラミングの初歩を学ぶ者にとっても,その考え方を理解してしまえば,より単純かつ応用範囲の広い道具として使いこなすことができる.

再帰的な記述

多くの関数は再帰的に定義される.Cでは繰り返しの途中の状態を設計したが,再帰的関数定義の基本は,求めるべき関数の値が満たすべき条件を等式として表現することである,Cでの繰り返しの考え方で学んだ各関数は,以下のような等式として記述できる,

  • 積を求める.(先ほど定義した階乗の計算)
    • factorial(0) = 1
    • factorial(n) = factorial(n-1) * n
  • 総和を求める.
    • sum(0) = 0
    • sum(n) = sum(n-1) + n
  • 2乗の和を求める.
    • sigma2(0) = 0
    • sigma2(n) = sigma2(n-1) + n*n
  • 3乗の和を求める.
    • sigma3(0) = 0
    • sigma3(n) = sigma3(n-1) + n*n*n
  • 掛け算を足し算を使って求める.(x * yはxをy回足したもの)
    • times(x,0) = 0
    • times(x,1) = x
    • times(x,y) = x + times(x, y - 1)
  • 与えられた数nをk乗する.
    • power(n, 0) = 1
    • power(n, k) = n * power(n,k-1)
  • 初項が1公差が2の等差数列(注1)
    • A(0) = 1
    • A(n) = A(n - 1) + 2
  • 初項が1公差が2の等比数列
    • B(0) = 1
    • B(n) = 2 * B(n - 1)
  • 漸化式
    • C(0) = 1
    • C(n) = 2 + 3 * C(n - 1)

これらは当たり前の定義として,理解できるであろう.

再帰的な関数定義

再帰的関数のコーディングの基本は,

「その関数がすでにある」と思って,その関数の本体を書き下す

ことだけである.C言語のようにメモリの内容を変更しながら結果を求めていくやり方と違い,関数型言語は,値を計算する関数そのものを定義していくので,どのような動作をするかを考える必用はない.

上記の関数のMLでの定義は,上記の定義をそのままMLの文法で以下のように書き下せばよい.

  • 積を求める.(先ほど定義した階乗の計算)
    • factorial(0) = 1
    • factorial(n) = factorial(n-1) * n
fun factorial 0 = 1
  | factorial n = factorial(n-1) * n
  • 総和を求める.
    • sum(0) = 0
    • sum(n) = sum(n-1) + n
fun sum 0 = 0
  | sum n = sum (n-1) + n
  • 2乗の和を求める.
    • sigma2(0) = 0
    • sigma2(n) = sigma2(n-1) + n*n
fun sigma2 0 = 0
  | sigma2 n =  sigma2 (n-1) + n*n
  • 3乗の和を求める.
    • sigma3(0) = 0
    • sigma3(n) = sigma3(n-1) + n*n*n
fun sigma3 0 = 0
  | sigma3 n =  sigma3 (n-1) + n*n*n
  • 掛け算を足し算を使って求める.(x * yはxをy回足したもの)
    • times(x,0) = 0
    • times(x,1) = x
    • times(x,y) = x + times(x, y - 1)
fun times(x,0) = 0
  | times(x,1) = x
  | times(x,y) = x + times(x, y - 1)
  • 与えられた数nをk乗する.
    • power(n, 0) = 1
    • power(n, k) = n * power(n,k-1)
fun power(n, 0) = 1
  | power(n, k) = n * power(n,k-1)
  • 初項が1公差が2の等差数列(注1)
    • A(0) = 1
    • A(n) = A(n - 1) + 2
fun A 0 = 1
  | A n = A (n - 1)  + 2
  • 初項が1公差が2の等比数列
    • B(0) = 1
    • B(n) = 2 * B(n - 1)
fun B 0 = 1
  | B n = 2 * B(n - 1)
  • 漸化式
    • C(0) = 1
    • C(n) = 2 + 3 * C(n - 1)
fun C 0 = 1
  | C n = 2 + 3 * C(n - 1)

テスト

以上の関数定義をファイルrecursions.smlに書き出し,テストしてみよう.以下のような出力が得られるはずである.

SML# 0.20 (2007-04-19 14:20:41)
# use "recursions.sml";
val factorial = fn : int  -> int
val sum = fn : int  -> int
val sigma2 = fn : int  -> int
val sigma3 = fn : int  -> int
val times = fn : int * int  -> int
val power = fn : int * int  -> int
val A = fn : int  -> int
val B = fn : int  -> int
val C = fn : int  -> int
# factorial 10;
val it = 3628800 : int
# sum 10;
val it = 55 : int
# sigma2 10;
val it = 385 : int
# sigma3 10;
val it = 3025 : int
# times(2,3);
val it = 6 : int
# power(2,3);
val it = 8 : int
# A 10;
val it = 21 : int
# B 10;
val it = 1024 : int
# C 10;
val it = 118097 : int
#

[ トップ | 目次 | 前ページ | 次ページ ]

Last modified:2007/05/15 10:59:29
Keyword(s):
References:[ML&Cチュートリアル 目次] [(9)[ML] 関数定義] [(19)[ML] 高階関数]