Python - Rekursi

Rekursi memungkinkan suatu fungsi memanggil dirinya sendiri. Langkah-langkah kode tetap dieksekusi berulang kali untuk nilai baru. Kami juga harus menetapkan kriteria untuk memutuskan kapan panggilan rekursif berakhir. Dalam contoh di bawah ini kita melihat pendekatan rekursif ke pencarian biner. Kami mengambil daftar yang diurutkan dan memberikan rentang indeksnya sebagai input ke fungsi rekursif.

Pencarian Biner menggunakan Rekursi

Kami menerapkan algoritma pencarian biner menggunakan python seperti yang ditunjukkan di bawah ini. Kami menggunakan daftar item yang dipesan dan mendesain fungsi rekursif untuk memasukkan daftar bersama dengan indeks awal dan akhir sebagai input. Kemudian fungsi pencarian biner memanggil dirinya sendiri hingga menemukan item yang dicari atau menyimpulkan tentang ketiadaannya dalam daftar.

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))

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

2
None