.NET開発者中心 厳選ブログ記事 C#開発者のためのやさしい「再帰」再入門 ― F#開発者ならこう考える ―― 「いげ太の日記」より ―― いげ太 2011/05/25

「.NET開発者中心 厳選ブログ記事」シリーズでは、世界中にある膨大なブログ・コンテンツの中から、特にInsider.NET／.NET開発者中心の読者に有用だと考えられるブログ記事を編集部が発掘・厳選し、そのブログ記事を執筆したブロガーの許可の下、その全文を転載・翻訳しています。この活動により、.NET開発者のブログ文化の価値と質を高め、より一層の盛り上げに貢献することを目指しています。

本稿は、ブログ記事「いげ太の日記： C#er のためのやさしい再帰入門」に簡単な校正・加筆を行ったうえで転載したものです。

　よく訓練された「C#使い」ならばご存じのとおり、C#に末尾最適化（＝メソッドの最後のステップがそのメソッドの再帰呼び出しになっている場合に、その処理効率を最適化する機能）はない。より正確に言い換えるなら、C# 4.0コンパイラは“tail.”プリフィックスを付与しない。このことによって、C#プログラミングにおいては、再帰はおよそ避けるべきものとして認識されている。しかし。

【Javaスクールの危険 - The Joel on Software Translation Projectより引用】

しかしポインタと再帰の明らかな重要性以上に重要なのは、これらの学習から得られる精神的な柔軟さと、これらを教えている授業からふるい落とされないために必要な精神的態度が、大きなシステムを構築するうえで欠かせないということだ。ポインタと再帰には、ある種の推論力、抽象的思考力、そして何よりも問題を同時に複数の抽象レベルで見るという能力が要求される。そしてポインタと再帰を理解できる能力は、優れたプログラマになるための能力と直接的に相関している。

　ならば。もしあなたが再帰の得意でないC#開発者であるならば、「末尾最適化を備えた.NET言語であるF#との対比によって、再帰に入門し直してみる」っていうのはどうか。

■はじめに

　この記事では、「末尾再帰」と「そうでない普通の再帰」の違いについては述べない。whileループを末尾再帰に書き換えるだけのことを説明する。

　なお、F#の文法について詳しく解説しないが、C#コードとF#コードを対比的に示しているから、およそ読み下せるであろうと思う。また、ステップ・バイ・ステップでコード例を書き換えていくため、途中の疑似コード例が、実行可能なコードではないことに注意してほしい。

■whileループから始めよう

　ありがちな学習用コードを示そう。「1」から引数「n」までの整数の総和を取る関数「Sum」（＝Sumメソッド）だ。ここでは、ごく簡単な例として示すために、forやforeachなどの高級なループ構文を使わずに、whileで書く。

int Sum(int n) {   var ret = 0;   var i   = 1;   while (i <= n) {     ret = ret + i;     i   = i + 1;   }   return ret; } // Console.WriteLine( Sum(10) ); // 55

「1」から引数「n」までの整数の総和を取るSumメソッドのコード例（C#）

　このC#コードと同等の意味を持つF#コードも示そう。「上のC#コードと下のF#コードに、たいした違いがない」と分かるだろう。

let sum n =   let mutable ret = 0   let mutable i   = 1   while i <= n do     ret <- ret + i     i   <- i + 1   ret // printfn "%d" (sum 10) // 55

「1」から引数「n」までの整数の総和を取るSum関数のコード例（F#）

■変数を減らす工夫

　さて、上記のコード例では、1、2、3、4と、数値を「1」ずつ加算してループを行うために、ループ・カウンタの「i」と、どこまで加算するかの終了条件となる「n」を、それぞれ個別の変数として持っている。

　しかしこれは、n、n-1、n-2、n-3と、数値を「1」ずつ減算していって最後は「1」で終わるようにすれば、引数の「n」自体をループ・カウンタとして使うことができるので、変数iをなくしてしまうことが可能だ。このような工夫を施して、C#コードを次のように書き換えよう。

int Sum(int n) {   var ret = 0;   while (n > 0) {     ret = ret + n;     n   = n - 1;   }   return ret; }

引数「n」自体をループ・カウンタにして変数を減らしたコード例（C#）

　同じようにして、F#コードも書き直そう。

　ただし、ちょっとした問題がある。F#の引数には基本的に再代入ができないのだ。よってここでは、関数内で、引数と同じ名前の再代入可能な変数を定義することで実現してみよう。「結局、実質の変数は減ってないじゃないか」って話だけど、気分はいくぶん楽になるだろう。

let sum n =   let mutable n   = n   let mutable ret = 0   while n > 0 do     ret <- ret + n     n   <- n - 1   ret

引数「n」自体をループ・カウンタにして変数を減らしたコード例（F#）

■変数でなく、引数として

　さて、上記のF#コードでは、いま「引数の『n』と変数の『n』は同質化してしまった」というわけだ。でもどうせなら、こんな「まがいもの」の同質化じゃなく、例えば次の疑似コードのように「本当に同じもの」だと呼べるようにしてしまいたい。もちろん、F#では引数への再代入ができないから、そう単純にはいかないわけだけど。

// こうしたい let sum n =   let mutable ret = 0   while n > 0 do     ret <- ret + n     n   <- n - 1   ret

引数の「n」と変数の「n」を「本当に同じもの」にした疑似コード例（F#）

　またここで、ついでに変数「ret」もなくしてしまいたい。いま関数内の変数「n」をなくそうとしているわけだけど、これはつまり、「変数の『n』を引数の『n』だけで、まかなってしまおう」ということで、すなわち、「関数内にある変数を引数に追い出してしまえば、万事オーケー」って寸法だ。それなら、併せて「ret」も引数に追い出してしまえばいい。そうすると、疑似コードは次のようになる。

// むしろこうしたい let sum ret n =   while n > 0 do     ret <- ret + n     n   <- n - 1   ret // 呼ぶときはこんな感じで // printfn "%d" (sum 0 10) // 55

変数の「ret」を引数に追い出した疑似コード例（F#）

　じゃあ、実際に変数を引数に追い出してみよう。でもどうすれば。

　再代入をなくせばいい。なぜいま再代入が必要か？ ループがあるからだ。

　なら、ループの代わりを探せばいい。そう、それが、つまり、再帰だ。

■繰り返しの条件

　でも、whileは条件判断の機能も担っている。whileループは取り除きたいが、条件判断だけは行いたい。

　よろしい、ならばifだ。whileループの中に隠れているifを引きずり出せ。白日の下に。コードの上に。

let sum ret n =   if n > 0 then     ret <- ret + n     n   <- n - 1   ret

whileループの中に隠れているifを書き出した疑似コード例（F#）

　としたところで1つ触れておきたいのは、実のところ、F#のifは文ではなく式であり、C#でいうところの条件演算子（いわゆる3項演算子、「cond ? exp1 : exp2」の形で値を返すアレ）の方に近いってことだ。つまり、上記のコードでは「exp2」に当たるものがなくて変だ。

　ここでは、次のコードのように、何もしないことを表す「()」という値を当て込んで、ひとまずの体面を整えておきたい。

let sum ret n =   if n > 0 then     ret <- ret + n     n   <- n - 1   else     ()   ret

if式のelse節に「()」を仮記述した疑似コード例（F#）

■sumthing else

　さて、肝心の再帰呼び出しをまだ書き入れていない。関数の内側からその関数自身を呼ぶのだ、上記の疑似コード例では再代入していた「ret + n」と「n - 1」を引数に渡して。

let sum ret n =   if n > 0 then     sum (ret + n) (n - 1)   else     ()   ret

if式のthen節で再帰呼び出しを行うコード例（F#）

　しかしこれはおかしなコードだ。何か変だ。そんなにおいがする。無理やりに突っ込まれた「()」がアンバランスさを教えている。

　これは、一度C#に立ち返って書き直すならば、こんなコードだ。

int Sum(int ret, int n) {   (n > 0) ? Sum(ret + n, n - 1) : null;   return ret; }

上記のF#コードと同等となるようなC#コード（条件式）の疑似コード例

　厳密には、F#の「()」はC#の「null」ではない。「()」を「null」で置き換えるのは無理やりに過ぎるとしたら、あるいはこんなコードと見立てよう。

int Sum(int ret, int n) {   if (n > 0)     Sum(ret + n, n - 1);   else     ;   return ret; }

上記のF#コードと同等となるようなC#コード（条件文）の疑似コード例

　何か嫌な予感がしてこないだろうか？

■再帰

　問題の本質はこうだ。

　while版のSumメソッドが呼ばれるとき、定義中の「return ret」が評価されるのは一度っきりだ。しかし、現状の再帰版Sumメソッドでは、再帰によってSumメソッドが呼ばれるたびに「return ret」が評価される。これはイケナイ。

　ということは、「return ret」が評価されるのを一度っきりにすればよいのであり、つまり、再帰時には「return ret」を通らないようにする。そんな場所に「return ret」を置くのだ。そんな場所はどこか？ それはelse節だ。

int Sum(int ret, int n) {   if (n > 0)     Sum(ret + n, n - 1);   else     return ret; }

上記のC#コード（条件分岐）のelse節に「return ret」を置いた疑似コード例

　オーケー。でもまだバランスが悪い。条件分岐の片側でしか「return」されていない。再帰呼び出しされたSumメソッドの戻り値が捨てられている。「きっと」こうだ。

int Sum(int ret, int n) {   if (n > 0)     return Sum(ret + n, n - 1);   else     return ret; }

完成した末尾再帰のC#コード（条件分岐）：上記のC#コードのif節で「return」により戻り値を返すようにしたコードの例

　「きっと」って、アバウトすぎる。なら、声に出して読んでみよう。指さし確認、声出し確認。

「n > 0」のときは、
　 「ret + n」の値を引数「ret」に渡し、「n - 1」の値を引数「n」に渡して、再度、Sumメソッドを呼んで、その結果を戻り値として返す、

そうでないときは、
　 「ret」の値を返す。

　ほら、何も問題ない。何も再帰だけ難しく考えすぎる必要はないんだ。

　ループを使うときに「この条件が成立する間はループの中身を実行して、成立しなくなったらそこから抜けて変数の値を返す」ということだけを意識すればよかったように、再帰だって前述のように読めばよいだけ、「この条件が成立するときは再帰して結果を返す、成立しなかったら引数の値を返す」と認識すればよいだけだ。

　重要なのは、どんな条件で再帰して、そして再帰の果てで何を返すのか。

　再帰によって、いずれその果てで得られる最終の結果を返すためには、再帰呼び出し部分にも「return」を付けておかなければいけない。再帰呼び出し先に結果の算出をお任せしておいて、そいつを捨ててしまっては元も子もない。

■それ、1行で

　F#のif式は、「C#の条件演算子により近しい」と述べた。ならば、次のように条件演算子を使って、C#コードを書き直そう。

int Sum(int ret, int n) {   return (n > 0) ? Sum(ret + n, n - 1) : ret; }

完成した末尾再帰のC#コード（条件式）

　そうしてF#に戻ろう。こうなる。

let sum ret n =   if n > 0 then sum (ret + n) (n - 1) else ret

C#コードから起こした、末尾再帰のF#コード

■寄せ

　実は、まだ上記のF#コードは動かない。下記で示すコードのように、再帰関数にはrecキーワードを付ける必要があるのだ。

let rec sum ret n =   if n > 0 then sum (ret + n) (n - 1) else ret

完成した末尾再帰のF#コード：「rec」キーワードを付与した末尾再帰のコード（F#）

　F#では、コードは上から順に定義され、未定義のモノを使用することはできない。また、定義中のモノは「未定義状態」と見なすのがデフォルトの解釈になるのだけれど、これを「定義済み状態」と見なすべく「rec」を付与するのである。つまり、「rec」のなし／ありが、定義中を「未定義」と見なすか／「定義済み」と見なすかを制御可能にするのである。少し込み入った説明をすると、そういうことだ。

　さあ、これで動くコードになった。けど、もうちょっとイイ感じに仕上げよう。かっこよく洗練された再帰関数にするのだ。

　まずはret引数だ。

　「ret」ではよく分からない。この場合は「accumulation」（＝蓄積）から「acc」と名付けるのがよいだろう。そして、この「acc」のような、再帰の間中、引き回すためだけの取って付けたような引数は、引数リストの最後に鎮座するのがお定まりだ。

let rec sum n acc =   if n > 0 then sum (n - 1) (acc + n) else acc

末尾再帰のF#コードの洗練：適切な意味を持つ変数名を付け、引数リストの順序を入れ替える

　次に、再帰呼び出しの位置だ。

　別に現状でも何ら問題はないが、せっかく「末尾再帰」と呼ばれるものを書いたのだから、コード上でも後ろの方にあった方が、「“この例の場合は”それっぽく見えていい」と思える。if式の条件をうまくひっくり返して、then節とelse節を入れ替えよう。

let rec sum n acc =   if n <= 0 then acc else sum (n - 1) (acc + n)

末尾再帰のF#コードの洗練：名実ともに「末尾再帰」になるようにif式を工夫する

　最後に、sum関数の呼び出し側を考える。

　いまsum関数の呼び出しは、例えば「10」までの総和であれば、「sum 10 0」のようなコードを記述する必要がある。そのくせ、第2引数は常に「0」でよい。常に「0」でよいのなら、常に「0」を与えるような関数でラップして、「sum 10」というコード記述で呼び出せるようにするべきだ。具体的には下記のようなコードになる。

let sum n =   let rec f n acc = if n <= 0 then acc else f (n - 1) (acc + n)   f n 0

末尾再帰のF#コードの洗練：無意味な引数をラップして再帰関数の呼び出しをシンプルにする

　これでF#によるイケてる末尾再帰コードは完成だ。

　そして最後の最後に、このF#コードと同等の意味を持つC#コードを記述するならば、下記のようになるだろう。ただし、冒頭で書いたように、C#では末尾最適化が行われないため、このような再帰的な定義は通常行うべきでないことには十分注意してほしい。

public int Sum(int n) {   Sum(n, 0) } private int Sum(int n, int acc) {   return (n <= 0) ? acc : Sum(n - 1, acc + n); }

末尾再帰のC#コードの洗練

　お疲れさま。これで出来上がり！

【筆者プロフィール】 いげ太（いげた） 　Microsoft MVP for F#。共著書に『実践F#　関数型プログラミング入門』（技術評論社、2011年）。 いげ太の日記：http://igeta.tumblr.com/ Twitter：@igeta

「.NET開発者中心 厳選ブログ記事」

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）