Python-data-structure-python-recursion

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