再帰がわからない
せきさん
(No.1)
再帰がわかるようになりません。
出るとこだけ！の５章の解説を読んでもさっぱりです。
例題の5-2の問題はmodとか数字が入ってるのでなんとなくわかって正解できたのですが図や解説を読んでも再帰の考え方がそもそもわかるようになりません。
なぜ自身が繰り返しになるのか？というところがわかりません。
過去問で出てきてもこの問題は再帰だと気づけませんでした。
考え方はどうしたら身につくでしょうか。
出るとこだけ！の５章の解説を読んでもさっぱりです。
例題の5-2の問題はmodとか数字が入ってるのでなんとなくわかって正解できたのですが図や解説を読んでも再帰の考え方がそもそもわかるようになりません。
なぜ自身が繰り返しになるのか？というところがわかりません。
過去問で出てきてもこの問題は再帰だと気づけませんでした。
考え方はどうしたら身につくでしょうか。
2024.09.02 14:07
まーぼさん
★FE シルバーマイスター
(No.2)
再帰のイメージがしやすいようにちょっと現実に近いところでの再帰の話をします。
プログラミング言語のPHPが何の略かご存知でしょうか？PHPのWikipediaには下記のように説明されています。
ちょっと小難しく書かれていますが、要は
PHPは”P”HP “H”ypertext “P”reprocessorの略でPHPの最初のPはPHPのことを指し、そのPHPの最初のPもPHPのことを指し、…と無限ループに陥ってしまうということです。再帰のプログラムを書くとよく無限ループに陥るのは、「再帰の終了条件を記述していないため」です。
少し現実での再帰の例を見て、再帰関数が無限ループするイメージを持てましたでしょうか。
プログラミング言語のPHPが何の略かご存知でしょうか？PHPのWikipediaには下記のように説明されています。
> 名称の PHP は再帰的頭字語として、 "PHP: Hypertext Preprocessor" を意味するとされており、「PHPはHTMLのプリプロセッサである」とPHP自身を再帰的に説明している。
ちょっと小難しく書かれていますが、要は
PHPは”P”HP “H”ypertext “P”reprocessorの略でPHPの最初のPはPHPのことを指し、そのPHPの最初のPもPHPのことを指し、…と無限ループに陥ってしまうということです。再帰のプログラムを書くとよく無限ループに陥るのは、「再帰の終了条件を記述していないため」です。
少し現実での再帰の例を見て、再帰関数が無限ループするイメージを持てましたでしょうか。
2024.09.02 16:34
かなりM氏さん
(No.3)
ヒントになるかは解りませんが、私が再帰を学んだ時は「ハノイの塔」というパズルをイメージしました。
アプリもあるはずですし、脳内やノートの切れ端でも出来るのでお暇な時にやってみて下さい。
アプリもあるはずですし、脳内やノートの切れ端でも出来るのでお暇な時にやってみて下さい。
2024.09.02 18:23
GinSanaさん
★FE シルバーマイスター
(No.4)
例えば、Javaで不特定階層のディレクトリ配下のをzip化する際には、ファイルなら圧縮して、ディレクトリならそのパスで再帰的に入って行ってファイルを探しに行って、ということをする。このときの再帰の終了条件は、ディレクトリがそれ以上存在しない、ということになる。
実際に動かしてみればわかるかもしれない。
※参考：Java ZipOutputStreamを使って、フォルダを丸ごとZIPファイルに圧縮する | javalife
public static void compressEntry(Path targetPath, String parentDirName, ZipOutputStream zos) throws IOException {
//ディレクトリ内のディレクトリ、ファイルを取得
try (DirectoryStream<Path> ds = Files.newDirectoryStream(targetPath)) {
for (Path filePath : ds) {
if (Files.isDirectory(filePath)) {
//ディレクトリの場合、再帰的に処置
compressEntry(filePath, parentDirName + "/" + filePath.getFileName(), zos);
} else {
//ファイルの場合、 圧縮
ZipEntry zipEntry = new ZipEntry(parentDirName + "/" + filePath.getFileName().toString());
zos.putNextEntry(zipEntry);
try(FileInputStream fis = new FileInputStream(filePath.toFile());
BufferedInputStream bis = new BufferedInputStream(fis);){
byte[] buffer = new byte[BUFFER_SIZE];
int len = -1;
while ((len = bis.read(buffer, 0, buffer.length)) != -1) {
zos.write(buffer, 0, len);
}
}
zos.closeEntry();
}
}
}
}
compressEntryだと、targetPathの直下しか参照しないので、再帰的にこのメソッドを呼ぶことで深堀りしていくことになる。//ディレクトリ内のディレクトリ、ファイルを取得
try (DirectoryStream<Path> ds = Files.newDirectoryStream(targetPath)) {
for (Path filePath : ds) {
if (Files.isDirectory(filePath)) {
//ディレクトリの場合、再帰的に処置
compressEntry(filePath, parentDirName + "/" + filePath.getFileName(), zos);
} else {
//ファイルの場合、 圧縮
ZipEntry zipEntry = new ZipEntry(parentDirName + "/" + filePath.getFileName().toString());
zos.putNextEntry(zipEntry);
try(FileInputStream fis = new FileInputStream(filePath.toFile());
BufferedInputStream bis = new BufferedInputStream(fis);){
byte[] buffer = new byte[BUFFER_SIZE];
int len = -1;
while ((len = bis.read(buffer, 0, buffer.length)) != -1) {
zos.write(buffer, 0, len);
}
}
zos.closeEntry();
}
}
}
}
実際に動かしてみればわかるかもしれない。
※参考：Java ZipOutputStreamを使って、フォルダを丸ごとZIPファイルに圧縮する | javalife
2024.09.02 18:50
adkさん
(No.5)
再帰は計算量が多くなるから難しく感じやすいので、めちゃめちゃ簡単な問題をやった方がいいと思います。
FE本番レベルはゴリゴリ計算しまくるのでけっこう辛いです。
FE本番レベルはゴリゴリ計算しまくるのでけっこう辛いです。
2024.09.03 09:34
masatoyさん
(No.6)
関数を分解して数字に置き換える方法をおすすめします。
例えば、
F(a, b){
a + bを返す
}
という関数があった場合、F(1, 2)は「3」に置き換えることができますよね。
ここで再帰処理を持つ
F(a){
a + F(a - 1)を返す
}
を同じ要領で置き換えてみます。例えばF(3)であれば、
F(3)を「3 + F(2)」に置き換えられます。続いて、F(2)を置き換えてみます。
F(2)は「2 + F(1)」になり、さっきの計算式に当てはめると、「3 + 2 + F(1)」となります。続いて、F(1)を置き換えてみます。
F(1)は「1 + F(0)」になり、さっきの計算式に当てはめると、「3 + 2 + 1 + F(0)」となります。
これを繰り返すことで再帰処理の結果を導き出せますが、このままでは
3 + 2 + 1 + 0 + F(-1)
3 + 2 + 1 + 0 + -1 + F(-2)
3 + 2 + 1 + 0 + -1 + -2 + F(-3)
︙
と、無限ループに入ってしまい、答えを導き出すことができません。
多くの場合、無限ループにならないように再帰を止める条件が書かれています。
ここで再帰を止める条件を追加した関数Fを記述してみます。
F(a){
a = 1 なら
1 を返す
でなければ
a + F(a - 1)を返す
}
この内容でF(3)をもう一度置き換えてみます。
F(3)を置き換えます。引数aは1ではないので、F(3)は「3 + F(2)」になります。
F(2)を置き換えます。引数aは1ではないので、F(2)は「2 + F(1)」となり、さっきの計算式に当てはめると、「3 + 2 + F(1)」となります。
F(1)を置き換えます。引数aは1なので、F(1)は「1」となり、さっきの計算式に当てはめると、「3 + 2 + 1」となります。
こうしてF(3)は6を返すことがわかります。
問題に出てくるものはもう少し複雑になっていますが、紙に書くなどして細かく分解すれば、確実に再帰処理の結果を求められます。
例えば、
F(a, b){
a + bを返す
}
という関数があった場合、F(1, 2)は「3」に置き換えることができますよね。
ここで再帰処理を持つ
F(a){
a + F(a - 1)を返す
}
を同じ要領で置き換えてみます。例えばF(3)であれば、
F(3)を「3 + F(2)」に置き換えられます。続いて、F(2)を置き換えてみます。
F(2)は「2 + F(1)」になり、さっきの計算式に当てはめると、「3 + 2 + F(1)」となります。続いて、F(1)を置き換えてみます。
F(1)は「1 + F(0)」になり、さっきの計算式に当てはめると、「3 + 2 + 1 + F(0)」となります。
これを繰り返すことで再帰処理の結果を導き出せますが、このままでは
3 + 2 + 1 + 0 + F(-1)
3 + 2 + 1 + 0 + -1 + F(-2)
3 + 2 + 1 + 0 + -1 + -2 + F(-3)
︙
と、無限ループに入ってしまい、答えを導き出すことができません。
多くの場合、無限ループにならないように再帰を止める条件が書かれています。
ここで再帰を止める条件を追加した関数Fを記述してみます。
F(a){
a = 1 なら
1 を返す
でなければ
a + F(a - 1)を返す
}
この内容でF(3)をもう一度置き換えてみます。
F(3)を置き換えます。引数aは1ではないので、F(3)は「3 + F(2)」になります。
F(2)を置き換えます。引数aは1ではないので、F(2)は「2 + F(1)」となり、さっきの計算式に当てはめると、「3 + 2 + F(1)」となります。
F(1)を置き換えます。引数aは1なので、F(1)は「1」となり、さっきの計算式に当てはめると、「3 + 2 + 1」となります。
こうしてF(3)は6を返すことがわかります。
問題に出てくるものはもう少し複雑になっていますが、紙に書くなどして細かく分解すれば、確実に再帰処理の結果を求められます。
2024.09.03 09:51
あるごさん
(No.7)
「再帰関数」とは、「同じ関数」を呼んでいるだけです。
下記の関数は、問5-2のプログラムをコピーして関数名を変えただけのプログラムです。
関数：f(775, 527)を実行したときのトレースはできますか？
できるなら「f10」で記載しているところが
再帰関数の場合は、「f」になりますので表現として「自分自身を繰り返し」呼んでいることになります。
（関数：f50は、エラーにならないように仮で記載しただけなので意味はあまりありません。）
もし、読めない場合は、関数の読み方から復習したほうが良いと思います。
（関数の呼び方、returnの戻り値）
[プログラム]
〇整数型：f(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f10(y, x mod y)
endif
〇整数型：f10(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f20(y, x mod y)
endif
〇整数型：f20(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f30(y, x mod y)
endif
〇整数型：f30(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f40(y, x mod y)
endif
〇整数型：f40(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f50(y, x mod y)
endif
〇整数型：f50(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return x
endif
頑張ってください。
下記の関数は、問5-2のプログラムをコピーして関数名を変えただけのプログラムです。
関数：f(775, 527)を実行したときのトレースはできますか？
できるなら「f10」で記載しているところが
再帰関数の場合は、「f」になりますので表現として「自分自身を繰り返し」呼んでいることになります。
（関数：f50は、エラーにならないように仮で記載しただけなので意味はあまりありません。）
もし、読めない場合は、関数の読み方から復習したほうが良いと思います。
（関数の呼び方、returnの戻り値）
[プログラム]
〇整数型：f(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f10(y, x mod y)
endif
〇整数型：f10(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f20(y, x mod y)
endif
〇整数型：f20(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f30(y, x mod y)
endif
〇整数型：f30(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f40(y, x mod y)
endif
〇整数型：f40(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return f50(y, x mod y)
endif
〇整数型：f50(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return x
endif
頑張ってください。
2024.09.04 12:09
あるごさん
(No.8)
もし、「 return f(y, x mod y)」の１行で「関数を呼んでreturnで戻す」行が
理解しにくい場合用に「２行で戻り値を変数に代入する」バージョンも作ってみました。
処理している内容は、同じです。
[プログラム]
〇整数型：f(整数型：x, 整数型：y)
整数型：a
if (yが0と等しい)
return x
else
a = f10(y, x mod y)
return a
endif
〇整数型：f10(整数型：x, 整数型：y)
整数型：b
if (yが0と等しい)
return x
else
b = f20(y, x mod y)
return b
endif
〇整数型：f20(整数型：x, 整数型：y)
整数型：c
if (yが0と等しい)
return x
else
c = f30(y, x mod y)
return c
endif
〇整数型：f30(整数型：x, 整数型：y)
整数型：d
if (yが0と等しい)
return x
else
d = f40(y, x mod y)
return d
endif
〇整数型：f40(整数型：x, 整数型：y)
整数型：e
if (yが0と等しい)
return x
else
e = f50(y, x mod y)
return e
endif
〇整数型：f50(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return x
endif
頑張ってください。
理解しにくい場合用に「２行で戻り値を変数に代入する」バージョンも作ってみました。
処理している内容は、同じです。
[プログラム]
〇整数型：f(整数型：x, 整数型：y)
整数型：a
if (yが0と等しい)
return x
else
a = f10(y, x mod y)
return a
endif
〇整数型：f10(整数型：x, 整数型：y)
整数型：b
if (yが0と等しい)
return x
else
b = f20(y, x mod y)
return b
endif
〇整数型：f20(整数型：x, 整数型：y)
整数型：c
if (yが0と等しい)
return x
else
c = f30(y, x mod y)
return c
endif
〇整数型：f30(整数型：x, 整数型：y)
整数型：d
if (yが0と等しい)
return x
else
d = f40(y, x mod y)
return d
endif
〇整数型：f40(整数型：x, 整数型：y)
整数型：e
if (yが0と等しい)
return x
else
e = f50(y, x mod y)
return e
endif
〇整数型：f50(整数型：x, 整数型：y)
if (yが0と等しい)
return x
else
return x
endif
頑張ってください。
2024.09.04 12:26
あるごさん
(No.9)
トレース結果
順番に関数が呼び出される。
・ f(775, 527)
・ f10(527, 248)
・ f20(248, 31)
・ f30(31, 0)
ここから戻る
[f30]
yが0なのでreturn で戻り値：31(x)でf20に移動する
[f20]
戻り値：31がcに代入されreturn でf10に移動する
[f10]
戻り値：31がbに代入されreturn でfに移動する
[f]
戻り値：31がaに代入され処理が終了する。
順番に関数が呼び出される。
・ f(775, 527)
・ f10(527, 248)
・ f20(248, 31)
・ f30(31, 0)
ここから戻る
[f30]
yが0なのでreturn で戻り値：31(x)でf20に移動する
[f20]
戻り値：31がcに代入されreturn でf10に移動する
[f10]
戻り値：31がbに代入されreturn でfに移動する
[f]
戻り値：31がaに代入され処理が終了する。
2024.09.04 12:27
pixさん
(No.10)
僭越ながら私も再帰のイメージについて解説いたします。
プログラムは以下の3つの要素からできています。
・順次 順番にプログラムを実行すること
・選択 条件分岐、いわゆるif
・反復 繰り返し、いわゆるwhile
この中で反復であるwhileはプログラムのもっとも得意とする動作です。
極端な話、世の中のプログラムのアルゴリズムの95%はこの反復を使えば
解決できます。
しかし残りの5%のアルゴリズムは反復を使うよりも効果的に問題を解決する
方法があります。それが再帰です。
再帰は使える場面が非常に限られますが、最適な箇所でつかえば、反復よりも
スッキリとしたプログラムになります。
再帰と反復とは根本的に処理が違います。
反復は同じことを繰り返す掛け算のイメージです。
しかし、再帰は特殊です。どちらかというと変則的な足し算のイメージです。
自分自身と似ているが、少し小さい計算が多数必要な場合に威力を発揮します。
再帰は自分自身の分身を産みます。この分身は自分よりも一回り小さいです。
いわば自分自身の子供です。また、その子供がまた子供を産みます。
イメージとしてはロシアのマトリョーシカ人形のように入れ子になってるような
ものです。
そうして生まれた分身が一斉に計算を行います。
その結果を最後に足すことによって、結果を求めます。
ネタばらしになりますが、再帰のプログラムも多少工夫すれば、反復の
プログラムに書き換え可能です。
ですが、再帰と反復のプログラムを比較した場合、反復よりも再帰のほうが
数学的観点からスッキリしたアルゴリズムとなっています。
FEで再帰を学ぶのはどちらかというと、教養としてそういうものがあるという
ことが理解できれば十分と思われます。
プログラムは以下の3つの要素からできています。
・順次 順番にプログラムを実行すること
・選択 条件分岐、いわゆるif
・反復 繰り返し、いわゆるwhile
この中で反復であるwhileはプログラムのもっとも得意とする動作です。
極端な話、世の中のプログラムのアルゴリズムの95%はこの反復を使えば
解決できます。
しかし残りの5%のアルゴリズムは反復を使うよりも効果的に問題を解決する
方法があります。それが再帰です。
再帰は使える場面が非常に限られますが、最適な箇所でつかえば、反復よりも
スッキリとしたプログラムになります。
再帰と反復とは根本的に処理が違います。
反復は同じことを繰り返す掛け算のイメージです。
しかし、再帰は特殊です。どちらかというと変則的な足し算のイメージです。
自分自身と似ているが、少し小さい計算が多数必要な場合に威力を発揮します。
再帰は自分自身の分身を産みます。この分身は自分よりも一回り小さいです。
いわば自分自身の子供です。また、その子供がまた子供を産みます。
イメージとしてはロシアのマトリョーシカ人形のように入れ子になってるような
ものです。
そうして生まれた分身が一斉に計算を行います。
その結果を最後に足すことによって、結果を求めます。
ネタばらしになりますが、再帰のプログラムも多少工夫すれば、反復の
プログラムに書き換え可能です。
ですが、再帰と反復のプログラムを比較した場合、反復よりも再帰のほうが
数学的観点からスッキリしたアルゴリズムとなっています。
FEで再帰を学ぶのはどちらかというと、教養としてそういうものがあるという
ことが理解できれば十分と思われます。
2024.09.04 12:41
まーぼさん
★FE シルバーマイスター
(No.11)
イメージだけで実例を出せていなかったので、補足させていただきます。
例えば、引数で自然数nを受け取り、2のn乗を返す関数を見てみます。
以下Pythonでの関数定義の例です。
for文での実装
再帰関数での実装
どちらも同じ結果を返しますが、考え方が違います。
for文は、「1に2をn回掛けると2のn乗が求まる」
対して再帰関数は、「2の(n-1)乗が分かっている前提なら、それに2を掛けると2のn乗が求まる」
です。
例えば、引数で自然数nを受け取り、2のn乗を返す関数を見てみます。
以下Pythonでの関数定義の例です。
for文での実装
def twoPowerNByForStatememt(n):
ret = 1
for i in range(n):
ret = ret * 2
return ret
ret = 1
for i in range(n):
ret = ret * 2
return ret
再帰関数での実装
def twoPowerNByRecursiveFuncton(n):
if n == 0:
return 1
return twoPowerNByRecursiveFuncton(n-1) * 2
if n == 0:
return 1
return twoPowerNByRecursiveFuncton(n-1) * 2
どちらも同じ結果を返しますが、考え方が違います。
for文は、「1に2をn回掛けると2のn乗が求まる」
対して再帰関数は、「2の(n-1)乗が分かっている前提なら、それに2を掛けると2のn乗が求まる」
です。
2024.09.04 17:06
広告
返信投稿用フォーム
スパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。
広告