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 ialah cara untuk mentakrifkan set objek dari segi set itu sendiri, berdasarkan kes asas mudah yang diberikan.
Rekursif juga akan dipanggil prosedur (fungsi) yang memanggil dirinya secara langsung atau melalui prosedur dan fungsi lain
Contoh prosedur rekursif:
kekosongan statik Rec(int a)
{
jika (a>0) Rec(a-1);
cout << 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 sudah tidak akan berlaku dan prosedur dengan parameter 0 akan mencetak nombor 0 dan ditamatkan. 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.
|
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 buat simulasi operasi gelung for.
Gelung for mengandungi pembolehubah pembilang langkah. Dalam subrutin rekursif, pembolehubah sedemikian boleh diluluskan sebagai parameter.
//LoopImitation() prosedur dengan dua parameter
//Parameter pertama – pembilang langkah, parameter kedua – jumlah bilangan langkah
batal LoopImitation(int i, int n)
{
cout << "Hello N" << i << endl; // Operator akan diulang untuk sebarang nilai i
jika (i < n) //Sehingga pembilang gelung sama dengan nilai n,
{ //panggil contoh baharu prosedur, dengan parameter i+1 (pergi ke nilai seterusnya i)
Tiruan Gelung(i+1, n);
}
}
|
Untuk memahami rekursi, anda perlu memahami rekursi...
Lelaran dalam pengaturcaraan — dalam erti kata yang luas — organisasi pemprosesan data, di mana tindakan diulang berkali-kali, tanpa membawa kepada panggilan kepada diri mereka sendiri (tidak seperti %BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Recursion" >Rekursi). Dalam erti kata sempit — satu langkah proses 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:
Anda mungkin perasan bahawa penerangan ini tidak lebih daripada fungsi rekursif.
Di sini baris pertama ( \(n <= 1\)) — ini ialah kes asas (keadaan akhir rekursi) dan baris kedua ialah peralihan ke langkah seterusnya.
| Fungsi faktorial rekursif akan kelihatan seperti ini |
Bandingkan algoritma untuk mencari faktorial dalam cara biasa bukan rekursif |
|
int Faktorial(int n){
jika (n > 1)
kembali n * Faktorial(n - 1);
lain kembali 1;
}
|
x = 1;
untuk (i = 2; i <= n; i++)
x = x * i;
printf("%d",x);
|
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.
Anda mungkin mendapati maklumat ini berguna:
Huruf Inggeris '\(A\)' mempunyai kod 65
Kemasukan
\(char \ c = 65;\) menyimpan huruf Inggeris dalam pembolehubah \(c\) \(A\)
Oleh itu, anda boleh mendapatkan huruf yang dikehendaki dengan kodnya
|
|