2019年11月18日ここでは、素数の判定に関する処理を、再帰関数を使って書く方法を考えてみます。この処理は、再帰で書く必要は特にありませんが、再帰について学ぶためにあえて再帰を使っています。コードはC++で書いていきます。与えられたときに、これが素数かどうかを判定する関数を考えてみます。行っていますが、ここでは、再帰を使って書くことを考えます。再帰を使うには、同じ構造でより小さな問題に分解すればいいのでした。今の場合ならどうなるでしょうか。素数かどうかを調べればいい、、、のか?」などと考えてしまうかもしれません。これではうまくいきません。素数かどうかは、関係がないからです。片方が素数で片方が合成数の時もあるし、両方が合成数の時もあるし、両方が素数の場合もありえます。そのため、今回は、どのように問題を分解すればいいのかを少し考える必要があります。絵で見てわかる26のアルゴリズム本書は、アルゴリズムを独学する人のために作りました。学ぶときにはイメージしやすく、復習するときには思い出しやすくなるよう、基本的な26のアルゴリズム+7つのデータ構造をすべてイラストにしています。中に、約数がないことを調べればいいのでした。割り切れない、なら素数だとわかるのでした。この部分であれば再帰で書くことができます。問題を次のように分解する、というアイデアです。割れない」イコールの前と、イコールの後の後半部分が同じ構造をしています。ここを再帰関数で表現します。その時点で素数でないとわかります。調べていけばいいですね。以下のどの整数でも割り切れなかった、ということなので、素数だとわかります。