新人奮闘記4
- 2016年7月14日
- 未分類, 他の話題, Web Service
今回は、再帰関数を用いて素因数分解をするプログラムを作成してみました。
素因数分解と突然言われると、懐かしかったり、どうだったかな?という事で簡単に計算例だけ紹介しておきます。
素因数分解は自然数を素数の積で表します。
72 ,120をそれぞれ素因数分解すると
のようになります。
今回は、与えられた自然数を2^3 × 3^2のようにハット記号で表すプログラムを書いていきます。
さっそく再帰関数を用いたコードを書いてみました。
$x:素数の初期値 $n:今回のターゲット $c:累乗の値x^c
5行目で関数をコールします。
8行目にて、xがnより大きい時、この関数は終了します。
9~15行目で、実際の計算を行っています。
16行目にて、自分自身をコールしていますが、この時1を加算してコールしています。
これにより、8行目で、関数は終了する事ができます。
7,8,16行目だけ見るとfor文と似た動きである事がわかります。
[基本的なfor文の動作]
初期化->条件式->ステートメント->インクリメント->条件式->ステートメント
[prime_Fact()の動作]
初期化->条件式->ステートメント->インクリメント->初期化->条件式
再帰呼び出しする時、$x+1,もしくは呼び出し以前に$xを変化させなければ無限ループになってしまう事に注意が必要です。
この条件式と再帰呼び出しの間がn回実行される処理という事になります。
[実行結果]
結果は予定通りですが…
いまいち納得がいきません!
上記コードだと、for文の代わりに関数を使って、関数内部(15行目)でechoを使って出力しています。
5行目にprim_Fact()を実行した場所で出力したいのです。つまり、実行結果を丸ごと返り値としてreturnして関数外部で使いたい。
これを解決しようとした時にハマりました。
それでは単純に関数内部で、結果文字列を貯めこんで、return しちゃえばいいんじゃないの?
という事で
14行目で最初の一度だけ$resを初期化
15行目にて連結を繰り返す。
7行目のreturnで貯め込んだ文字列$resを返す。
4行目にて、返り値を確認しています
コード
[実行結果]
見ての通り$resは未定義扱い、おまけにNULLでreturnされていない事がわかります。
繰り返しの中で最後に一度だけ、return されているはずなのに、、、
そこで、returnはどこに何を返すのか、改めて考えていると、大きな勘違いをしている事に
気がつきました。returnは「呼び出し元へ値を返す」事はわかっていたつもりでした。
上記のコードは、7行目でreturnした値は,4行目に返る事を期待したコードです。
しかし、NULLという結果になっているという事は、4行目の関数には返っていません。
では、7行目のreturnはどこへ返っているのでしょうか。
結論から言うと、16行目のprime_Fact()へ返っていました。
動作を図へ示します。
いままでは、シンプルに6行目から16行目を単に繰り返していると考えてました。
上図のように全く同じ関数ではないと考えると、ロジックは変化し、コードも変化します。
図を踏まえた上でもう一度コードを書きなしてみようと思います。
[実行結果]
14行目で$strに最初の素因数分解の結果2^3が格納され、それを引数にして、次のprime_Fact()へ値を渡しています。
これを繰り返し、7行目のreturnが実行された時、一つ前の関数(呼び出し元)へ15行目へ値が返ります。
最終的に初めて関数をコールした場所(5行目)へ値が返ってくるという仕組みです。
以上、細かな例外処理は、割愛させていただきますが、再帰関数に頼る時には、役にたてばと思います。
keny
admin at 2016年07月14日 10:00:13