Fungsi Rekursi

Rekursi adalah suatu konsep dalam pemrograman di mana sebuah fungsi dapat memanggil dirinya sendiri untuk menyelesaikan suatu tugas. Rekursi sering digunakan dalam penyelesaian masalah yang dapat dipecahkan secara berulang dengan cara yang sama pada setiap tahap. Pemahaman dan penggunaan yang bijak dari rekursi dapat menghasilkan solusi yang lebih elegan untuk beberapa permasalahan. Berikut adalah beberapa aspek terkait rekursi:

a. Pengertian Rekursi

#

Rekursi terjadi ketika suatu fungsi memanggil dirinya sendiri dalam tubuh fungsinya. Fungsi yang memanggil dirinya disebut fungsi rekursif.

b. Struktur Fungsi Rekursif

#

Sebuah fungsi rekursif umumnya memiliki dua bagian utama:

def fungsi_rekursif(parameter):
    # Basis kasus (base case)
    if kondisi_basis:
        return nilai_basis
    
    # Kasus rekursif
    else:
        return ekspresi_rekursif

• Basis Kasus (Base Case): Kasus yang sederhana dan dapat langsung dipecahkan tanpa pemanggilan rekursif. Fungsi rekursif berhenti saat mencapai basis kasus.
• Kasus Rekursif: Bagian di mana fungsi memanggil dirinya sendiri dengan input yang lebih sederhana, menuju basis kasus.

c. Contoh Fungsi Rekursif

#

Misalnya, kita dapat menggunakan rekursi untuk menghitung faktorial suatu bilangan:

def faktorial(n):
    # Basis kasus
    if n == 0 or n == 1:
        return 1
    # Kasus rekursif
    else:
        return n * faktorial(n - 1)

• Basis kasus: Faktorial dari 0 atau 1 adalah 1.
• Kasus rekursif: Faktorial dari suatu bilangan n adalah n dikali faktorial dari n - 1.

d. Kelebihan dan Keterbatasan Rekursi

#

Kelebihan:

• Solusi dapat menjadi lebih singkat dan elegan untuk beberapa permasalahan.
• Cocok untuk permasalahan dengan struktur yang dapat dipecahkan secara rekursif.

Keterbatasan:

• Membutuhkan alokasi memori tambahan untuk setiap pemanggilan fungsi.
• Pemanggilan rekursif yang terlalu dalam dapat menyebabkan “Stack Overflow” (batas kapasitas tumpukan).

e. Contoh Aplikasi Rekursi: Bilangan Fibonacci

#

Bilangan Fibonacci adalah deret angka di mana setiap angka adalah hasil penjumlahan dua angka sebelumnya.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Contoh penggunaan
for i in range(5):
    print(fibonacci(i))

• Basis kasus: Fibonacci dari 0 atau 1 adalah angka itu sendiri.
• Kasus rekursif: Fibonacci dari suatu angka n adalah penjumlahan Fibonacci dari n - 1 dan n - 2.