1

私は「コンピューター科学者のように考える方法」を研究しており、現在、再帰を把握しようとしています。私は問題の1つに問題を抱えているので、あなたが私を助けてくれることを願っています。

私は、要素が整数、整数のリスト、整数のリストのリストなどであるリストの再帰的最小値を見つける関数を書いています。

これが私の現在のバージョンです：

def recursive_min(nested_num_list):
    """
      >>> recursive_min([9, [1, 13], 2, 8, 6])
      1
      >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
      1
      >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
      -7
      >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
      -13
    """
    min = nested_num_list[0]
    while type(min) == type([]):
        min = min[0]
    for item in nested_num_list:
        if type(item) == type([]):
            recursive_min(item)
        elif item < min:
            min = item
    return min

ただし、これはトップレベルで最小値を見つけるためにのみ機能するため、コードがリストの深部に到達していません。

さて、答えを見ると、私のバージョンは次のようになっているはずです。

def recursive_min(nested_num_list):
    """
      >>> recursive_min([9, [1, 13], 2, 8, 6])
      1
      >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
      1
      >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
      -7
      >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
      -13
    """
    min = nested_num_list[0]
    while type(min) == type([]):
        min = min[0]
    for item in nested_num_list:
        if type(item) == type([]):
            min_of_elm = recursive_min(item)
            if min_of_elm < min:
                min = min_of_elm
        elif item < min:
            min = item
    return min

recursive_min（item）を実行するだけでなく、それを変数に割り当て、現在の最小値と比較することに注意してください。私の考えのように、埋め込まれたリストに対して関数全体を実行し、それが整数のリストである場合、なぜそれを行う必要があるのか​​わかりません。その後、ifステートメントではなくelifステートメントに到達する必要があります。 ）そして値を適切に比較します。

私はここで再帰について何かが欠けているに違いないことを知っています。2番目のバージョンが機能するのに、最初のバージョンが失敗する理由を理解するのに役立つ洞察をいただければ幸いです。

ありがとうございました！

4

2 に答える 2

2

なぜうまくいくのでしょうか？関数を呼び出すと、min が見つかるまで再帰します。次に、それは何をしますか？トップレベルに戻るまで、すべての再帰を順番に終了します。その時点で、 の値はmin? 再帰関数からの戻り値を取得していないため、再帰を開始する前とまったく同じです。

関数の各呼び出しには独自のローカル変数があることを忘れないでください。したがって、独自のローカル値min.

于 2012-05-15T18:41:51.237 に答える
0

この問題を解決するには多くの方法があります。個人的には、ループやローカル変数を使用せずに、リストの再帰のみを使用する、より機能的なアプローチを好みます。これは確かに問題を解決するための最も効率的な方法ではありませんが、シンプルでエレガントです。

def recursive_min(num_list):
    return aux_min(num_list[1:], num_list[0]) if num_list else None

def aux_min(num_list, min_num):
    if not num_list:
        return min_num
    elif not isinstance(num_list, list):
        return min(num_list, min_num)
    else:
        return min(aux_min(num_list[0],  min_num),
                   aux_min(num_list[1:], min_num))

上記のコードでは、メイン関数はrecursive_min、ヘルパー関数を呼び出すaux_minです。次に、aux_minリストと現在の最小値を受け取り、問題を 3 つのケースに分割します。

  1. リストが空の場合、現在の最小値を返します
  2. リストではなく数値の場合、数値と現在の最小値の間の最小値を返します
  3. リストの場合、最初の要素と残りのリストの間の最小値を再帰的に返します

3番目のケースでは、最初の要素がリスト自体になる可能性があるため、リストのリストに対して機能します。

于 2012-05-15T19:17:57.450 に答える