Rekursi terjadi ketika sebuah fungsi berisi dalamnya sebuah panggilan ke dirinya sendiri. Rekursi bisa menghasilkan kode yang sangat rapi dan elegan yang intuitif untuk diikuti. Ini juga bisa menghasilkan penggunaan memori yang sangat besar jika rekursi terlalu dalam.
Contoh umum di mana rekursi digunakan:
* Menjelajahi struktur data rekursif seperti daftar tertaut, pohon biner, dll.
* Menjelajahi skenario yang mungkin dalam permainan seperti catur
Rekursi selalu terdiri dari dua bagian utama. Kasus terminasi yang menunjukkan kapan rekursi akan selesai dan panggilan ke dirinya sendiri yang harus membuat kemajuan menuju kasus terminasi.
Sebagai contoh, fungsi ini akan melakukan perkalian dengan penambahan rekursif:
#include <stdio.h>
unsigned int multiply(unsigned int x, unsigned int y)
{
if (x == 1)
{
/* Kasus terminasi */
return y;
}
else if (x > 1)
{
/* Langkah rekursif */
return y + multiply(x-1, y);
}
/* Menangani skenario ketika x adalah nol */
return 0;
}
int main()
{
printf("3 kali 5 adalah %d", multiply(3, 5));
return 0;
}
| Elemen | Deskripsi | Contoh |
|---|---|---|
| Fungsi rekursif | Fungsi yang memanggil dirinya sendiri | factorial(n) memanggil factorial(n-1) |
| Kasus terminasi | Kondisi yang menghentikan rekursi | if (n <= 1) return 1; |
| Panggilan rekursif | Fungsi memanggil dirinya sendiri | return n * factorial(n-1); |
| Parameter berubah | Parameter yang berubah untuk mendekati kasus terminasi | factorial(n-1) |
Definisikan fungsi baru bernama factorial() yang akan menghitung faktorial dengan perkalian rekursif (5! = 5 x 4 x 3 x 2 x 1). Perhatikan bahwa berdasarkan konvensi, faktorial dari 0 adalah sama dengan 1 (0! = 1).
Requirements:
- Buat fungsi rekursif untuk menghitung faktorial
- Gunakan kasus terminasi yang benar
- Fungsi harus bekerja untuk 0! = 1
Expected Output:
0! = 1
1! = 1
3! = 6
5! = 120
Try writing your solution in the code editor below!
Current Lesson: Recursion
Learning Objectives:
- Memahami konsep rekursi dalam bahasa C
- Belajar membuat fungsi rekursif
- Mengenal kasus terminasi dalam rekursi
- Memahami aplikasi rekursi dalam pemrograman
Prerequisites:
- Pemahaman tentang fungsi dalam C
- Pemahaman dasar tentang perulangan