C++ 再帰関数 書いて覚えるための初心者自己中記事

自分自身を呼ぶ関数を再帰関数と呼ぶ。

void Forever() {//再帰関数
	cout << "Forever" << endl;
	Forever();//再帰呼び出し
}
 
int main() {

	Forever();
 
system("pause");
}

自分自身を呼ぶことを再帰呼び出しという。

永遠とループする。エラー。

スタックオーバーフローする。

スタックオーバーフローはスタック領域があふれること。

何がスタック領域に積み重なったかというと、関数を呼び出した時に呼び出した場所へ戻るためのアドレスが保存される。

再帰呼び出しでそれがひたすら積まれた。

int i;
void Forever() {//再帰関数
	if (i < 3) {
		cout << "Forever : " << i << endl;
		++i;
		Forever();//再帰呼び出し
	}
}
int main() {
	Forever();
system("pause");
}

終了条件を付ければ大丈夫。

グローバル変数を使わないで、再帰関数の引数を利用する。

void Forever(int count) {//再帰関数
	if (count < 3) {
		cout << "Forever : " << count << endl;
		
		Forever(++count);//再帰呼び出し
	}
}
int main() {
	Forever(0);
	system("pause");
}

これも簡単。

つぎ、戻り値も利用して階乗を求める。

unsigned int Factorial(int count) {//再帰関数
		return count == 0 ? 1 : count * Factorial(count - 1);//再帰呼び出し	
}
 
int main() {
	cout << "階乗 : " << Factorial(5) << endl;;
	system("pause");
}

複雑になった。

引数count が０になるまで再帰呼び出しは行われる。

またcountが０の場合は１を返す。

逆順に考えると、count が１の時の戻り値は１

その戻り値に呼び出し元でcount をかける。

その答えがreturnで戻り値になって、また呼び出し元のcount をかける。

うん。

社長（mainで呼び出したFactorial）からの指示がどんどん部下に伝わっていって、末端の社員が行った仕事が、その上司、そのまた上司とどんどん上に上がっていく。

上がっていくときに上司は少しずつ部下の仕事を訂正していって最終的に社長の元に届く。

って感じか。

 次に文字列チェック。

* をワイルドカードとして文字列が一致するかのチェック。

その前にテキストのコード見てたら気になる部分があったのでそこから。

void Test(const char* str, const char* pat) {
	cout << *str << " " << *pat << endl;
	++str;
	++pat;
	cout << *str << " " << *pat << endl;
}
int main() {
	static const char PAT[] = "*.txt";
	string str = "test.txt";
	Test(str.c_str(), PAT);
	system("pause");
}

 文字リテラルを引数にして受け取ったcharポインタ変数。

*をつけて値を出すと一文字だけなんだなぁ。

++ すると１バイト次へいくのかchar型１つ分行くのかどっちかわからないけど、次の文字のアドレスにいくんだなぁ。

すごいなぁ。

mainでやるとconstかかってるからできない。

関数側だとconst char* で受けてるからポインタのアドレスを変更は出来る。

凄い。

で、まず再帰関数を使わないでやると

bool Match(const char* str, const char* pat) {
	//str pat どちらかが終端に達するまで行う
	for (; !(*str == '\0' || *pat == '\0'); ++str, ++pat) {
		//patの先頭文字がワイルドカードだったら
		if (*pat == '*') {
			//patを次の文字に進めて patとstrの１文字が一致するまで比較
			for (++pat; *pat != *str; ++str) {
				//一致しないままstrが終端まで来たらfalse
				if (*str == '0') {
					return false;
				}
			}
		}
		else {//patが* でなければこっちで比較、違っていればfalse
			if (*pat != *str) {
				return false;
			}
		}
		//ここまで来たらforがstrとpatを一文字ずつ次に行かせる
	}
	//どちらかが終端に達したらここに来る
	return *pat == *str;
}

 ややこしすぎでしょ。

一応ちゃんと答えは出せるけど、例外があって、

*txt

test.txt.txt

これを比較すると、*txtが終端に達したときにtext.txt.txtは終端に来てなくて

*txt は \0

test.txt.txt は . になる。

最後のreturn 分でflase になる。

 のはずなんだけど、テキストがなにいってるか分からない。

 test.txt.txtの一つ目の ' . ' でワイルドカード文字の判定が完全に終了している。

そのため残りのtxt.txt と txt を比較してfalse になってしまう。

ここは言い方の問題だと思う。わかると思う。

次の、

これを回避するには ' . ' 1つだけ見つかるまで無視するんじゃなく

".txt" 全体が見つかるまで無視していく必要がある。

？？？？？？

最後のreturn での判定をなくせば良いんじゃないのかな？

目的があいまいなんだな。俺の。

*.txt 

に一致するということは、.txt が文字列にあれば良いという話じゃなくて

末尾が.txt なのか、ということなのか。

これを再帰関数で達成する

int count = 0;
 
bool Match(const char* str, const char* pat) {
	++::count;
	cout << ::count <<" : " << str << " " << pat << endl;
 
	for (; !(*str == '\0' || *pat == '\0'); ++str, ++pat) {
		if (*pat == '*') {
			for (++pat; ; ++str) {
 
				if (Match(str, pat)) {
					return true;
				}
 
				if (*str == '0') {
					return false;
				}
			}
		}
		else {
			if (*pat != *str) {
				return false;
			}
		}
	}
	return *pat == *str;
}
//output
1 : test.txt.txt *.txt
2 : test.txt.txt .txt
3 : est.txt.txt .txt
4 : st.txt.txt .txt
5 : t.txt.txt .txt
6 : .txt.txt .txt
7 : txt.txt .txt
8 : xt.txt .txt
9 : t.txt .txt
10 : .txt .txt
1

たどればわかる。

だけど、まだ、理解できてない。

あ、そうか再帰呼び出しの引数は呼び出し側の引数と関係ないのか。

outputの６ くらいから最初のマッチングが始まってるのに、どうして' * '  持ってる方の文字が減らないのかと思てたけど。

６でがっつりマッチングして最後のreturn でfalse になったから呼び出しもとにfalseで戻ってきて、だけどそこのstrとpatは無傷なのか。

いやこれ、見ればわかるけど自分で考えるの難しいぞ・・・。

いちおうアドバイスが書いてある。

関数内である処理が必要になった際にその処理がその関数自身で実現できるなら、その関数を呼んでしまえばいい。

そうか！

ここまで。