3

データ構造とアルゴリズムを学んでいます。再帰を理解するのは特に難しいと思いました。そこで、以下の質問があります。ただし、特定のコードとは関係ありません。

  1. メソッドを実装するとき、いつ/どこで再帰を考慮する必要がありますか?
  2. 一般的なコーディング規約では、単純な繰り返しよりも再帰を優先する必要がありますか?
  3. 再帰の最も可能性のある形式を実際に理解して、必要なときにそれらを考えることができるようにするにはどうすればよいですか? それを学ぶための最良の方法は何ですか？(関連する本やウェブサイトはありますか?) パターンはありますか?

再帰が単純で自然だと思うなら、この質問は非建設的に聞こえるかもしれません。しかし、私にとっては、私の直感とうまく一致しません。どんな助けにも感謝します。

4

4 に答える 4

4

1

データが類似していると見なすことができる場合、問題に対する再帰的な解決策は非常に小さくなります。例えば。sum-treeバイナリ ツリーがあり、定義したすべてのリーフ ノードの合計を取得する場合は、それがリーフ ノードの場合は合計、値はリーフ ノードでない場合は、両方のサブツリーの合計の加算です。 .

これが私のテキストのScheme実装です

(define (sum-tree tree)
  (if (leaf? tree)
      (node-value tree)
      (+ (sum-tree (node-left tree))
         (sum-tree (node-right tree)))))

またはJavaでも同じで、Nodeクラスのメソッドとして定義されています。

public int sum()
{
    if ( isLeaf() )
        return value;
    else
        return left.sum() + right.sum();
}

これに対する反復的な解決策は、長くなり、読みにくくなります。この場合、再帰を優先する必要があります。

2

場合によります。Python や Java でプログラミングしている場合は、末尾再帰がないため、そうすべきではありません。ただし、Scheme では、それが唯一の方法です。あなたの言語が末尾再帰をサポートしている場合、より明確なコードを作成するときに再帰を選択する必要があります。

3

行うことによって学びます。ツールとして再帰を使用するいくつかのアルゴリズムを作成する必要があります。流れがわからない場合は、紙を使用してスタックの流れをたどります。いくつかのSchemeまたは同様の関数型言語を学ぶことは、あなたを大いに助けるかもしれません.

于 2013-09-23T13:45:06.933 に答える
1

最初は、再帰に頭を悩ませるのも大変でした。私が再帰を学んでいたのは、学校でJava. Javaで書くのが煩わしいので、イテレータよりも再帰を使用することが多いことがわかりました。しかし、私は学びRuby、再帰的なメソッドを書くことがどんどん減っていることに気づきました。それから、私は多くの再帰関数を書いていることに気づきましたElixir。Erlang私のポイント？一部のツールは、特定のスタイルで書くことができます。

あなたの質問に答えるために、あなたは再帰を学び始めたばかりなので、それらを深く掘り下げて、できる限りそれらを書くことに慣れるようにすることをお勧めします。

特定のタスクは、再帰を使用した方がはるかに優れています (例: フィボナッチ数列、ツリーのトラバースなど)。単純なループを書く方が良い人もいます。ただし、ループを使用して任意の再帰メソッドを記述できることに注意してください。ただし、場合によっては扱いにくい場合があります。

全体として、再帰は、コツをつかむと、実際にはかなりクールな概念です。

再帰に関連するこの質問を見てください: Erlang 演習、リストの作成

于 2013-09-23T01:59:10.120 に答える
1
  1. 同じことを何度も繰り返す場合は、再帰を使用できます。たとえば、ツリーをトラバースしている場合、再帰メソッドを使用して左または右の子に移動できます。
  2. 私は読みやすい方を選びます。一般に、単純な反復はオーバーヘッドがないため高速になります (再帰にはオーバーヘッドがあり、レベルが深すぎるとスタック オーバーフローが発生する可能性がありますが、単純な反復では発生しません)。しかし場合によっては、再帰関数を書く方が、単純な反復で同等のものを書くよりもはるかに簡単です。
  3. 最初に問題を確認してから、それを解決するために再帰が必要かどうかを判断します。その逆ではありません。どんなアルゴリズムの本でも十分です。おそらく、最初からhttp://en.wikipedia.org/wiki/Recursionを読み直すことができます。そこには再帰に関する簡単な例があり、単純な反復を使用して実装することもできると思います。
于 2013-09-23T01:55:21.210 に答える
1

よく知られている再帰アルゴリズムの研究に行きます。たとえば、階乗計算を実装したり、ツリー内のすべてのパスの長さを取得したりできます。

そうすることで、(うまくいけば) 再帰的アプローチがコードを単純化するのにどのように役立つか、およびこれらの特定のケースでなぜそれが良いアプローチであるかがわかります。これにより、将来のアプリケーションのアイデアが得られる可能性があります:)

于 2013-09-23T13:51:24.747 に答える