Hayato式！！　　応用情報技術者試験　　　　　　　　　～～アルゴリズム編その3～～

1⃣　再帰

～～そもそも再帰とは？～～

再帰とは、別名リカーシブといい、あるプログラムを実行すると、プログラム中でそのプログラム自身を呼び出すということ。このような構造を持つプログラムを再帰的プログラムという。

①　再帰の概念

再帰の概念は基本的に自然数の階乗で説明することが多い。
ｎ（ｎ≧１）の階乗はｎ！と表し、再帰を用いて定義するとｎ！を表すのに（ｎー１）！を使用して定義する。これは、ｎの値が違うだけで同じプログラムを使うことができることを示しています。

②　分割統治

分割統治は、再帰の特殊な形態で、解くべき問題をいくつかの部分に分けて、各部分の問題の答えをまとめることで全体の答えを出そうとする考え方。分割統治と再帰を組み合わせたアルゴリズムとしてマージソートや、クイックソートなどがあります。

2⃣　文字列探索アルゴリズム

～～文字列探索とは？～～

文字列探索と葉、文字列の中に指定された文字列があるかを調べる探索のこと。以下に各探索方法の種類を紹介していく。

①　力任せ法

これは文字列を探索するのに、配列の先頭から順次1文字ずつずらしながら比較していく方法です。

②　BM法

指定された文字列の右側から比較していく方法。一致した場合はそこで終了するが、不一致だった場合、比較範囲の右端の文字によってスキップする文字数を変えることがある。