8

これが一般的な質問である場合は申し訳ありませんが、私はPythonの初心者であり、他の人が再帰を使用してコーディングしているのを見ると、メイン関数のヘルパー関数を作成し、それ自体が再帰的なヘルパー関数を呼び出します。

これは、たとえば、関数が自分自身のみを呼び出す最も単純な再帰のケース (リストの合計、階乗) とは少し異なるようです。

おそらく例を使って、誰かがこの手法をより注意深く説明できますか?

とても有難い。

例 1: (再帰を使用してリンクされたリストを逆にする)

def revert_list(self):
    self.head = self._revert_helper(self.head)


def _revert_helper(self, node):
    temp = None
    if node.forward == None: 
        return node
    else:
        temp = self._revert_helper(node.forward)
        node.forward.forward = node
        node.forward = None
    return temp

例 2: (二分探索木)

def __contains__(self, key):
    return self._bstSearch(self._root, key)

# Returns the value associated with the key.
def valueOf(self, key):
    node = self._bstSearch(self._root, key)
    assert node is not None, "Invalid may key."
    return node.value

# Helper method that recursively searches the tree for a target key:
# returns a reference to the Node. This allows 
# us to use the same helper method to implement
# both the contains and valueOf() methods of the Map class.

def _bstSearch(self, subtree, target):
    if subtree is None:  # base case
        return None
    elif target < subtree.key: # target is left of the subtree root
        return self._bstSearch(subtree.left) 
    elif target > subtree.key: # target is right of the subtree root
        return self.bstSearch(subtree.right) 
    else:                      # base case
        return subtree
4

3 に答える 3

7

Python は通常、オプションの引数を使用してその動作をエミュレートできるため、これは実際には他の言語でより頻繁に使用されます。再帰は、ユーザーが提供する必要のない多くの初期引数を取得し、問題を追跡するのに役立つという考えです。

def sum(lst):
    return sumhelper(lst, 0)

def sumhelper(lst, acc):
    if lst:
        acc += lst[0]
        return sumhelper(lst[1:], acc)
    return acc

ここでは、開始パラメーターを 0 に設定するために使用されるため、ユーザーが指定する必要はありません。accただし、Python では、オプションにすることでエミュレートできます。

def sum(lst, acc=0):
    if lst:
        acc += lst[0]
        return sum(lst[1:], acc)
    return acc
于 2013-02-28T06:05:31.183 に答える
4

通常、これを行うときは、再帰関数を呼び出すのが難しいか面倒なので、より便利なラッパーを用意しています。たとえば、迷路ソルバー関数を想像してください。再帰関数には、迷路内の訪問スポットを追跡するためのデータ構造が必要ですが、呼び出し元の利便性のために、呼び出し元が解決するために迷路を渡す必要があるだけです。Python のデフォルト変数でこれを処理できるかもしれません。

私がこれを行ったもう1つの主な理由は、速度です。再帰関数は非常に信頼性が高く、その引数がすべて有効であると想定しています。再帰を全速力で進めます。次に、ラッパー関数は、再帰関数への最初の呼び出しを行う前に、すべての引数を慎重にチェックします。些細な例として、階乗：

def _fact(n):
    if n == 0:   # still need to handle the basis case
        return 1
    return n*_fact(n-1)

def fact(n):
    n0 = int(n)
    if n0 != n:
        raise ValueError("argument must make sense as an int")
    if n < 0:
        raise ValueError("negative numbers not allowed")
    return _fact(n)

これをオリジナルから編集したところ、実際にはかなり合理的な例になりました。引数を整数に強制します (「ダック タイピング」) が!=、この強制によって値が変更されたことを演算子が示さないようにする必要があります。に変換するとint値が変更される場合 (たとえば、float小数部分が切り捨てられた値)、引数は拒否されます。同様に、否定をチェックして引数を拒否します。次に、実際の再帰関数は非常に信頼性が高く、チェックはまったく含まれていません。

この質問に影響を与えたコードの例を投稿していただければ、あいまいな回答を減らすことができます。

編集：さて、あなたの例についての議論。

  • 例 1: (再帰を使用してリンクされたリストを逆にする)

非常に単純です。「ヘルパー」関数は、リンクされたリストを持つクラス内の任意のノードで機能する一般的な再帰関数です。self.head次に、ラッパーは、リストの先頭であるを見つける方法を知っているメソッド関数です。この「ヘルパー」はクラス メンバー関数ですが、一般的なデータ構造ライブラリの単純な関数にすることもできます。(これは、C などの言語よりも Python の方が理にかなっています。このような関数は、forward「次のポインター」値として呼び出されるメンバーを持つクラスである任意のリンク リストで動作する可能性があるためです。リンクされたリストを実装する複数のクラスがあります。)

  • 例 2: (二分探索木)

None指定された でノードが見つからない場合、実際の再帰関数は戻りますkey。それから2 つのラッパーがあり__contains__()ますNone。valueOf()キーが見つからない場合は例外が発生します。コメントにあるように、2 つのラッパーを使用すると、1 つの再帰関数で 2 つの異なる問題を解決できます。

また、最初の例と同様に、2 つのラッパーは特定の場所 (self._rootツリーのルート) で検索を開始します。実際の再帰関数は、ツリー内のどこからでも開始できます。

__contains__()検索するノードのデフォルト引数を使用して実装され、デフォルトが一意の値に設定されている場合、特別な値をチェックし、その場合はルートから開始できます。が__contains__()正常に呼び出されると、一意の値が渡され、再帰関数は特別な場所を調べる必要があることを知ることができますself._root。self._root（デフォルト値はコンパイル時に設定され、その後クラスインスタンスが変更される可能性があるため、デフォルト値として渡すことはできません。そのため、正しく機能しません。）

class UniqueValue:
    pass

def __contains__(self, key, subtree=UniqueValue):
    if subtree is UniqueValue:
        subtree = self._root

    if subtree is None:  # base case
        return None
    elif key < subtree.key: # target is left of the subtree root
        return self.__contains__(key, subtree.left) 
    elif key > subtree.key: # target is right of the subtree root
        return self.__contains__(key, subtree.right) 
    else:                      # base case
        return subtree

ここで示したように実装できると言いましたが、それを好むとは言いませんでした。実際、私は 2 つのラッパー バージョンを好みます。これは少しトリッキーで、再帰呼び出しチェックのたびに時間を浪費してsubtree is UniqueValue. より複雑で時間を無駄にします... 勝利ではありません! 適切な場所で開始する 2 つのラッパーを作成するだけです。単純。

于 2013-02-28T06:03:22.500 に答える
3

私の経験 (および私の経験のみ) から、私はこのスタイルのコーディングを次の場合に使用します。

  1. 再帰は、より大きな関数でのみ役立ちます (あまりお勧めしませんが、私には悪い習慣がいくつかあります)。

  2. 関数の準備が必要ですが、(フラグやその他のスイッチの代わりに) 1 回だけです。

私がそれを使用する1つの方法は、ログの目的で、再ログレベルを回避することです

def _factorial(x):
    x == 0 の場合は 1 を返し、それ以外の場合は x*_factorial(x)

@log #何らかのロギング デコレータ「ログ」を想定
デフォルト階乗(x):
    return _factorial(x)

そうしlogないと、階乗関数の再帰レベルごとに呼び出されますが、これは望ましくない可能性があります。

もう 1 つの使用法は、デフォルト引数を解決することです。

def some_function(x = なし):
    x = x または set() #またはその他
    #何か
    some_function() を返す

x私が実際に必要としているのはデコレータであるか、代替手段である間、すべての反復で falseyかどうかを確認します。

def some_function(x = なし):
   return _some_function(x if x else set())

_some_functionヘルパー関数はどこにありますか。

特に2では、ある程度の自由な抽象化が可能です。何らかの理由で bstsearch を使用したくない場合は、それを他の関数に置き換えることができ__contains__ます (また、別の場所でコードを再利用することもできます)。

于 2013-02-28T06:04:25.070 に答える