-2

私は再帰的なプログラミングが苦手です。この問題は簡単だと思いますが、解き方がわかりません。コーディング方法のアイデアが必要です。私を助けてください！

再帰的手法を使用しているときに、値 X がリスト L のメンバーであることを確認する方法は?

4

2 に答える 2

1

非常に大まかな擬似コードですが、このようなものになります。

int checkList(List L, Value X, int current_index)
{
    if ( List.ValueAt(current_index) == X)
    {
        return 1;
    }

    if (List.Length == current_index+1)
    {
        return 0;
    }

    return checkList(L, X, current_index+1);
}

とにかく再帰的である必要があるのはなぜですか？再帰では、戻り情報のために各関数呼び出しをメモリスタックに追加する必要があるため、これを繰り返し行う方がはるかに優れています。

于 2013-10-19T10:04:50.023 に答える
1

再帰を使用して問題を解決するには、「小さい値の答えがわかっている場合、変数 X についての質問にどのように答えるか」という方法を考える必要があります。-あなたの場合-「XがリストLの末尾（最初の要素を除くすべての要素）であるリストKのメンバーであるかどうかをすでに知っている場合、値XがリストLのメンバーであるかどうかをテストするにはどうすればよいですか？ "

例として、別のことを考えてみましょう - 再帰を使用して整数のリストの最大値を取得する方法は?

  1. 1 つの要素リストの最大値はその唯一の要素なので、MAX( [ x ] ) = x
  2. リスト K の最大値がわかっている場合、K と新しい値 x で構成されるリストの最大値は単純に大きい方であることがわかりますMAX( [ x | K ] ) = x if x > MAX(K) or MAX(K) otherwise。どこで | は連結演算なので、[ 1 2 3 ] = [ 1 | [2 3] ]

実行中、そのような再帰はリストの最初の要素を取り、それを残りの最大のものと比較し、単一のリストが見つかるまで再帰的に呼び出します-最大値は簡単に定義できます。これで、同じ方法で問題の解決策を見つけることができます。

于 2013-10-19T10:04:56.457 に答える