Q&A
コードの中を見てない一般論ですが、方法としては、「一旦ループで書いたコードを再帰に変換する」のでなく、「最初から問題を再帰的な発想で考える」ほうが良いと思います。
下記のコードを再帰関数に書き換えたいのですが、どのような手順を踏んで再帰に書き換えることが考えられますでしょうか？
私がいつも再帰を実装するときに踏んでいる手順では、フィボナッチ数列や簡単な順列の問題での再帰呼び出しが一つの場合には、有効なのですが、下記の重複したループを考えるときには、すんなりとはいきません。
なにかお気づの点ありましたらご教示いただけませんしょうか？
私がいつも踏んでいる手順は下記です。
ーーーー
- ループがある箇所を再帰にできそうか否か。
- 再帰にできるループが何個あるか。
- 再帰にできるループの数だけ、base caseを考える。
- それぞれのループの終了条件を確認し、それをbase caseとして実装する。
- base caseに向かって再帰で呼び出す関数の引数にどんな値を渡せばいいかを考える
- 再帰で呼び出す関数の実行前に引数にわたす値を計算するコードを実装
ーーーー
再帰関数に書き換えたいコード
(合計値がtargetと同等のユニークな組み合わせを出力するコード)
python
1def combination_sum(candidates, target): 2 outputs = [[]] 3 results = [] 4 for c in candidates: 5 tmps = [] 6 for output in outputs: 7 while target >= sum(output): # >=にするのは、targetと同じものを含めて、後で取り出す、という考えがあるから。 8 tmps.append(output.copy()) 9 output.append(c) 10 if sum(output) == target: # ターゲットと同じリストを保持する -> backtrackingの条件1 11 results.append(output.copy()) 12 outputs = tmps # リストの更新(2のみの組み合わせ, 2,3の組み合わせ、2,3,6の組み合わせ....) -> backtrackingの条件2 13 return results 14 15if __name__ == "__main__": 16 candidates = [2,3,6,7] 17 target = 7 18 print(combination_sum(candidates, target))
アウトプット
shell
1$ python backtracking.py 2[[2, 2, 3], [7]]
日本人が英会話を勉強するときに、二つの考え方があります。
(1) 日本語での会話を瞬時に英語に翻訳して話そうとする。
(2) 英語で考えて英語で話そうとする。
(1)でまともに英会話するのは現実問題として無理です。
おはようございます = Good morning
こんにちは = Good afternoon
こんばんは = Good evening
では、11時にあいさつするときは？
とか考えていては会話になりませんね。
Good morning ： May you have a good morning
と理解していれば、そしてmorningはsunriseからnoonまでだと理解していれば、瞬時に反応できますし応用も利きます。
これと同じように、CでプログラミングするときはCで考え、PythonでプログラミングするときはPythonで考え、再帰でプログラミングするときは再帰で考えるのが楽ですし実用的です。
私は良く再帰のコードを書きますが、その理由は再帰で考える方が楽で、短い時間でコードが書けるからです。しかし、再帰コードは実行性能が悪い(遅い)ことが多いので、性能を気にするときは、最初からループで書きます。
ループで書いたコードを元に再帰コードを作るというのは意味がありませんし効率が悪いと思います。
> 下記のコードを再帰関数に書き換えたいのですが
なぜ書き換えなければならないのでしょうか（どのような要件を実現するために、再帰で書くことが必要となったのでしょうか）？
> maisumakun
確認ありがとうございます。他の方も同じような疑問が浮かぶかと思いましたので、質問の背景を詳細に下記に記載しておきます。
上記のようなコードを再帰実装する上での処理ステップを言語化して人にわかりやすく説明できるようになるため、もしくはより汎用的な説明を見つけるために、わざわざfor-loopから再帰で書こうとしています。
まずは、for-loopを実装して、それから再帰に書き換えてみましょう、という説明の仕方が一番クリアで実装前の実装後を比較しながら対応付けをしつつ理解しやすいと思ったからです。
最初から再帰を実装しろ、という教え方は、誰にでも通じる説明の仕方ではない一方で、for-loopはわりと手続的に理解ができ、処理ステップが理解しやすので、手続的に理解してから命題的に課題を解く、っていう考え方のほうがいいかなと思っています。
仮に最初から再帰的に解けと言われた瞬間に手続的に踏む処理ステップがblack boxになり、ある数式を途中式をかかず説明せずにこれで動くんです、自明である、的な説明で終始しがちになります。その思考癖だとデバックはもとい、これはこうだから動く、なんとく私のローカル環境では動くから正しい、のような思考癖になります。
で、その説明をする上で、上記のようなループがいれくんだ複雑なコードになった瞬間、手続的→命題的に、for-loop→recursionのステップでの理解がしづらくなってきた気がしましたので、どう説明及び言語化したらいいだろうか、というのが質問の背景になります。
もし、手続的→命題的に、for-loop→recursionのステップでの理解がそもそもこの問題に対して適切でない場合は、どうしてそうなのか、や最初から命題的に考える方が楽であれば、楽な理由も気になっています。
> 上記のようなコードを再帰実装する上での処理ステップを言語化して人にわかりやすく説明できるようになるため、もしくはより汎用的な説明を見つけるために、わざわざfor-loopから再帰で書こうとしています。
他の人の回答にもありますが、「再帰は再帰で考える」ほうが妥当なコードを書けます。（再帰しか使えない言語でやるためなら別ですが）forから書き直すのでは、再帰で書くメリットがなにもないコードを生み出すだけになります。
> 「再帰は再帰で考える」ほうが妥当なコードを書けます
ありがとうございます。その場合、上記のような問題を初見で見て、何を基準に最初から再帰で考えるべき、っていう考えになりますでしょうか？私は、まずはfor-loopでとけるかどうかを考えましたので。
というのもどんな問題が再帰でとけるかどうかを知るには、ある前提知識が必要(例えば公式を知ってるとか、一回解いた事がある問題とか)だと思っていて、その前提知識がない場合は解くことができない、ってことになってしまいそうでして。
> 私は、まずはfor-loopでとけるかどうかを考えましたので。
「再帰で解く」という条件が与えられた状況でもないのでしたら、それで構わないのではないでしょうか？
性能やメモリ消費など、必要な条件を満たすのであれば、プログラミングはどんな処理で進めても構わないものです。
> というのもどんな問題が再帰でとけるかどうかを知るには、ある前提知識が必要(例えば公式を知ってるとか、一回解いた事がある問題とか)だと思っていて、その前提知識がない場合は解くことができない、ってことになってしまいそうでして。
理論的には、再帰もループもチューリング完全（書けるプログラムの範囲は同じ）です。プログラミング言語やライブラリ由来の制約がない状況であれば、「どちらかでないと絶対に書けない」ものはありません。
もともとのこの質問の意図が解くことが目的というより、再帰を理解するために例として上のコードと問題を選んで記載しているに過ぎないです。
再帰で正解解答が知りたいとかは、本質的な目的ではないです。
どちらでも解けるのはわかっていまるんですが、上記のようなコードの場合のfor-loopからrecursionへの書き換えの処理ステップやどうしてそう判断したのかが知りたいのが当質問の意図になります。質問のタイトルに書かれてる通りだと思いますが。
> 質問のタイトルに書かれてる通りだと思いますが。
タイトルと本文が合っていない印象です。
> 上記のようなコードの場合のfor-loopからrecursionへの書き換えの処理ステップやどうしてそう判断したのかが知りたいのが当質問の意図になります。
「実用的でなくてもいいから機械的にやるやり方を知りたい」、ということで間違いないでしょうか？
なぜ、そうおもいましたでしょうか？どう直したらいいとおもいますでしょうか？
> 実用的でなくてもいいから
この実用的の定義が難しいですが、再帰を理解するためには実用的だと思っています。
そもそも、再帰自体が、関数型言語やlamudaを使わない限り、可読性・保守性の点からプロダクトに実装するような書き方ではないという意味で実用的だとは言えないと思うので。
この質問の意図は、タイトル通り、ただ単にfor-loopからrecursionへの書き換えの際のわかりやすい処理ステップが知りたいにすぎないです。
というのも、ちまたにある書籍や記事では、再帰を扱う場合、すごく簡単な例題、フィボナッチなハノイの塔のような題材しか扱っていないので。
> 再帰を理解するためには実用的だと思っています。
ここの点から理解が一致していません。for loopで書けば素直に書けるものを機械的に再帰で書き直したところで、再帰の理解につながるものではないと考えます。
> そもそも、再帰自体が、関数型言語やlamudaを使わない限り、可読性・保守性の点からプロダクトに実装するような書き方ではないという意味で実用的だとは言えないと思うので。
「再帰的下向き構文解析」とアルゴリズム名から「再帰」と入っているような、再帰で実装するほうがきれいに実装できるアルゴリズムもあります。あとは、HTMLツリーやディレクトリツリーなど、データ構造自体が再帰的になっているものをハンドリングする場合にも再帰で書くほうが素直な実装となりえます。
> for loopで書けば素直に書けるものを機械的に再帰で書き直したところで、再帰の理解につながるものではないと考えます。
そう考える理由はなんでしょうか？きになります。
>「再帰的下向き構文解析」とアルゴリズム名から「再帰」と入っているような、再帰で実装するほうがきれいに実装できるアルゴリズムもあります。
しってます。
> そう考える理由はなんでしょうか？きになります。
逆に、「どのように役に立つ」とお考えなのでしょうか？（どう役に立つのかが何1つ想像できないので、「役に立たない」としか判断できない状態です）
> しってます。
そういうアルゴリズムだけ再帰で書けばいい、というのが自分としての考えです。
> そういうアルゴリズムだけ再帰で書けばいい
既知である場合を前提としてると思いますが、未知の課題に対して、どうやって対応しますか？
> 逆に、「どのように役に立つ」とお考えなのでしょうか？
下記に書いてあるとおりです。すでに投稿済みです。
> まずは、for-loopを実装して、それから再帰に書き換えてみましょう、という説明の仕方が一番クリアで実装前の実装後を比較しながら対応付けをしつつ理解しやすいと思ったからです。
最初から再帰を実装しろ、という教え方は、誰にでも通じる説明の仕方ではない一方で、for-loopはわりと手続的に理解ができ、処理ステップが理解しやすので、手続的に理解してから命題的に課題を解く、っていう考え方のほうがいいかなと思っています。
仮に最初から再帰的に解けと言われた瞬間に手続的に踏む処理ステップがblack boxになり、ある数式を途中式をかかず説明せずにこれで動くんです、自明である、的な説明で終始しがちになります。その思考癖だとデバックはもとい、これはこうだから動く、なんとく私のローカル環境では動くから正しい、のような思考癖になります。
せっかくここまでコメント頂いてるので言いづらいことではありますが、
このサイトを使っている目的は、特にディベートをしたり、論破をしたいわけではありません。お困りごとを解決したいだけなので、再帰への書き換えがわからない、処理ステップがわからないのであれば無視していただいても構わないです。コメント頂いた事自体に関しては、感謝しています、ありがとうございます。
> 手続的に理解してから命題的に課題を解く、っていう考え方のほうがいいかなと思っています。
そんな考え方を辿らせること自体が教育的に意味があるのか、という段階で疑問なのです。
> お困りごとを解決したいだけなので
その「困りごと」と考えていること自体が、実はすでに脱線しているのではないか、というのが自分としての考えですが、これ以上続けても平行線をたどるだけなので、このあたりにしようかと思います。
フィボナッチ数列の説明は再帰で定義されていますが、実際にはループで行う方が効率よく数列を作成できます。
再帰を使う場合はメモ化を考えなければいけません。
機械的に変換しようとすると、かえって煩雑になるでしょう。
つまり相互に変換可能とはいえ、これは別のアルゴリズムなんですよ。
ループ脳で再帰関数を書こうとしたり、再帰脳でループを書こうとすると、かえって難しくなります。
フィボナッチを再帰で求める場合、ループとは逆の順番で処理が呼ばれるため、ループ脳でこれを書こうとすると、変換のために余計なことを色々と考えなくてはならなくなります。
再起関数を難しいと感じる人は、ループから変換しようとするから難しく感じるんだと思いますよ。
「同じ名前で同じ処理の関数を呼ぶだけで、他の関数を呼ぶのと何一つ変わらない」と最初から考えていれば、なんのことはありません。
他人のお困りごとを解決したいのであれば、まず自分がその問題を理解していないといけないと思いますが、このような質問をしている段階で、理解していると言えるでしょうか？
再帰関数はブラックボックスでもなんでもありません。
ただの関数呼び出しです。
もしそれがブラックボックスに見えているとすれば、それは単にそう見えている人が、何かの固定観念に目をふさがれて、正しく理解できていないだけなのではないかと疑ってみてください。
回答2件
0
ベストアンサー
通常、事前条件などはコード化されません。コメントに書かれればいいところで、プログラムの一部として表明(アサーション)されることは稀です。今回のコードにも、「ここを見ればわかるでしょ」といえるほど明確に示してる部分があるとは思いません。
ではなぜこれが重要なのかというと、これを理解することがコードを理解することだと思ってるからです。特に強調したいのが、これは再帰だとか関係なく、コードの読み書き全般において重要だと考えているということです。
例えば、ソースコードが与えられたときに紙と鉛筆を使って同じ処理を行えることも理解してるといえる状況の一つです。しかし、ふつうはこれを理解してるとは言わないでしょう。それぞれのコードがどういう役割を果たして、どう関係しているのかがわからなければ理解したとは言えません。
それさえわかってしまえば再帰関数への書き換えは大きく進みます。あとは、その役割を再帰関数で行うにはどうしたらいいのか、完全に同じ役割の再帰関数でないのならほかの役割をどう変えなきゃいけないのか、これを考えるだけですから。
コメントを見ていて気になったのは手続き的には理解できると言ってるところで、きちんと理解しようと思ったら手続き的だろうがそれなりに大変です。逆に手続き的なコードのほうが本質的ではない部分が入り込みやすいので理解しづらいことすらあります。
たとえば今のコードでも、tmpsのような典型的な一時変数は言語の都合上置かれてるだけで理解する上では冗長なだけです。
一番内側のwhileループ中でresultsに追加している部分も同様です。resultsに追加している部分がない場合このwhileループの役割は__「outputにcを0個以上追加したもののうち合計がtarget以下のものをtmpsに入れる」ことで、resultsに追加する部分を付け加えることで**「outputにcを0個以上追加したもののうち合計がtarget以下のものをtmpsに入れる + outputにcを1個以上追加したもののうち合計がtargetになるものをresultsに入れる」__になります。
なんでtmpsに入れるのが「0個以上追加したもの」で、resultsに入れるのが「1個以上追加したもの**」なんでしょう? あんまり深入りしませんがややこしくないですか? 実はresultsへの追加はここでやる必要はないのでこんなこと考えないようにすることも可能なんです。ありうる組み合わせを列挙してその中から合計がちょうどtargetになるものを選び出すと考えれば、むしろループが終わってからoutputsから合計がちょうどになるものを抜き出すほうが自然です。そういう意味ではこのwhileループは手続き型のコードにありがちな、分離可能な処理を一つのループで同時に行っている状態です。
そんなこともあって、別にループで書かれてるからと言って理解する難しさにはそんなに差がないのにループなら理解できると思っているのは、ループのコードに関しては深く追及してないんじゃないかと思ってしまいます。
再帰で書いたコードの全体です。Pythonの言語仕様に詳しくないので同名の関数がどう扱われてるのかわかりませんが、とりあえず期待通り動いてるのでそのまま貼ります。appendの呼び出しはすべてここで定義しているappendを呼び出しているつもりです。
Python
1def append(combination: List[int], value: int) -> List[List[int]]: 2 if sum(combination) > target: #base case すでにtargetを超えていたら組み合わせは存在しない 3 return [] 4 5 return [combination] + append(combination + [value], value) # valueを一つも追加しない組み合わせと一つ以上追加したものの和集合 6 7def rec(i: int) -> List[List[int]]: 8 if i == len(candidates): 9 return [[]] #使える要素がないので、何も選ばない組み合わせしかない 10 11 return [appended for combination in rec(i + 1) for appended in append(combination, candidates[i])] #i + 1以降を使う組み合わせ(combination)それぞれに対してcandidates[i]を0個以上追加したもので合計がtarget以下のもの 12 13return [combination for combination in rec(0) if sum(combination) == target]
少し話はそれますが「事前条件」「事後条件」「(ループ)不変条件」という考え方になじみはありますか?
再帰関数に限らず、複雑なアルゴリズムを扱う上で必須の考え方です。もしあまり気にしてこなかったなら、意識してほしいと思います。質問者さんのいつもの手順がこういった考えと違ってあまりに機械的に思えたので強調のため先頭に書きました。
さて本題の再帰関数ですが試しに以下の再帰関数での置き換えをします。
def append(combination, value): combination(組み合わせ)にvalueを0以上追加したもので合計がtarget以下のものを重複なくすべて返す
def rec(i): candidatesのi番目以降の要素を使った組み合わせで合計がtarget以下のものを重複なくすべて返す
まずappendは
Python
1def append(combination: List[int], value: int) -> List[List[int]]: 2 if sum(combination) > target: #base case すでにtargetを超えていたら組み合わせは存在しない 3 return [] 4 5 return [combination] + append(combination + [value], value) # valueを一つも追加しない組み合わせと一つ以上追加したものの和集合 6
とかけます。気を付けなければいけないのは、base caseの正しさと、append(combination + [value], value)が正しい結果を返した場合にappend(combination, value)が正しい結果を返すかということです。
次にrecを考えると
Python
1def rec(i: int) -> List[List[int]]: 2 if i == len(candidates): 3 return [[]] #使える要素がないので、何も選ばない組み合わせしかない 4 5 return [appended for combination in rec(i + 1) for appended in append(combination, candidates[i])] #i + 1以降を使う組み合わせ(combination)それぞれに対してcandidates[i]を0個以上追加したもので合計がtarget以下のもの 6
と書けます。appendと同様に、base caseの正しさと、rec(i + 1)が正しい結果を返した場合にrec(i)も正しい結果を返すかに気を付ける必要があります。
最後にrec(0)から合計が一致するものだけ選び出せばほぼ同質のの関数が出来上がります。
次に、ループバージョンで書かれていたものを見てみます。
for c in candidates: の各イテレーションの先頭で、outputsはcより前の要素を使った合計がtarget以下の組み合わせです。ただし最初のループでは使える要素がないので何も選ばない組み合わせしかありません。そして各イテレーションの最後ではoutputsはcとcより前の要素を使った合計がtarget以下の組み合わせです。
なぜそう言えるかというと、cより前の要素を使った組み合わせそれぞれに対して(for output in outputs:)、合計がtarget以下になるような(target >= sum(output):)、cを0個以上追加した組み合わせを求めてる(tmps.append(output.copy()); output.append(c))からです。この処理は、outputsがcより前の要素を使った合計がtarget以下の組み合わせであるとき、cとcより前の要素を使った合計がtarget以下の組み合わせを列挙できます。
こうしてみると今回のコードに関しては、再帰で書こうがループで書こうが考えなければいけないことは対して違いがなくて、ループ/再帰だからというような難しさはあまりないように思います。それでもそこがなかなかはっきりしないのは「事前条件」「事後条件」「(ループ)不変条件」といったことに意識が向いてないからじゃないかと思います。
投稿2021/09/19 12:54
編集2021/09/20 08:28
総合スコア2047
コメントありがとうございます。
今回の質問であげたコードでいうと、「事前条件」「事後条件」「(ループ)不変条件」がそれぞれどの部分にあたり、それぞれが意識していないとなぜできないかの理由、もしくはどうそれぞれの言葉と実装コードを結びつけて理解できるのかをご教示いただけませんでしょうか？
教科書的な意味は知っているのものの、それぞれの言葉がどう実装ステップを明白に言語化する上で必要になってくるかどうかが気になっています。もし再帰関数を実装するために役立ちそうな言葉であれば、積極的に使っていこうと思いました。
また、もしよろしければ、ご回答頂いたコード全体をくっつけて記載頂けませんでしょうか？
というのも`append`は、pythonの標準モジュールで同じ関数名で`append`を実装し直してるかと思うのですが、ちょっとrec(恐らくrecursionに書き換えた関数？！)関数との関係について間違って理解しそうな気がしましたので。
解答の更新ありがとうございます。
結局のところ、記載していただいたコードで「事前条件」「事後条件」「(ループ)不変条件」がそれぞれどの部分にあたりますでしょうか？また、各コード箇所に対して一言でいうとそれぞれ、どういった条件になりますか？
「事前条件」：xxxx
「事後条件」：yyyy
「(ループ)不変条件」：zzzz
そこがまだ、しっくりきていない状態です。
append
「事前条件」：append(combination + [value], value)が正しい結果を返す
「事後条件」：append(combination, value)が正しい結果を返す
rec
「事前条件」：rec(i + 1)が正しい結果を返す
「事後条件」：rec(i)が正しい結果を返す
もっと細分化することは可能ですが、コアになるのはこれです。それぞれの関数における正しい結果が具体的に何かということは前のほうに書いてあります。
すみません、理解できそうで、できないので「事前条件」「事後条件」「(ループ)不変条件」について理解する記事かなにか参考になりそうなリソース教えていただけませんでしょうか？
事前条件と事後条件の違いが混乱してきました。
理解しやすいかどうかは人それぞれなので何とも言えませんが、「事前条件」や「事後条件」でググるより「ホーア論理」でググったほうが役に立つ情報が見つけやすいと思います。
ありがとうございます。もう少し関数プログラミングやプログラミング仕様書論あたりについて教科書をあさってみます。
0
ループは機械的に再帰にできますが、多分これは求めている解ではないでしょう。
Python
1def combination_sum(candidates, target): 2 outputs = [[]] 3 results = [] 4 def f1(i): 5 if i < len(candidates): 6 c = candidates[i] 7 tmps = [] 8 nonlocal outputs 9 def f2(i): 10 if i < len(outputs): 11 output = outputs[i] 12 def f3(): 13 if target >= sum(output): 14 tmps.append(output.copy()) 15 output.append(c) 16 if sum(output) == target: 17 results.append(output.copy()) 18 f3() 19 f3() 20 f2(i+1) 21 f2(0) 22 outputs = tmps 23 f1(i+1) 24 f1(0) 25 return results 26 27if __name__ == "__main__": 28 candidates = [2,3,6,7] 29 target = 7 30 print(combination_sum(candidates, target))
追記
forループを再帰にする方法
python
1a = [11, 22, 33, 44] 2 3for e in a: 4 print(e) 5print('---') 6 7for i in range(len(a)): 8 e = a[i] 9 print(e) 10print('---') 11 12def f(i): 13 if i < len(a): 14 e = a[i] 15 print(e) 16 f(i+1) 17f(0) 18print('---')
whileループを再帰にする方法
python
1a = [] 2i = 1 3while sum(a) < 10: 4 print(i, a) 5 a.append(i) 6 i += 1 7print('---') 8 9a = [] 10def f(i): 11 if sum(a) < 10: 12 print(i, a) 13 a.append(i) 14 i += 1 15 f(i) 16f(1) 17print('---')
投稿2021/09/19 13:44
編集2021/09/20 04:38
総合スコア8224
> ループは機械的に再帰にできますが、多分これは求めている解ではないでしょう。
コメントありがとうございます。
むしろ、私には、この実装がおもいつかなかったので、どういうふうに機械的に実装したのかがきになります
あなたの回答
tips
プレビュー
