[解決済み] 再帰とヘルパー関数

質問

私は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 

解決方法は？

通常、私がこのようなことをするのは、再帰的な関数がトリッキーだったり、呼び出すのが面倒だったりするので、より便利なラッパーを用意するためです。 例えば、迷路ソルバー関数を想像してください。 再帰的関数は迷路内の訪問スポットを追跡するためのデータ構造を必要としますが、呼び出し側の利便性を考えて、呼び出し側は解くべき迷路を渡すだけで良いようにします。 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)

原文から編集してみましたが、実はかなり合理的な例になっていますね。 引数を整数にする("duck typing")のですが、そのために != 演算子は、この強制によって値が変更されたことを示さない。 int は値を変更します（例えば float の値が小数部分を切り捨てていた場合、その引数は拒否されます。 同様に、負の値をチェックし、引数を拒否する。 そうすると、実際の再帰的関数は非常に信頼性が高く、チェックを全く行わない。

この質問のきっかけとなった、あなたが見たコードの例を載せていただければ、曖昧な答えにならないのですが。

EDIT: わかりました、あなたの例について議論します。

• 例1: (再帰を用いたリンクリストの反転)

非常にシンプルです。quot;helper" 関数は、リンクリストを持つクラス内のすべてのノードで動作する一般的な再帰関数です。 そしてラッパーは、リンクリストを見つける方法を知っているメソッド関数です。 self.head リストの先頭である このquot;helper"はクラスのメンバー関数ですが、一般的なデータ構造もののライブラリの簡単な関数でもかまいません。 (というのは、このような関数は、リンクリストが forward をその次のポインタの値として使用します。 つまり、これを一度書いておけば、リンクリストを実装している複数のクラスで使うことができるわけです)。

• 例2: (バイナリサーチツリー)

実際の再帰的関数は None を指定したノードが見つからない場合は key . そして に ラッパーを実装しています。 __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つのラッパーを書くだけで、正しい位置からスタートすることができます。 シンプルに。