今回こそ再帰関数を有効的に利用したいと思います。代表的な例として、マッチングでもやってみましょう。
それでは、今回の要点です。
では、いってみましょう。
マッチングというのは、ある文字列と別の文字列を比較して、同じかどうかを確かめることです。それだけなら strcmp を使えばいいのですが、マッチングというと普通ワイルドカードを含みます。
ワイルドカードというのは、何の代わりにでも使える文字のことです。有名なカードゲーム「ＵＮＯ」にも、自由に色を変えることのできる「ワイルドカード」というのがありますね。あれと同じ事です。
ここでは、* というワイルドカードだけを考えたいと思います。この * は普通、「ここには文字が０〜ｘ文字ありますよ」というワイルドカードです。例えば、"*.txt" は "File.txt" や ".txt" などにマッチし、"Test.dat" にはマッチしないと言う具合です。
「じゃぁ、簡単だ。* の次に '.' があるわけだから、'.' が出てくるまで処理を飛ばせばいいんだ」ということで、次のようにしてみました。
| プログラム |
|---|
// Match1.cpp
#include <iostream.h>
#include <string.h>
bool Match(const char* str, const char* pszMatch)
{
int i, iMatch;
for(i = iMatch = 0; !(pszMatch[iMatch] == 0 || str[i] == 0); i++, iMatch++)
{
// ワイルドカードの時の処理
if(pszMatch[iMatch] == '*')
{
iMatch++;
for(; !(str[i] == pszMatch[iMatch] || str[i] == 0); i++);
// str が終了していると、ループはもう終了
if(str[i] == 0)
break;
}
// 普通の比較処理
else
{
// 文字が違えば、マッチは失敗
if(pszMatch[iMatch] != str[i])
break;
}
}
// マッチングが成功しているときは両方ヌルターミネータを指しています
// そうでないときは、異なる値が入っています
return pszMatch[iMatch] == str[i];
}
bool InputAndOutput()
{
static const char* pszResult[] = {
"マッチしませんでした。", "マッチしました。"
};
static const char szMatch[] = "*.txt";
char buffer[512];
cout << szMatch << " とのマッチングを行います。" << endl
<< "文字列を入力して下さい > " << flush;
cin >> buffer;
if(strcmp(buffer, "exit") == 0)
return false;
cout << pszResult[Match(buffer, szMatch)] << endl;
return true;
}
int main()
{
while(InputAndOutput());
return 0;
} |
| 実行結果 |
*.txt とのマッチングを行います。 文字列を入力して下さい > Test.txt マッチしました。 *.txt とのマッチングを行います。 文字列を入力して下さい > File.txt マッチしました。 *.txt とのマッチングを行います。 文字列を入力して下さい > File.txA マッチしませんでした。 *.txt とのマッチングを行います。 文字列を入力して下さい > File.txA.txt マッチしませんでした。 *.txt とのマッチングを行います。 文字列を入力して下さい > exit |
おや？ "Test.txA.txt" でマッチが失敗しています。
これがこのワイルドカードの厄介なところで、* の次の '.' が来るまで処理を飛ばすだけでは、'A' の部分でマッチングが失敗してしまうのです。
つまり、一回失敗したとしても、即座にマッチングを失敗させるわけには行かないのです。再び '.' の次からさらに '.' を探し、そこからも確認してみないことには、マッチングが失敗したのかは分からないのです。
一旦まとめてみます。'.' がくると、その後に "txt" が来るかどうか確認したいわけです。で、失敗するとまた次の '.' を探し、また "txt" が来るかどうか確認したいわけです。
ここで、素直に考えてみましょう。この「確認」には Match 関数自身が使えると思いませんか？ ということで、次のようにしてみましょう。
| プログラム |
|---|
// Match1b.cpp
#include <iostream.h>
#include <string.h>
bool Match(const char* str, const char* pszMatch)
{
int i, iMatch;
for(i = iMatch = 0; !(pszMatch[iMatch] == 0 || str[i] == 0); i++, iMatch++)
{
// ワイルドカードの時の処理
if(pszMatch[iMatch] == '*')
{
bool bRet;
iMatch++;
do
{
for(; !(str[i] == pszMatch[iMatch] || str[i] == 0); i++);
// str が終了していると、ループはもう終了
if(str[i] == 0)
goto EXIT_FUNC;
// マッチング
i++;
bRet = Match(&str[i], &pszMatch[iMatch + 1]);
}
while(!bRet);
return bRet;
}
// 普通の比較処理
else
{
// 文字が違えば、マッチは失敗
if(pszMatch[iMatch] != str[i])
break;
}
}
EXIT_FUNC:
// マッチングが成功しているときは両方ヌルターミネータを指しています
// そうでないときは、異なる値が入っています
return pszMatch[iMatch] == str[i];
}
bool InputAndOutput()
{
static const char* pszResult[] = {
"マッチしませんでした。", "マッチしました。"
};
static const char szExit[] = "exit";
char szMatch[512];
char buffer[512];
cout << "マッチングを行います。" << endl
<< "先ずはマッチ文字列を入力して下さい > " << flush;
cin >> szMatch;
if(strcmp(szMatch, szExit) == 0)
return false;
cout << "では、確認する文字列を入力して下さい > " << flush;
cin >> buffer;
if(strcmp(buffer, szExit) == 0)
return false;
cout << pszResult[Match(buffer, szMatch)] << endl;
return true;
}
int main()
{
while(InputAndOutput());
return 0;
} |
| 実行結果 |
マッチングを行います。 先ずはマッチ文字列を入力して下さい > *.txt では、確認する文字列を入力して下さい > Txt.txt.txt マッチしました。 マッチングを行います。 先ずはマッチ文字列を入力して下さい > *.txt では、確認する文字列を入力して下さい > File.txA.txt マッチしました。 マッチングを行います。 先ずはマッチ文字列を入力して下さい > *.txt では、確認する文字列を入力して下さい > .txt マッチしました。 マッチングを行います。 先ずはマッチ文字列を入力して下さい > *A*B*C では、確認する文字列を入力して下さい > ABBBCBBCB マッチしませんでした。 マッチングを行います。 先ずはマッチ文字列を入力して下さい > *A*B*C では、確認する文字列を入力して下さい > ABBBCBBC マッチしました。 マッチングを行います。 先ずはマッチ文字列を入力して下さい > exit |
問題なく動作しますね。
このように、ある動作を行いたいときにその関数自身が利用できる可能性も考える必要があるわけです。この考え方が出来るようになれば、プログラミングの幅も大きく広がると思います。
もう１つ、再帰関数の定番に「フォルダ操作」があります。が、これは機種依存なので詳しくは話しません。が、どんなことができるかくらいは話しておきましょう。
例えば、フォルダの中身を全て検索し、全てのファイル名を取得すると言うことが出来ます。
先ず、初めのフォルダの中身を検索します。そのとき、サブフォルダが出てくるとまたその中身を検索することになりますが、ここで再帰呼び出しが出来ますね。
ほかにも、深いフォルダを作成することもできます。
環境によるのかもしれませんが、深いフォルダを一気に作ることができないことがあります。そういうときは、１つずつフォルダを作っていくことになります。
先ず、フォルダ名を書き換え可能なバッファに移します。ここから再帰関数を呼び出します。この再帰関数では、先ずフォルダを１階層減らしてみます。後ろから '/' や '\' を探して (strrchr) 、これを消せば（ヌルターミネータに変えれば）いいですね。
で、このフォルダが存在するかを確認します。存在しなければ、再帰呼び出しをします。こうして、１階層ずつフォルダを確認して行くわけです。
そして、最終的にフォルダの存在する場所に来ます。そのとき、消した '/' や '\' を元に戻し、そのフォルダを作って return します。そして、戻ったところでも '/' や '\' を元に戻して、フォルダを作ります。これを繰り返していけば、深いフォルダが作れるわけですね。
フォルダのような構造のことを枝分かれした木に見立てて「木構造」というのですが、木構造のデータを扱うときは、このように再帰関数が活躍することがよくあります。
木構造を扱うときは、「再帰関数が使えるのでは？」という意識をもってかかるといいでしょう。
では、今回の要点です。
今回で再帰関数は終わりです。再帰関数は頭の中だけで考えるのはちょっと複雑になることもあるので、紙に書いてどうなるか考えてから作ってみるといいでしょう。
それでは、次回まで。さようなら。
第２２章 call itself ２ | 第２４章 たのしいソート
Last update was done on 2000.8.25
この講座の著作権はロベールが保有しています