IN1037 Sesi 10: Rekursi Dasar

I. Ulasan: Definisi dan Prinsip Rekursi

Rekursi adalah teknik di mana sebuah fungsi memanggil dirinya sendiri. Teknik ini sangat elegan untuk memecahkan masalah yang memiliki struktur yang sama pada skala berbeda (seperti struktur tree, fraktal, atau urutan matematis seperti Faktorial dan Fibonacci).

Dua Pilar Rekursi (Wajib):

Basis (Base Case): Kondisi di mana fungsi berhenti memanggil dirinya sendiri. Jika Basis tidak didefinisikan, akan terjadi *infinite loop* (rekursi tak terbatas) dan *Stack Overflow*.
Langkah Rekursif (Recursive Step): Langkah di mana fungsi memanggil dirinya sendiri, tetapi dengan *input* yang telah dimodifikasi, sehingga input tersebut bergerak mendekati kondisi basis.

Rekursi vs. Iterasi (Perulangan)

Sebagian besar masalah rekursif dapat diselesaikan dengan iterasi (for atau while). Namun, rekursi sering lebih mudah dipahami secara konseptual untuk masalah-masalah tertentu.

Kriteria	Rekursi	Iterasi
Keterbacaan	Baik untuk masalah yang bersifat hirarkis/bertingkat (ex: tree).	Lebih mudah untuk perhitungan linier (ex: penjumlahan deret).
Memori	Konsumsi memori lebih besar (menyimpan stack panggilan).	Konsumsi memori lebih efisien.
Kecepatan	Cenderung sedikit lebih lambat di Python karena overhead panggilan fungsi.	Cenderung lebih cepat.

II. Contoh Manual: Kalkulasi Faktorial

Faktorial ($n!$) adalah contoh klasik rekursi. Formula: $n! = n \times (n-1)!$

2.1. Formula dan Basis:

Basis: Jika $n = 0$, kembalikan 1 ($0! = 1$).
Langkah Rekursif: $n \times \text{faktorial}(n-1)$.

2.2. Pelacakan Rekursi (Tracing) untuk 3!

faktorial(3)
    -> 3 * faktorial(2)
        -> 2 * faktorial(1)
            -> 1 * faktorial(0) (Basis Tercapai!)
            <- return 1
        <- return 2 * 1 = 2
    <- return 3 * 2 = 6
OUTPUT AKHIR: 6

III. Kode Praktik (Google Colab)

3.1. Kode Sederhana: Fungsi Faktorial Rekursif

Implementasi langsung dari logika faktorial.

In [1]: python

def hitung_faktorial_rekursif(n):
    # Basis: n=0 atau n=1
    if n <= 1:
        return 1
    # Langkah Rekursif
    else:
        return n * hitung_faktorial_rekursif(n - 1)

# Uji coba
hasil_5 = hitung_faktorial_rekursif(5)
hasil_8 = hitung_faktorial_rekursif(8)

print(f"Faktorial 5: {hasil_5}")
print(f"Faktorial 8: {hasil_8}")

Out [1]:

Faktorial 5: 120
Faktorial 8: 40320

3.2. Kode Kompleks: Urutan Fibonacci (Pola Pertumbuhan)

Urutan Fibonacci (F_n = F_n-1 + F_n-2) sering muncul dalam model pertumbuhan biologis dan efisiensi algoritma.

In [2]: python

def fibonacci_rekursif(n):
    # Basis: n=0 atau n=1
    if n <= 1:
        return n
    # Langkah Rekursif: penjumlahan dua suku sebelumnya
    else:
        return fibonacci_rekursif(n - 1) + fibonacci_rekursif(n - 2)

# Mencari suku ke-6 dan ke-10
suku_6 = fibonacci_rekursif(6)
suku_10 = fibonacci_rekursif(10)

print(f"Suku ke-6 (0, 1, 1, 2, 3, 5, 8): {suku_6}")
print(f"Suku ke-10: {suku_10}")

# Catatan: Perhatikan bagaimana waktu eksekusi meningkat drastis
# saat n besar karena kalkulasi berulang.

Out [2]:

Suku ke-6 (0, 1, 1, 2, 3, 5, 8): 8
Suku ke-10: 55

3.3. Kode Kompleks: Menghitung Jumlah Digit (Aplikasi Rekursi Non-Matematika)

Mendemonstrasikan bagaimana rekursi dapat digunakan untuk memecah masalah non-numerik (menghitung jumlah digit dari sebuah bilangan).

In [3]: python

def jumlah_digit_rekursif(n):
    # Mengambil nilai absolut untuk bilangan negatif
    n = abs(n) 
    
    # Basis: Jika bilangan hanya satu digit (0-9)
    if n < 10:
        return 1
    # Langkah Rekursif: Pecah digit terakhir dan panggil ulang fungsi
    # // adalah integer division
    else:
        return 1 + jumlah_digit_rekursif(n // 10)

# Uji coba
angka_besar = 153098
angka_kecil = 7

count_besar = jumlah_digit_rekursif(angka_besar)
count_kecil = jumlah_digit_rekursif(angka_kecil)

print(f"Angka {angka_besar} memiliki {count_besar} digit.")
print(f"Angka {angka_kecil} memiliki {count_kecil} digit.")

Out [3]:

Angka 153098 memiliki 6 digit.
Angka 7 memiliki 1 digit.

IV. Penugasan / PR Sesi 10: Sum of Natural Numbers

Tugas Anda adalah membuat fungsi rekursif bernama sum_natural_numbers(n) yang menghitung jumlah total bilangan asli dari 1 hingga $n$.

Formula: S(n) = n + S(n − 1).
Basis: Jika n = 0 atau n = 1.
Implementasi: Hitung dan kembalikan (return) totalnya.
Pengujian: Panggil fungsi untuk n = 10. Hasilnya harus 55.