Rekursi dalam C

Hai sana, para pemrogram masa depan! Hari ini, kita akan melihat salah satu konsep yang paling menarik dalam pemrograman: rekursi. Jangan khawatir jika itu terdengar menakutkan - di akhir panduan ini, Anda akan menjadi ahli rekursi! Mari kita mulai perjalanan menarik ini bersama-sama.

Apa itu Fungsi Rekursif dalam C?

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

Sebuah 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?"

Ini 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 nomor yang lebih kecil setiap kali. Itu seperti countdown roket, di mana kita terus menghitung sampai mencapai nol dan kemudian blast off!

Mengapa Rekursi Digunakan dalam C?

Anda mungkin berpikir, "Mengapa harus mengganggu rekursi ketika kita memiliki loop?" Pertanyaan bagus! Rekursi memiliki beberapa keungguran:

1. Itu dapat membuat kode lebih mudah dibaca dan elegan untuk beberapa masalah.
2. Itu sangat cocok untuk tugas yang memiliki sifat rekursif, seperti menelusuri 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 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 nomor n (ditulis sebagai n!) adalah produk semua bilangan positif kurang dari atau sama dengan n.

Ini 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 dasar kita).
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 efisien untuk menemukan item dalam daftar yang diurutkan. Itu bekerja dengan terus membagi interval pencarian setengah. 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 bagian kiri.
4. Jika target lebih besar dari elemen tengah, cari bagian kanan.
5. Jika kita tidak menemukan elemen, kembalikan -1.

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

Deret Fibonacci Menggunakan Rekursi

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

Ini adalah cara kita generate 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 adalah 0 atau 1, kita kembalikan n (ini adalah kasus dasar kita).
2. Untuk n lainnya, kita kembalikan jumlah 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

Mengembalikan ke belakang, kita mendapat:

• 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

Ini 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 dalam array yang diurutkan	Elemen ditemukan atau tidak dalam array	Cari bagian kiri atau kanan
Fibonacci	Generate 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 delegasi tugas kepada klornya sendiri - Anda tahu mereka akan menangani 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-tama memahami rekursi. ?

Credits: Image by storyset