Python-再帰

再帰により、関数はそれ自体を呼び出すことができます。コードの修正された手順は、新しい値に対して何度も実行されます。また、再帰呼び出しがいつ終了するかを決定するための基準を設定する必要があります。以下の例では、バイナリ検索への再帰的アプローチを示しています。ソートされたリストを取得し、そのインデックス範囲を再帰関数への入力として指定します。

再帰を使用した二分探索

以下に示すように、Pythonを使用してバイナリ検索のアルゴリズムを実装します。アイテムの順序付きリストを使用し、入力として開始インデックスと終了インデックスとともにリストを取り込む再帰関数を設計します。次に、バイナリ検索関数は、検索されたアイテムが見つかるまで、またはリストにアイテムがないことを確認するまで、自分自身を呼び出します。

def bsearch(list, idx0, idxn, val):

    if (idxn < idx0):
        return None
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value

        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

上記のコードを実行すると、次の結果が得られます。

2
None