Rekursi dalam C

Rekursi adalah teknik ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan suatu masalah.

Dalam pelajaran ini, Anda akan mempelajari:

• Apa itu rekursi dan cara kerjanya.
• Cara mengimplementasikan fungsi rekursif.
• Perbedaan antara rekursi dan iterasi.

Apa Itu Rekursi?

Rekursi terjadi ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan bagian yang lebih kecil dari suatu masalah.

Contoh sintaks:

void function() { function(); // Recursive call }

Setiap fungsi rekursif harus memiliki kasus dasar untuk mencegah rekursi tak berhingga.

Contoh: Rekursi

Program ini mendemonstrasikan rekursi dengan mencetak angka dari 5 hingga 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Kasus Dasar dalam Rekursi

Fungsi rekursif harus menyertakan kasus dasar untuk menghentikan rekursi.

Contoh:

if (n == 0) return;

Tanpa kasus dasar, fungsi akan memanggil dirinya sendiri tanpa henti dan menyebabkan luapan tumpukan.

Contoh: Faktorial Menggunakan Rekursi

Program ini menghitung faktorial suatu angka menggunakan rekursi.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Rekursi dan Iterasi

Rekursi dan iterasi (perulangan) dapat menghasilkan hasil yang sama, tetapi cara kerjanya berbeda.

Perbedaan:

• Rekursi menggunakan pemanggilan fungsi dan membutuhkan lebih banyak memori.
• Iterasi menggunakan perulangan dan umumnya lebih efisien.
• Rekursi membuat kode lebih sederhana untuk masalah seperti penelusuran pohon.

Contoh: Deret Fibonacci (Rekursif)

Program ini menghitung deret Fibonacci menggunakan rekursi.

#include <stdio.h>

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

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Kapan Menggunakan Rekursi?

Rekursi berguna untuk masalah yang melibatkan:

• Penelusuran pohon.
• Penelusuran mundur (misalnya, menyelesaikan labirin).
• Masalah matematika seperti faktorial dan Fibonacci.

Ringkasan

Dalam pelajaran ini, Anda telah mempelajari:

• Apa itu rekursi dan cara kerjanya.
• Pentingnya kasus dasar.
• Perbedaan antara rekursi dan iterasi.

Selanjutnya, kita akan mempelajari larik dan string dalam C!