Bagaimana untuk Melaksanakan Rekursi Panggilan Ekor untuk Penjumlahan Cekap dalam Python?

Rekursi dalam Python: Panduan Memahami

Fungsi Rekursif untuk Menjumlahkan Senarai Integer

Katakan kita perlu mencipta fungsi rekursif yang dipanggil "listSum" yang mengira jumlah semua integer dalam senarai. Matlamatnya adalah untuk melakukan ini tanpa menggunakan sebarang fungsi terbina dalam. Mula-mula, kita harus memikirkan bagaimana kita boleh menyatakan hasil fungsi itu dari segi dirinya.

Dalam kes ini, kita boleh mendapatkan hasilnya dengan menambah nombor pertama dengan hasil panggilan fungsi yang sama dengan selebihnya elemen dalam senarai. Secara rekursif, ini boleh dinyatakan sebagai:

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6])
                         = 1 + (3 + listSum([4, 5, 6]))
                         = 1 + (3 + (4 + listSum([5, 6])))
                         = 1 + (3 + (4 + (5 + listSum([6]))))
                         = 1 + (3 + (4 + (5 + (6 + listSum([])))))

Kes asas untuk rekursi ialah apabila senarai menjadi kosong, peristiwa yang memerlukan hasil 0. Melaksanakan pendekatan ini dalam kod Python:

<code class="python">def listSum(ls):
    if not ls:
        return 0
    return ls[0] + listSum(ls[1:])</code>

Rekursi Panggilan Ekor

Pelaksanaan sebelumnya bergantung pada nilai panggilan fungsi sebelumnya untuk mengira hasil sebenar. Ini boleh diperbaiki menggunakan Tail Call Recursion:

<code class="python">def listSum(ls, result):
    if not ls:
        return result
    return listSum(ls[1:], result + ls[0])</code>

Dengan memperkenalkan hasil parameter tambahan, kami mengumpul jumlah di dalamnya dan mengembalikannya apabila syarat asas dipenuhi.

Indeks Melewati Sekitar

Untuk mengelak daripada mencipta berbilang senarai perantaraan, kita boleh menghantar sekitar indeks item yang akan diproses:

<code class="python">def listSum(ls, index, result):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

Syarat asas menyemak sama ada indeks telah mencapai panjang senarai.

Versi Fungsi Dalaman

Untuk memudahkan penghantaran parameter, kita boleh menggunakan fungsi dalam:

<code class="python">def listSum(ls):
    def recursion(index, result):
        if index == len(ls):
            return result
        return recursion(index + 1, result + ls[index])
    return recursion(0, 0)</code>

Rekursi fungsi dalam menerima parameter indeks dan hasil, dan listSum mengembalikan hasil daripada memanggil fungsi dalam dengan nilai awal.

Versi Parameter Lalai

Menggunakan parameter lalai ialah pemudahan selanjutnya:

<code class="python">def listSum(ls, index=0, result=0):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

Nilai lalai diberikan kepada indeks dan keputusan jika tidak dinyatakan secara eksplisit oleh pemanggil.

Masalah Kuasa Rekursif

Pertimbangkan masalah pengiraan kuasa(asas, eksponen), yang mengembalikan nilai asas yang dinaikkan kepada kuasa eksponen. Secara rekursif, kita boleh mentakrifkan penyelesaian:

power(2, 5) = 2 * power(2, 4)
            = 2 * (2 * power(2, 3))
            = 2 * (2 * (2 * power(2, 2)))
            = 2 * (2 * (2 * (2 * power(2, 1))))

Keadaan asas ialah apabila eksponen menjadi 1 atau kurang, yang mana hasilnya ialah pangkalan itu sendiri:

            = 2 * (2 * (2 * (2 * 2)))
            = 2 * (2 * (2 * 4))
            = 2 * (2 * 8)
            = 2 * 16
            = 32

Pelaksanaan dalam Python :

<code class="python">def power(base, exponent):
    if exponent <= 1:
        return base
    return base * power(base, exponent - 1)</code>

Menggunakan parameter lalai untuk versi Tail Call Optimized:

<code class="python">def power(base, exponent, result=1):
    if exponent <= 0:
        return result
    return power(base, exponent - 1, result * base)</code>

Atas ialah kandungan terperinci Bagaimana untuk Melaksanakan Rekursi Panggilan Ekor untuk Penjumlahan Cekap dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!