スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#入門第27回(再帰(1))

今回のお題は「再帰(1)」です。
 
まずは宿題の答えから
 
宿題
 
let lst : (int -> int) list = [(fun x-> x + 1);(fun x -> 3 * x);(fun x -> x + 2) ]
let f = List.fold (>>) (fun x -> x) lst 
 
としたときfは何を表すでしょうか。
 
(答え)
 
(((fun x -> x) >> (fun x-> x + 1)) >> (fun x -> 3 * x)) >> (fun x -> x + 2) 
ですから
(fun x -> (3*(x + 1)) + 2) すなわち
(fun x -> 3*x + 5)を表します。
 
さて今回のお題です。
普通CやJavaの入門では、最初の方にfor ループの話とかがくるのですが、関数型言語の入門書では、forループの話は出てきません。(部分的に出てくる場合はありますが。)
F#は「関数型」と「命令型」のキメラ言語ですので、後ほど命令型の側面のお話をするときには登場するのですが、今までの「関数型言語」としての、F#ではforループは、リスト内含表記で出てくるのみで、今後も出てきません。それでは、Forループの代役は何が果たすのでしょうか。答えとしては、Listで代用(特によく使われるのがList.fold)もしくは、今回紹介する再帰関数です。
まずは、再帰関数の基本的な部分から復習します。
まず、関数といっても、関数の定義部分と、「仮変数に実際の値をはめ込んで、どんどん評価していく」という二つの段階があります。
再帰関数というのは、実際に評価されていくときに、引数を変えながら、同一の定義の関数を繰り返し呼び出していく関数のことです。
とりあえず例をみてみましょう。再帰関数を定義するにはキーワードrec を関数名の前につけます。
 

 
let rec recSample01 (k:int) =
    printfn "引数%dで関数内に入りました" k
    match k with
    | _ when k = 0 -> printfn "引数が0になったのでこれ以上関数を呼び出しません"
    | _            -> recSample01 (k - 1)
                      printfn "引数%dの関数に戻ってきました"  k
                      
これが定義部分です。
見て分かるように、引数が0に適用すると、これ以上関数を呼び出しません。
それ以外のときは、引数を一つ減らしたものに、この関数を適用します。
さて、それではk = 3のときに、どのような実行結果になるかを予想してみてください。
では実験です。
 
> recTest 3;;
 
引数3で関数内に入りました
引数2で関数内に入りました
引数1で関数内に入りました
引数0で関数内に入りました
引数が0になったのでこれ以上関数を呼び出しません
引数1の関数に戻ってきました
引数2の関数に戻ってきました
引数3の関数に戻ってきました
val it : unit = ()
 
予想は合っていましたでしょうか、「引数?の関数に戻ってきました」の部分を正確に予想できましたでしょうか。
例えば引数3の場合の関数呼び出しの中で、引数2で関数を呼び出すのですがこの時、呼び出した関数が戻ってきたあとの仕事(「引数3の関数に戻ってきました」と表示すること)が残っているのです。よって、返ってきた後、この仕事が遂行されます。
大事なのは、次の関数を呼び出すまで(行き)と、返ってきてから(帰り)の処理があるということです。(なにせ、再帰(再び帰ってくる)関数です。)
 
次にこの関数を-1に適用しましょう。どうなるでしょうか。理論上では、引数が一つずつ減って行き、どんどん関数を呼び出しますので、引数が0になることがなく、無限に関数呼び出しを続けます。(int型には範囲があり、桁あふれがおこるので、これは起こりません。それどころか、桁あふれして0に戻る前に、スタックオーバーフローというものに見舞われます。これは、なぜかというと、返ってきてから(帰り)の処理(仕事)というのは、スタックに記憶されるのですが、これは、それほどは容量が大きくないのです。一杯になって、あふれ出して(オーバーフロー)してしまうのです。
ということで、再帰関数を定義するときの原則を二つほどあげておきます。
(1)どのとき、さらなる関数呼び出しをやめるかを定義に含めておく。(終了条件といいます。)
(2)できる限り、帰りの処理を少なくする。
(あまり深くない(関数呼び出しの回数が少ない)再帰では(2)は、無視されたりすることもあります。(1)は絶対無視してはダメです。)
 
さてそれでは次の例です。(これは、よくみかける例です。)
 
let rec recFact1 n =
    match n with
    | 1 -> 1
    | n -> n * (recFact1 (n - 1))
 
これは、引数が1になると、1を返す。(終了条件)
それ以外では、「引数 -1」に関数を適用したものに、引数をかけて、呼び出し元に返す」
という関数です。(つまり、帰りの処理として、返ってきた値に引数をかけて、呼び出し元に返すということです。)
 
図で書くと(最初の引数が4の場合です。)
 
引数 :     4             3          2        1
行き              →          →       →    
帰り  4*(3*(2*1))←   3*(2*1) ←  2*1  ←    1  
 
それでは念のため関数にどういう動きをしているかを表示するprintfn関数を追加してみます。
 
let rec recFact2 n =
    match n with
    | 1 -> printfn "引数が1なので、1を呼び出し元に返します"
           1
    | _ ->  let t = recFact2 (n - 1)
            printf "引数 %dで呼び出した関数の返り値が%dなので、" (n-1) t
            printfn "これに%dをかけた数%dを呼び出し元に返します" n (n * t)
            n * t //これが返り値
            
実行例
 
> recFact2 4;;
引数が1なので、1を呼び出し元に返します
引数 1で呼び出した関数の返り値が1なので、これに2をかけた数2を呼び出し元に返します
引数 2で呼び出した関数の返り値が2なので、これに3をかけた数6を呼び出し元に返します
引数 3で呼び出した関数の返り値が6なので、これに4をかけた数24を呼び出し元に返します
val it : int = 24
 
つまるところrecFact1,recFact2は、数の階乗を返す関数なのでした。
 
さて、recFact1は返り値が返ってきたときに、何らかの数をかけて、呼び出し元へ戻しています。
「再帰関数の定義原則(2)できる限り、帰りの処理を少なくする」に、基づき、改良できないか考えてみます。
まずは「返りの処理を少なくする」の究極の形を考えてみましょう。これは、「返り値をそのまま呼び出し先に返し、あとは仕事をのこさない。」ということです。
つまり、関数のおこなう最後のステップが、再帰呼び出しになるようにすることです。
例えば
 
let rec recsam  引数 =
    .....
    .....
    .....
    recssam (上とは異なる引数) //これがこの関数の返り値
 
という形にすることです。
この形なら、呼び出した関数から値が返ってきたときに、、その値を呼び出し元の関数へ
戻す仕事だけしか、残っていません。
このような再帰を末尾再帰といいます。
 
それでは、具体例に入ります。返りの仕事は返り値を返すだけなの、ですから、必要なことは、「行き」の方で済ます必要があります。「行き」の方で済ますのであれば、その作業結果を次に呼び出す関数に伝える必要があります。ということで答えにつながるデーターを次の関数に伝えるようにします。(これを、ここでは「答えの種」と呼ぶことにします、)
さてそれでは、さっきの関数を定義しなおしてみます。
 
let rec recFact3 seed n =
    match n with 
    | _ when n = 1 -> seed
    | _            -> recFact3 (seed * n) (n - 1)
 
引数に答えの種であるseedが付け加えられました。呼び出すときはこれを1にして呼び出します。
 
> recFact3 1 3 ;;
val it : int = 6
 
> recFact3 1 4 ;;
val it : int = 24
 
 
    引数 :     4             3          2               1
seed 行き       1     →     4*1    →   3*(4*1)  →   2*(3*(4*1)  
     帰り 2*(3*(4*1))← 2*(3*(4*1) ←2*(3*(4*1)  ←   2*(3*(4*1)
 
どうでしょうか、行く順方向だけを考えればよいので、割と頭にもやさしいのではないでしょうか。(この関数では引数seedにn倍するという作業をして、次のseedとして渡していき、n= 1のところまで、行ったらそれを、そのまま元まで返します。)
 
また、このように関数を定義するとき、一回一回seedの部分を1にして呼び出すのは、不格好なので、よくある方法としては、recFact3を関数内部で、定義してしまいます。
 
let recFact4 k =
    let rec recFact3 seed n =
        match n with 
        | _ when n = 1 -> seed
        | _            -> recFact3 (seed * n) (n - 1)   
    recFact3 1 k    
 
こうしておけば 単にrecFact4 5 とすればrecFact3 1 5が呼び出されるようになります。
 
もっと頭にやさしく改良してみます。
引数をカウントダウンするかわりに、カウントアップさせてみます。
どこで、カウントアップをやめるかをlimitという引数で、与えることにします。
 
    let rec subF seed n limit =
        if n = limit then
            seed
        else
            subF ((n + 1) * seed) (n + 1) limit         
 
これ補助関数で、nがlimitになるまで、(n+1)倍しては、nをカウントアップします。
seedの初期値は1とします。
 
   引数 n :    1             2          3               4(=limit)
seed 行き       1     →     2*1    →   3*(2*1)  →   4*(3*(2*1)  
     帰り 4*(3*(2*1))← 4*(3*(2*1))←4*(3*(2*1)) ←   4*(3*(2*1))
 
全体としては、次のようになります。
 
let recFact5 k =
    let rec subF seed n limit =
        if n = limit then
            seed
        else
            subF ((n + 1) * seed) (n + 1) limit         
    subF 1 1 k
 
ただ、limitはkで固定なので、スコープを考えると、次のようにも書けます。
 
let recFact6 k =
    let rec subF seed n  =
        if n = k then
            seed
        else
            subF ((n + 1) * seed) (n + 1)         
    subF 1 1 
 
 
これらの方法以外に「帰り」にすべき残った仕事を関数化して、累積して次に渡していくという方法もあります。
試しに上の例で挑戦してみると
 
let recFact7 k =
    let rec makeFuncLst lst n =
        match n with
        | _ when n = 1 -> lst //付け足す関数なし
        | _            -> //n倍するという関数をリストに付け足す
                          makeFuncLst ((fun x -> n * x) :: lst) (n - 1) 
 
     //種を[]として上の関数で関数リストを育て上げる
     let accumulatedFuncList = subF [] k 
     (List.fold (|>) 1 accumulatedFuncList) 
 
実行例
 
> recFact7 5;;
val it : int = 120
 
それでは、宿題です。
フィボナッチ数列(隣り合う2項の和が次の項になる数列)
1,1,2,3,5,8,13,..
の第n項を求める関数fibo n を書いてください。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。