Rekursi -1

Pengenalan 1

Proses di mana fungsi memanggil dirinya sendiri dipanggil rekursi dan
fungsi yang sepadan dipanggilfungsi rekursif.
Memandangkan pengaturcaraan komputer ialah aplikasi asas matematik, jadi marilah
kami mula-mula 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, kita boleh menghantar nilai x yang berbeza kepada fungsi ini dan menerima output kita
sewajarnya.
Sebelum beralih ke rekursi, mari kita cuba memahami matematik yang lain
konsep yang dikenali sebagaiPrinsip 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
berikut 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
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 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
Maka terbukti.

Kerja rekursi

Kita boleh mentakrifkan langkah-langkah pendekatan rekursif dengan meringkaskan tiga perkara 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 tersekat dalam
gelung tak terhingga. Tidak lama lagi, kedalaman rekursi* akan melebihi dan ia akan melontar
satu kesilapan.
● Panggilan rekursif: Fungsi rekursif akan menggunakan 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 kepada 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 Induksi: Kami telah pun 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 dapat

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 n = 0, iaitu 1. Jadi kita akan
simpan ini sebagai kes asas kami. Oleh itu, kod tersebut kini menjadi:

faktorial int statik awam(int n){
jika (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!