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

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

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

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

データ構造

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

ループ

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

再帰

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

Python

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

解決済

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

sequelanonymous
sequelanonymous

総合スコア123

アルゴリズム

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

データ構造

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

ループ

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

再帰

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

Python

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

2回答

0リアクション

1クリップ

735閲覧

投稿2021/09/19 06:59

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

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

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

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

ーーーー

再帰関数に書き換えたいコード
(合計値がtargetと同等のユニークな組み合わせを出力するコード)

python

def combination_sum(candidates, target): outputs = [[]] results = [] for c in candidates: tmps = [] for output in outputs: while target >= sum(output): # >=にするのは、targetと同じものを含めて、後で取り出す、という考えがあるから。 tmps.append(output.copy()) output.append(c) if sum(output) == target: # ターゲットと同じリストを保持する -> backtrackingの条件1 results.append(output.copy()) outputs = tmps # リストの更新(2のみの組み合わせ, 2,3の組み合わせ、2,3,6の組み合わせ....) -> backtrackingの条件2 return results if __name__ == "__main__": candidates = [2,3,6,7] target = 7 print(combination_sum(candidates, target))

アウトプット

shell

$ python backtracking.py [[2, 2, 3], [7]]

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

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

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

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

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

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

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
86.12%

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

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

質問する

関連した質問

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

アルゴリズム

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

データ構造

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

ループ

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

再帰

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

Python

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