Rekursi
Prosedur atau fungsi mungkin mengandungi panggilan ke prosedur lain di dalamnya. Termasuk, subrutin boleh memanggil dirinya sendiri. Dalam kes ini, komputer tidak peduli. Dia juga, seperti biasa, secara konsisten melaksanakan perintah yang dia temui dari atas ke bawah.
Jika anda ingat matematik, maka di sana anda boleh bertemu prinsip aruhan matematik. Ia adalah seperti berikut:
beberapa pernyataan adalah benar untuk setiap n semula jadi jika
1. ia sah untuk n = 1 dan
2. daripada kesahihan pernyataan untuk sebarang n = k semula jadi sewenang-wenangnya ia mengikuti bahawa ia adalah benar untuk n = k + 1.
Dalam pengaturcaraan, teknik ini dipanggil rekursi.
Rekursi adalah satu cara untuk mentakrifkan set objek dari segi set itu sendiri, berdasarkan yang diberikan kes asas mudah.
Rekursif ialah prosedur (fungsi) yang memanggil dirinya secara langsung atau melalui prosedur dan fungsi lain.
Contoh
def Rec(a):
jika (a>0): Rec(a-1)
cetak(a)
Secara skematik, kerja rekursi boleh diwakili oleh carta alir
Prosedur Rec() dilaksanakan dengan parameter 3. Kemudian, di dalam prosedur dengan parameter 3, prosedur dengan parameter 2 dipanggil, dan seterusnya, sehingga prosedur dengan parameter 0 dipanggil. Apabila prosedur dengan parameter 0 dipanggil, panggilan rekursif tidak akan berlaku lagi dan prosedur dengan parameter 0 akan mencetak nombor 0 dan keluar. Kemudian kawalan dipindahkan kembali ke prosedur dengan parameter 1, ia juga menyelesaikan kerjanya dengan mencetak nombor 1, dan seterusnya. sebelum prosedur dengan parameter 3.
Semua prosedur yang dipanggil disimpan dalam ingatan sehingga mereka menyelesaikan kerja mereka. Bilangan prosedur serentak dipanggil kedalaman rekursi.
|
Rekursi sebagai penggantian gelung
Kami telah melihat bahawa rekursi ialah pelaksanaan berulang arahan yang terkandung dalam subrutin. Dan ini, pada gilirannya, adalah serupa dengan kerja kitaran. Terdapat bahasa pengaturcaraan di mana binaan gelung tidak hadir sama sekali. Contohnya, Prolog.
Mari cuba meniru kerja gelung untuk.
Gelung for mengandungi pembolehubah pembilang langkah. Dalam subrutin rekursif, pembolehubah sedemikian boleh diluluskan sebagai parameter.
# Prosedur LoopImitation() dengan dua parameter
# Parameter pertama – pembilang langkah, parameter kedua – jumlah bilangan langkah
def LoopImitation(i, n):
print("Hello N", i) # Pernyataan yang perlu diulang untuk sebarang nilai i
jika saya < n: # Sehingga pembilang gelung sama dengan nilai n,
LoopImitation(i + 1, n) # panggil contoh baru prosedur,
# dengan parameter i+1 (pergi ke nilai seterusnya i)
|
Rekursi dan lelaran
Untuk memahami rekursi, anda perlu memahami rekursi...
Lelaran dalam pengaturcaraan - satu langkahproses pemprosesan data kitaran.
Selalunya algoritma berulang pada langkah semasa (lelaran) menggunakan hasil operasi atau tindakan yang sama yang dikira pada langkah sebelumnya. Satu contoh pengiraan sedemikian ialah pengiraan perhubungan berulang.
Contoh mudah nilai rekursif ialah faktorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Pengiraan nilai pada setiap langkah (lelaran) ialah \(N=N \cdot i\) . Apabila mengira nilai \(N\), kami mengambil nilai yang telah disimpan \(N\).< br />
Faktorial nombor juga boleh diterangkan menggunakan formula berulang:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)
Anda mungkin perasan bahawa penerangan ini tidak lebih daripada fungsi rekursif.
Di sini baris pertama (\(n <= 1\)) ialah huruf asas (syarat penamatan rekursi) dan baris kedua ialah peralihan ke langkah seterusnya.
| Fungsi faktorial rekursif |
Algoritma lelaran |
|
def Faktorial(n):
jika n > 1:
kembali n * Faktorial(n - 1)
lain:
pulangkan 1
|
x=1
untuk i dalam julat(1, n + 1):
x = x * i;
|
Perlu difahami bahawa panggilan fungsi melibatkan beberapa overhed tambahan, jadi pengiraan faktorial bukan rekursif akan menjadi lebih pantas sedikit.
Kesimpulan:di mana anda boleh menulis program dengan algoritma berulang yang mudah, tanpa rekursi, maka anda perlu menulis tanpa rekursi. Namun begitu, terdapat kelas masalah yang besar di mana proses pengiraan dilaksanakan hanya dengan rekursi.
Sebaliknya, algoritma rekursif selalunya lebih mudah difahami.
Tugas
Dalam abjad bahasa puak «Tumba-Yumba» empat huruf: "K", "L", "M" dan "N". Ia adalah perlu untuk memaparkan pada skrin semua perkataan yang terdiri daripada n huruf yang boleh dibina daripada huruf abjad ini
Masalahnya ialah masalah kekerasan biasa yang boleh dikurangkan kepada masalah yang lebih kecil.
Kami akan menggantikan huruf secara berurutan untuk perkataan itu.
Kedudukan pertama perkataan boleh menjadi salah satu daripada 4 huruf abjad ( K, L, M, N).
Mula-mula, letakkan huruf ' K' dahulu. Kemudian, untuk mendapatkan semua varian dengan huruf pertama ' K', anda perlu menghitung semua kemungkinan gabungan huruf dalam baki n-1 kedudukan dan .dll. (lihat gambar)
Oleh itu, kami menghasilkan penyelesaian rekursif: dalam gelung, pergi melalui semua huruf pertama yang mungkin (meletakkan setiap huruf abjad secara bergilir-gilir di tempat pertama) dan untuk setiap kes bina semua kemungkinan "ekor"; panjang n-1.
Lelaran rekursif aksara
Anda perlu menghentikan rekursi dan mengeluarkan perkataan siap apabila bahagian yang tinggal kosong (n = 0), i.e. semua huruf sudah dipilih.
Prosedur rekursif akan kelihatan seperti ini:
def TumbaWords(perkataan, abjad, n):
jika n < 1:
cetak(perkataan)
kembali
untuk c dalam abjad:
TumbaWords(perkataan+c, abjad, n - 1)
|
|