質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.60%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

1318閲覧

二重forループとwhileループを組み合わせた関数をどのような手順を踏んで再帰関数に書き換えられるか

sequelanonymous

総合スコア123

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2021/09/19 06:59

下記のコードを再帰関数に書き換えたいのですが、どのような手順を踏んで再帰に書き換えることが考えられますでしょうか?

私がいつも再帰を実装するときに踏んでいる手順では、フィボナッチ数列や簡単な順列の問題での再帰呼び出しが一つの場合には、有効なのですが、下記の重複したループを考えるときには、すんなりとはいきません。
なにかお気づの点ありましたらご教示いただけませんしょうか?

私がいつも踏んでいる手順は下記です。
ーーーー

  1. ループがある箇所を再帰にできそうか否か。
  2. 再帰にできるループが何個あるか。
  3. 再帰にできるループの数だけ、base caseを考える。
  4. それぞれのループの終了条件を確認し、それをbase caseとして実装する。
  5. base caseに向かって再帰で呼び出す関数の引数にどんな値を渡せばいいかを考える
  6. 再帰で呼び出す関数の実行前に引数にわたす値を計算するコードを実装

ーーーー

再帰関数に書き換えたいコード
(合計値が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]]

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

また依頼した内容が修正された場合は、修正依頼を取り消すようにしましょう。

otn

2021/09/19 11:10

コードの中を見てない一般論ですが、方法としては、「一旦ループで書いたコードを再帰に変換する」のでなく、「最初から問題を再帰的な発想で考える」ほうが良いと思います。
ppaul

2021/09/19 23:58 編集

日本人が英会話を勉強するときに、二つの考え方があります。 (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

2021/09/20 02:41

> 下記のコードを再帰関数に書き換えたいのですが なぜ書き換えなければならないのでしょうか(どのような要件を実現するために、再帰で書くことが必要となったのでしょうか)?
sequelanonymous

2021/09/20 03:05

> maisumakun 確認ありがとうございます。他の方も同じような疑問が浮かぶかと思いましたので、質問の背景を詳細に下記に記載しておきます。 上記のようなコードを再帰実装する上での処理ステップを言語化して人にわかりやすく説明できるようになるため、もしくはより汎用的な説明を見つけるために、わざわざfor-loopから再帰で書こうとしています。 まずは、for-loopを実装して、それから再帰に書き換えてみましょう、という説明の仕方が一番クリアで実装前の実装後を比較しながら対応付けをしつつ理解しやすいと思ったからです。 最初から再帰を実装しろ、という教え方は、誰にでも通じる説明の仕方ではない一方で、for-loopはわりと手続的に理解ができ、処理ステップが理解しやすので、手続的に理解してから命題的に課題を解く、っていう考え方のほうがいいかなと思っています。 仮に最初から再帰的に解けと言われた瞬間に手続的に踏む処理ステップがblack boxになり、ある数式を途中式をかかず説明せずにこれで動くんです、自明である、的な説明で終始しがちになります。その思考癖だとデバックはもとい、これはこうだから動く、なんとく私のローカル環境では動くから正しい、のような思考癖になります。 で、その説明をする上で、上記のようなループがいれくんだ複雑なコードになった瞬間、手続的→命題的に、for-loop→recursionのステップでの理解がしづらくなってきた気がしましたので、どう説明及び言語化したらいいだろうか、というのが質問の背景になります。
sequelanonymous

2021/09/20 03:13 編集

もし、手続的→命題的に、for-loop→recursionのステップでの理解がそもそもこの問題に対して適切でない場合は、どうしてそうなのか、や最初から命題的に考える方が楽であれば、楽な理由も気になっています。
maisumakun

2021/09/20 03:20

> 上記のようなコードを再帰実装する上での処理ステップを言語化して人にわかりやすく説明できるようになるため、もしくはより汎用的な説明を見つけるために、わざわざfor-loopから再帰で書こうとしています。 他の人の回答にもありますが、「再帰は再帰で考える」ほうが妥当なコードを書けます。(再帰しか使えない言語でやるためなら別ですが)forから書き直すのでは、再帰で書くメリットがなにもないコードを生み出すだけになります。
sequelanonymous

2021/09/20 03:26

> 「再帰は再帰で考える」ほうが妥当なコードを書けます ありがとうございます。その場合、上記のような問題を初見で見て、何を基準に最初から再帰で考えるべき、っていう考えになりますでしょうか?私は、まずはfor-loopでとけるかどうかを考えましたので。
sequelanonymous

2021/09/20 03:29

というのもどんな問題が再帰でとけるかどうかを知るには、ある前提知識が必要(例えば公式を知ってるとか、一回解いた事がある問題とか)だと思っていて、その前提知識がない場合は解くことができない、ってことになってしまいそうでして。
maisumakun

2021/09/20 03:29

> 私は、まずはfor-loopでとけるかどうかを考えましたので。 「再帰で解く」という条件が与えられた状況でもないのでしたら、それで構わないのではないでしょうか? 性能やメモリ消費など、必要な条件を満たすのであれば、プログラミングはどんな処理で進めても構わないものです。
maisumakun

2021/09/20 03:37

> というのもどんな問題が再帰でとけるかどうかを知るには、ある前提知識が必要(例えば公式を知ってるとか、一回解いた事がある問題とか)だと思っていて、その前提知識がない場合は解くことができない、ってことになってしまいそうでして。 理論的には、再帰もループもチューリング完全(書けるプログラムの範囲は同じ)です。プログラミング言語やライブラリ由来の制約がない状況であれば、「どちらかでないと絶対に書けない」ものはありません。
sequelanonymous

2021/09/20 03:38 編集

もともとのこの質問の意図が解くことが目的というより、再帰を理解するために例として上のコードと問題を選んで記載しているに過ぎないです。 再帰で正解解答が知りたいとかは、本質的な目的ではないです。 どちらでも解けるのはわかっていまるんですが、上記のようなコードの場合のfor-loopからrecursionへの書き換えの処理ステップやどうしてそう判断したのかが知りたいのが当質問の意図になります。質問のタイトルに書かれてる通りだと思いますが。
maisumakun

2021/09/20 03:43

> 質問のタイトルに書かれてる通りだと思いますが。 タイトルと本文が合っていない印象です。
maisumakun

2021/09/20 03:44

> 上記のようなコードの場合のfor-loopからrecursionへの書き換えの処理ステップやどうしてそう判断したのかが知りたいのが当質問の意図になります。 「実用的でなくてもいいから機械的にやるやり方を知りたい」、ということで間違いないでしょうか?
sequelanonymous

2021/09/20 03:45

なぜ、そうおもいましたでしょうか?どう直したらいいとおもいますでしょうか?
sequelanonymous

2021/09/20 03:53 編集

> 実用的でなくてもいいから この実用的の定義が難しいですが、再帰を理解するためには実用的だと思っています。 そもそも、再帰自体が、関数型言語やlamudaを使わない限り、可読性・保守性の点からプロダクトに実装するような書き方ではないという意味で実用的だとは言えないと思うので。 この質問の意図は、タイトル通り、ただ単にfor-loopからrecursionへの書き換えの際のわかりやすい処理ステップが知りたいにすぎないです。 というのも、ちまたにある書籍や記事では、再帰を扱う場合、すごく簡単な例題、フィボナッチなハノイの塔のような題材しか扱っていないので。
maisumakun

2021/09/20 03:59 編集

> 再帰を理解するためには実用的だと思っています。 ここの点から理解が一致していません。for loopで書けば素直に書けるものを機械的に再帰で書き直したところで、再帰の理解につながるものではないと考えます。 > そもそも、再帰自体が、関数型言語やlamudaを使わない限り、可読性・保守性の点からプロダクトに実装するような書き方ではないという意味で実用的だとは言えないと思うので。 「再帰的下向き構文解析」とアルゴリズム名から「再帰」と入っているような、再帰で実装するほうがきれいに実装できるアルゴリズムもあります。あとは、HTMLツリーやディレクトリツリーなど、データ構造自体が再帰的になっているものをハンドリングする場合にも再帰で書くほうが素直な実装となりえます。
sequelanonymous

2021/09/20 04:00 編集

> for loopで書けば素直に書けるものを機械的に再帰で書き直したところで、再帰の理解につながるものではないと考えます。 そう考える理由はなんでしょうか?きになります。 >「再帰的下向き構文解析」とアルゴリズム名から「再帰」と入っているような、再帰で実装するほうがきれいに実装できるアルゴリズムもあります。 しってます。
maisumakun

2021/09/20 04:08

> そう考える理由はなんでしょうか?きになります。 逆に、「どのように役に立つ」とお考えなのでしょうか?(どう役に立つのかが何1つ想像できないので、「役に立たない」としか判断できない状態です) > しってます。 そういうアルゴリズムだけ再帰で書けばいい、というのが自分としての考えです。
sequelanonymous

2021/09/20 04:19

> そういうアルゴリズムだけ再帰で書けばいい 既知である場合を前提としてると思いますが、未知の課題に対して、どうやって対応しますか? > 逆に、「どのように役に立つ」とお考えなのでしょうか? 下記に書いてあるとおりです。すでに投稿済みです。 > まずは、for-loopを実装して、それから再帰に書き換えてみましょう、という説明の仕方が一番クリアで実装前の実装後を比較しながら対応付けをしつつ理解しやすいと思ったからです。 最初から再帰を実装しろ、という教え方は、誰にでも通じる説明の仕方ではない一方で、for-loopはわりと手続的に理解ができ、処理ステップが理解しやすので、手続的に理解してから命題的に課題を解く、っていう考え方のほうがいいかなと思っています。 仮に最初から再帰的に解けと言われた瞬間に手続的に踏む処理ステップがblack boxになり、ある数式を途中式をかかず説明せずにこれで動くんです、自明である、的な説明で終始しがちになります。その思考癖だとデバックはもとい、これはこうだから動く、なんとく私のローカル環境では動くから正しい、のような思考癖になります。 せっかくここまでコメント頂いてるので言いづらいことではありますが、 このサイトを使っている目的は、特にディベートをしたり、論破をしたいわけではありません。お困りごとを解決したいだけなので、再帰への書き換えがわからない、処理ステップがわからないのであれば無視していただいても構わないです。コメント頂いた事自体に関しては、感謝しています、ありがとうございます。
maisumakun

2021/09/20 04:27

> 手続的に理解してから命題的に課題を解く、っていう考え方のほうがいいかなと思っています。 そんな考え方を辿らせること自体が教育的に意味があるのか、という段階で疑問なのです。 > お困りごとを解決したいだけなので その「困りごと」と考えていること自体が、実はすでに脱線しているのではないか、というのが自分としての考えですが、これ以上続けても平行線をたどるだけなので、このあたりにしようかと思います。
Zuishin

2021/09/20 14:26

フィボナッチ数列の説明は再帰で定義されていますが、実際にはループで行う方が効率よく数列を作成できます。 再帰を使う場合はメモ化を考えなければいけません。 機械的に変換しようとすると、かえって煩雑になるでしょう。 つまり相互に変換可能とはいえ、これは別のアルゴリズムなんですよ。 ループ脳で再帰関数を書こうとしたり、再帰脳でループを書こうとすると、かえって難しくなります。 フィボナッチを再帰で求める場合、ループとは逆の順番で処理が呼ばれるため、ループ脳でこれを書こうとすると、変換のために余計なことを色々と考えなくてはならなくなります。 再起関数を難しいと感じる人は、ループから変換しようとするから難しく感じるんだと思いますよ。 「同じ名前で同じ処理の関数を呼ぶだけで、他の関数を呼ぶのと何一つ変わらない」と最初から考えていれば、なんのことはありません。 他人のお困りごとを解決したいのであれば、まず自分がその問題を理解していないといけないと思いますが、このような質問をしている段階で、理解していると言えるでしょうか? 再帰関数はブラックボックスでもなんでもありません。 ただの関数呼び出しです。 もしそれがブラックボックスに見えているとすれば、それは単にそう見えている人が、何かの固定観念に目をふさがれて、正しく理解できていないだけなのではないかと疑ってみてください。
guest

回答2

1

ベストアンサー

通常、事前条件などはコード化されません。コメントに書かれればいいところで、プログラムの一部として表明(アサーション)されることは稀です。今回のコードにも、「ここを見ればわかるでしょ」といえるほど明確に示してる部分があるとは思いません。

ではなぜこれが重要なのかというと、これを理解することがコードを理解することだと思ってるからです。特に強調したいのが、これは再帰だとか関係なく、コードの読み書き全般において重要だと考えているということです。
例えば、ソースコードが与えられたときに紙と鉛筆を使って同じ処理を行えることも理解してるといえる状況の一つです。しかし、ふつうはこれを理解してるとは言わないでしょう。それぞれのコードがどういう役割を果たして、どう関係しているのかがわからなければ理解したとは言えません。

それさえわかってしまえば再帰関数への書き換えは大きく進みます。あとは、その役割を再帰関数で行うにはどうしたらいいのか、完全に同じ役割の再帰関数でないのならほかの役割をどう変えなきゃいけないのか、これを考えるだけですから。

コメントを見ていて気になったのは手続き的には理解できると言ってるところで、きちんと理解しようと思ったら手続き的だろうがそれなりに大変です。逆に手続き的なコードのほうが本質的ではない部分が入り込みやすいので理解しづらいことすらあります。
たとえば今のコードでも、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
yudedako67

総合スコア2047

sequelanonymous👍を押しています

下記のような回答は推奨されていません。

  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

また依頼した内容が修正された場合は、修正依頼を取り消すようにしましょう。

回答へのコメント

sequelanonymous

2021/09/20 02:21 編集

コメントありがとうございます。 今回の質問であげたコードでいうと、「事前条件」「事後条件」「(ループ)不変条件」がそれぞれどの部分にあたり、それぞれが意識していないとなぜできないかの理由、もしくはどうそれぞれの言葉と実装コードを結びつけて理解できるのかをご教示いただけませんでしょうか? 教科書的な意味は知っているのものの、それぞれの言葉がどう実装ステップを明白に言語化する上で必要になってくるかどうかが気になっています。もし再帰関数を実装するために役立ちそうな言葉であれば、積極的に使っていこうと思いました。 また、もしよろしければ、ご回答頂いたコード全体をくっつけて記載頂けませんでしょうか? というのも`append`は、pythonの標準モジュールで同じ関数名で`append`を実装し直してるかと思うのですが、ちょっとrec(恐らくrecursionに書き換えた関数?!)関数との関係について間違って理解しそうな気がしましたので。
sequelanonymous

2021/09/20 09:36 編集

解答の更新ありがとうございます。 結局のところ、記載していただいたコードで「事前条件」「事後条件」「(ループ)不変条件」がそれぞれどの部分にあたりますでしょうか?また、各コード箇所に対して一言でいうとそれぞれ、どういった条件になりますか? 「事前条件」:xxxx 「事後条件」:yyyy 「(ループ)不変条件」:zzzz そこがまだ、しっくりきていない状態です。
yudedako67

2021/09/20 10:07

append 「事前条件」:append(combination + [value], value)が正しい結果を返す 「事後条件」:append(combination, value)が正しい結果を返す rec 「事前条件」:rec(i + 1)が正しい結果を返す 「事後条件」:rec(i)が正しい結果を返す もっと細分化することは可能ですが、コアになるのはこれです。それぞれの関数における正しい結果が具体的に何かということは前のほうに書いてあります。
sequelanonymous

2021/09/20 13:03

すみません、理解できそうで、できないので「事前条件」「事後条件」「(ループ)不変条件」について理解する記事かなにか参考になりそうなリソース教えていただけませんでしょうか? 事前条件と事後条件の違いが混乱してきました。
yudedako67

2021/09/20 15:07

理解しやすいかどうかは人それぞれなので何とも言えませんが、「事前条件」や「事後条件」でググるより「ホーア論理」でググったほうが役に立つ情報が見つけやすいと思います。
sequelanonymous

2021/09/22 02:25

ありがとうございます。もう少し関数プログラミングやプログラミング仕様書論あたりについて教科書をあさってみます。
guest

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
kazuma-s

総合スコア8222

下記のような回答は推奨されていません。

  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

また依頼した内容が修正された場合は、修正依頼を取り消すようにしましょう。

回答へのコメント

sequelanonymous

2021/09/20 02:23

> ループは機械的に再帰にできますが、多分これは求めている解ではないでしょう。 コメントありがとうございます。 むしろ、私には、この実装がおもいつかなかったので、どういうふうに機械的に実装したのかがきになります
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.60%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

同じタグがついた質問を見る

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。