Rekursi -1

Pengenalan 1

Proses di mana fungsi memanggil dirinya sendiri dipanggil rekursi dan
fungsi yang sepadan dipanggil fungsi rekursif.
Memandangkan pengaturcaraan komputer ialah aplikasi asas matematik, jadi marilah
mula-mula kita cuba memahami penaakulan matematik di sebalik rekursi.
Secara umum, kita semua sedar tentang konsep fungsi. Secara ringkasnya, fungsi ialah
persamaan matematik yang menghasilkan output apabila memberikan input. Contohnya:
Katakan fungsi F(x) ialah fungsi yang ditakrifkan oleh: F(x) = x^2 + 4
Kita boleh menulis Kod Java untuk fungsi ini sebagai:

int statik awam F(int x){
kembali (x * x + 4);
}

Kini, kami boleh menghantar nilai x yang berbeza kepada fungsi ini dan menerima output kami
sewajarnya.
Sebelum beralih ke rekursi, mari kita cuba memahami matematik lain
konsep yang dikenali sebagai Prinsip Induksi Matematik (PMI).

Prinsip Induksi Matematik (PMI) ialah teknik untuk membuktikan sesuatu pernyataan, a
formula, atau teorem yang ditegaskan tentang set nombor asli. Ia mempunyai
mengikuti tiga langkah:
1.** Langkah kes remeh*: Dalam langkah ini, kami akan membuktikan kenyataan yang diingini untuk
kes asas seperti n = 0 atau n = 1.
2.* Langkah andaian**: Dalam langkah ini, kami akan menganggap bahawa pernyataan yang diingini
adalah sah untuk n = k.

1. Untuk membuktikan langkah: Daripada keputusan langkah andaian, kami akan membuktikan bahawa, n = k + 1 juga benar untuk persamaan yang diingini apabila n = k adalah benar.

Sebagai Contoh: Mari kita buktikan menggunakan Prinsip Aruhan Matematik bahawa:
S(N): 1 + 2 + 3 + ... + N = (N * (N + 1))/2
(Jumlah N nombor asli pertama)
Bukti:
Langkah 1: Untuk N = 1, S(1) = 1 adalah benar.
Langkah 2: Andaikan, pernyataan yang diberikan adalah benar untuk N = k, iaitu,
1 + 2 + 3 + .... + k = (k * (k + 1))/2
Langkah 3: Mari kita buktikan pernyataan untuk N = k + 1 menggunakan langkah 2.

Untuk Membuktikan: 1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
Bukti:

Menambah (k+1) pada kedua-dua LHS dan RHS dalam hasil yang diperoleh pada langkah 2:
1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)

Sekarang, mengambil (k+1) biasa dari bahagian RHS:
1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)

Menurut kenyataan yang kami cuba buktikan:
1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
Oleh itu terbukti.

Kerja rekursi

Kita boleh mentakrifkan langkah-langkah pendekatan rekursif dengan meringkaskan tiga di atas
langkah:
● Kes asas: Fungsi rekursif mesti mempunyai keadaan penamatan di mana
proses itu akan berhenti memanggil dirinya sendiri. Kes sedemikian dikenali sebagai kes asas. Tanpa kes asas, ia akan terus memanggil dirinya sendiri dan terperangkap dalam
gelung tak terhingga. Tidak lama lagi, kedalaman rekursi* akan melebihi dan ia akan melontar
ralat.
● Panggilan rekursif: Fungsi rekursif akan menggunakan dirinya sendiri pada versi yang lebih kecil
daripada masalah utama. Kita perlu berhati-hati semasa menulis langkah ini sebagaimana adanya
penting untuk mengetahui dengan betul apa masalah kecil anda.
● Pengiraan kecil: Secara umumnya, kami melakukan langkah pengiraan dalam setiap rekursif
panggil. Kita boleh mencapai langkah pengiraan ini sebelum atau selepas panggilan rekursif
bergantung pada jenis masalah.

Nota: Rekursi menggunakan tindanan terbina dalam yang menyimpan panggilan rekursif. Oleh itu,
bilangan panggilan rekursif mestilah sekecil mungkin untuk mengelakkan limpahan memori. Jika
bilangan panggilan ulangan melebihi jumlah maksimum yang dibenarkan, iaitu
**kedalaman rekursi** akan melebihi.
Sekarang, mari kita lihat cara menyelesaikan beberapa masalah biasa menggunakan Recursion

Pernyataan Masalah - Cari Faktorial Nombor

Pendekatan: Memikirkan tiga langkah PMI dan kemudian mengaitkan perkara yang sama menggunakan
rekursi

1. Langkah Aruhan: Mengira faktorial bagi suatu nombor n - F(n) Hipotesis Aruhan: Kami telah memperoleh faktorial bagi n-1 - F(n-1)
2. Menyatakan F(n) dalam sebutan F(n-1): F(n)=n*F(n-1). Dengan itu kita mendapat

fakta int statik awam(int n){
int ans = fakta(n-1); #Langkah andaian
kembali ans * n; #Menyelesaikan masalah dari langkah andaian
}

1. Kod masih belum lengkap. Bahagian yang hilang ialah kes asas. Sekarang kita akan kering untuk mencari kes di mana rekursi perlu dihentikan. Pertimbangkan n = 5:

Seperti yang kita lihat di atas, kita sudah tahu jawapan bagi n = 0, iaitu 1. Jadi kita akan
simpan ini sebagai kes asas kami. Oleh itu, kod itu kini menjadi:

faktorial int statik awam(int n){
if (n == 0) // huruf asas
pulangkan 1;
lain
kembalikan n*faktorial(n-1); // kes rekursif
}

Atas ialah kandungan terperinci Rekursi -1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!