ID (Indonesia) Translation

Rekursi dalam C

Halo sana, para pemrogram masa depan! Hari ini, kita akan memantulkan salah satu konsep yang paling menarik dalam pemrograman: rekursi. Jangan khawatir jika itu terdengar menakutkan - pada akhir tutorial ini, Anda akan menjadi ahli rekursi! Ayo kita mulai perjalanan yang menarik ini bersama-sama.

Apa Itu Fungsi Rekursif dalam C?

Bayangkan Anda melihat diri Anda dalam cermin, dan di belakang Anda ada cermin lain. Anda melihat banyak refleksi tak terbatas dari diri Anda. Itu agak seperti rekursi dalam pemrograman!

Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri selama eksekusinya. Itu seperti sebuah fungsi mengatakan, "Hey, saya memerlukan bantuan. Siapa yang lebih baik untuk membantu saya kecuali... diri saya sendiri?"

Berikut adalah contoh sederhana:

void countdown(int n) {
if (n == 0) {
printf("Blastoff!\n");
} else {
printf("%d\n", n);
countdown(n - 1);
}
}

Dalam fungsi ini, countdown memanggil dirinya sendiri dengan angka yang lebih kecil setiap kali. Itu seperti hitung mundur roket, di mana kita terus menghitung sampai mencapai nol dan kemudian blast off!

Mengapa Rekursi Digunakan dalam C?

Anda mungkin bertanya-tanya, "Mengapa mengganggu rekursi saat kita memiliki loop?" Pertanyaan bagus! Rekursi memiliki beberapa keunggulan:

1. Itu dapat membuat kode lebih mudah dibaca dan elegan untuk beberapa masalah.
2. Itu sangat baik untuk tugas yang memiliki sifat rekursif, seperti meng traversal struktur seperti pohon.
3. Itu dapat mengurangi kebutuhan untuk struktur loop yang kompleks dan variabel sementara.

Namun, rekursi tidak selalu menjadi pilihan terbaik. Itu dapat memakan memori yang banyak dan lebih lambat untuk beberapa masalah. Seperti halnya banyak hal lain dalam pemrograman, itu tentang memilih alat yang tepat untuk pekerjaan.

Faktorial Menggunakan Rekursi

Mari kita lihat contoh kelasik rekursi: menghitung faktorial. Faktorial dari sebuah bilangan n (ditulis sebagai n!) adalah produk semua bilangan positif kurang dari atau sama dengan n.

Berikut adalah cara kita menghitung faktorial secara rekursif:

int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

mari kitauraikan ini:

1. Jika n adalah 0 atau 1, kita kembalikan 1 (ini adalah kasus dasarnya).
2. Jika tidak, kita kalikan n dengan faktorial (n-1).

Jadi, jika kita panggil factorial(5), ini apa yang terjadi:

• 5 * factorial(4)
• 5 (4 factorial(3))
• 5 (4 (3 * factorial(2)))
• 5 (4 (3 (2 factorial(1))))
• 5 (4 (3 (2 1)))
• 5 (4 (3 * 2))
• 5 (4 6)
• 5 * 24
• 120

Dan begitu Anda mendapat - 5! = 120.

Pencarian Binari Menggunakan Rekursi

Pencarian binari adalah algoritme yang efisien untuk menemukan item dalam daftar yang diurutkan. Itu bekerja dengan terus membagi interval pencarian menjadi dua. Mari kita implementasikan itu secara rekursif:

int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);
}

return -1;
}

Fungsi ini melakukan hal berikut:

1. Hitung indeks tengah.
2. Jika elemen tengah adalah target, kita selesai!
3. Jika target kurang dari elemen tengah, cari di setengah kiri.
4. Jika target lebih besar dari elemen tengah, cari di setengah kanan.
5. Jika kita tidak menemukan elemen, kembalikan -1.

Itu seperti permainan tingkat tinggi "tebak angka", di mana Anda selalu menebak angka tengah diantara rentang yang tersisa!

Deret Fibonacci Menggunakan Rekursi

Deret Fibonacci adalah deret bilangan di mana setiap bilangan adalah jumlah dari dua bilangan sebelumnya. Itu kandidat sempurna untuk rekursi!

Berikut adalah cara kita menghasilkan bilangan Fibonacci secara rekursif:

int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

Fungsi ini bekerja seperti ini:

1. Jika n kurang dari atau sama dengan 1, kita kembalikan n (ini adalah kasus dasarnya).
2. Untuk n lainnya, kita kembalikan jumlah dari dua bilangan Fibonacci sebelumnya.

Jadi, jika kita panggil fibonacci(5), ini apa yang terjadi:

• fibonacci(5) = fibonacci(4) + fibonacci(3)
• fibonacci(4) = fibonacci(3) + fibonacci(2)
• fibonacci(3) = fibonacci(2) + fibonacci(1)
• fibonacci(2) = fibonacci(1) + fibonacci(0)
• fibonacci(1) = 1
• fibonacci(0) = 0

Mengerjakan mundur, kita mendapatkan:

• fibonacci(2) = 1 + 0 = 1
• fibonacci(3) = 1 + 1 = 2
• fibonacci(4) = 2 + 1 = 3
• fibonacci(5) = 3 + 2 = 5

Jadi bilangan Fibonacci ke-5 adalah 5!

Metode Rekursif Umum

Berikut adalah tabel metode rekursif umum yang kita diskusikan:

Metode	Deskripsi	Kasus Dasar	Kasus Rekursif
Faktorial	Menghitung n!	n = 0 atau 1	n * factorial(n-1)
Pencarian Binari	Menemukan elemen di array terurut	Elemen ditemukan atau tidak dalam array	Cari setengah kiri atau kanan
Fibonacci	Menghasilkan bilangan Fibonacci	n <= 1	fibonacci(n-1) + fibonacci(n-2)

Ingat, kunci memahami rekursi adalah untuk mempercayai bahwa panggilan rekursif akan melakukan tugasnya dengan benar. Itu seperti mem delegasikan tugas ke克隆 Anda sendiri - Anda tahu mereka akan menyelesaikan itu seperti Anda!

Rekursi dapat menjadi sedikit membingungkan pada awalnya, tapi dengan latihan, itu menjadi alat kuat dalam peralatan pemrograman Anda. Terus mencoba, dan segera Anda akan melihat solusi rekursif di mana-mana!

Happy coding, dan ingat - untuk memahami rekursi, Anda harus pertama kali memahami rekursi. ?

Credits: Image by storyset