1

私はPythonの再帰を学んでいます。各ノードに item と next があるリンク リストを定義します。奇数と偶数を別々のセットに入れる再帰を書きたいです。

class LinkNode(object):
"""A node in a linked list."""

def __init__(self, item, next=None):
    """(LinkNode, object, LinkNode) -> NoneType
    Initialize this node to store item and next.
    """
    self.item = item
    self.next = next

def odd_or_even(self):
    """(LinkNode) -> ([object], [object])
    Return a pair of lists: (odd number, even number.
    """
    if self is None:
        return ([], [])
    else:
        if (self.item % 2 == 1):
            odd_num = odd_num.append(self.item)
        else:
            even_num = even_num.append(self.item)
    if self.next is not None:
        self.next.odd_or_even()
    return (odd_num, even_num)

実行すると、次のエラーが発生しました。

ファイル "C:\Program Files\Wing IDE 101 4.1\src\debug\tserver_sandbox.py"、19 行目、odd_or_even builtins.UnboundLocalError: 割り当て前に参照されるローカル変数 'odd_num'

上書きされないようにするには、odd_num、even_num をどこで初期化する必要がありますか?

ありがとう。

4

2 に答える 2

0 
    if (self.item % 2 == 1):
        odd_num = odd_num.append(self.item)
    else:
        even_num = even_num.append(self.item)
...
return (odd_num, even_num)

上記のコードセクションでは、またはのいずれかの値を設定しますが、odd_num両方の値を設定することはできeven_numません。odd_num次に、との両方を返そうとしeven_numますが、どちらか一方にエラーが発生します。両方をNoneそのステートメントの直前に初期化するifと、発生したエラーを回避できます。ただし、セマンティクスを機能させるには、関数に別のパラメーター、つまり前のレベルの結果を追加する必要がある場合があります。再帰呼び出しでは、計算されたばかりodd_numまたはeven_num次のレベルに渡します。次に、次のレベルの結果を返します。ただし、再帰を避け、代わりに2回実行されるループを使用する方がよい場合があります。

于 2013-03-04T02:01:38.790 に答える
0

使用できるいくつかの異なるアプローチがあると思います。

1 つは、グローバル変数を使用することです。これはあまりお勧めしませんが、わかりやすいので最初に紹介します。

even_num = [] # these should be at module level, but I'm not showing the class
odd_num = []  # so you'll have to imagine the indentation being correct

def odd_or_even(self):
    """(LinkNode) -> ([object], [object])
    Return a pair of lists: (odd number, even number.
    """
    if self.item % 2 == 1:
        odd_num.append(self.item)
    else:
        even_num.append(self.item)

    if self.next is not None:
        self.next.odd_or_even()

コードへの変更はマイナーで、主にreturnステートメントを削除するだけです。selfであることの最初のチェックを行いましたNone。これは、メソッドでは決して不可能であるためです (呼び出し元がそれを実現しようと非常に懸命に努力しない限り)。すでに存在するグローバル変数にアクセスするのではなく、ローカル変数を作成するため、odd_numまたは直接に代入しようとしないことにも注意してください。even_numこのソリューションの欠点は、一度しか呼び出せずodd_or_even、正しく動作させることができることです。再度 (おそらく別のリストで) 呼び出したい場合は、グローバル変数を再初期化する必要があります。

これは、ローカル変数として偶数リストと奇数リストを作成し、最後にそれらを返すより良いアプローチです。これはおそらくコードで目指していたものですが、再帰呼び出しの結果をリストに追加する手順がありませんでした。

def odd_or_even(self):
    even_num = []
    odd_num = []

    if self.item % 2 == 1:
        odd_num.append(self.item)
    else:
        even_num.append(self.item)

    if self.next is not None:
        next_even, next_odd = self.next.odd_or_even()
        even_num.extend(next_even)
        odd_num.extend(next_odd)

    return even_num, odd_num

このコードの問題は、リストの作成と拡張が無駄であるということです。再帰の各レベルで、2 つの新しいリストが作成されますが、そのレベルで処理される値は 1 つだけです。より良いアプローチでは、再帰プロセス全体で合計 2 つのリストのみを使用できます。

def odd_or_even(self, lists=None):
    if lists is not None:
        even_num, odd_num = lists
    else:
        even_num = []
        odd_num = []

    if self.item % 2 == 1:
        odd_num.append(self.item)
    else:
        even_num.append(self.item)

    if self.next is not None:
        return self.next.odd_or_even((even_num, odd_num))
    else:
        return even_num, odd_num

これは、再帰のすべてのレベルで同じリストを使用するため、以前のバージョンよりも効率的です。他のいくつかのプログラミング言語では、再帰呼び出しが実行される前にすべての作業が完了するこのスタイルの再帰は、他の種類の再帰よりもはるかに効率的です。これは、コンパイラがreturn関数のステップを最適化して取り除くことができるためです (そして、スタック フレームを再利用するだけです)。ただし、Python はそのような「テール コールの最適化」を行わないため (スタック トレースが台無しになるため)、メリットはそれほど大きくありません。

考慮すべきもう 1 つの点: Python のリストではなく、独自のリンク リスト クラスを使用して、偶数と奇数の値を保持することができます。上に示した 2 番目と 3 番目の解決策はどちらも機能しますが、偶数と奇数の値を逆の順序で返す場合は、3 番目の方法が最も自然に機能します。

于 2013-03-04T03:05:41.550 に答える