Recursive Functions

Sejauh ini fungsi kita memanggil fungsi lain — MATLAB juga mengizinkan sebuah fungsi memanggil dirinya sendiri, teknik yang disebut recursion. Untuk masalah yang definisinya memang rekursif — faktorial, deret Fibonacci, penelusuran struktur bersarang — bentuk program paling natural justru yang meniru definisinya. Rekursi juga punya dua sisi gelap yang wajib kita pahami sebelum memakainya: tanpa kasus dasar program tidak pernah berhenti, dan beberapa rekursi yang terlihat polos ternyata tumbuh eksponensial. Cakupan chapter ini:

• anatomi rekursi: kasus dasar dan kasus rekursif
• faktorial, Fibonacci, dan maksimum array versi rekursif
• batas kedalaman rekursi MATLAB dan kapan memilih loop

Faktorial: Kasus Dasar dan Kasus Rekursif #

Aturannya: setiap fungsi rekursif wajib punya dua bagian — kasus dasar yang dijawab langsung tanpa pemanggilan ulang, dan kasus rekursif yang memanggil fungsi itu dengan masukan yang mengecil menuju kasus dasar. Mekanisme di balik layar: setiap pemanggilan menumpuk satu frame pemanggilan berisi salinan parameternya; tumpukan itu terurai dari dalam ke luar begitu kasus dasar tercapai. Definisi n! = n × (n-1)! dengan 0! = 1! = 1 diterjemahkan hampir kata demi kata di faktorialRekursif.m:

function hasil = faktorialRekursif(n)
% faktorialRekursif Faktorial n versi rekursif.
%   hasil = faktorialRekursif(n) menghitung n! lewat relasi
%   n! = n * (n-1)! dengan kasus dasar 0! = 1! = 1.

if n <= 1
    hasil = 1;   % kasus dasar: menghentikan rekursi
    return
end

% kasus rekursif: masalah mengecil menuju kasus dasar
hasil = n * faktorialRekursif(n - 1);
end

Mari kita bedah baris-baris kode di atas:

1. Baris 6 (if n <= 1): kasus dasar — 0! dan 1! bernilai 1; cabang ini menjadi titik pemberhentian seluruh rantai pemanggilan.
2. Baris 7-8 (hasil = 1; return): nilai jawaban diisi lalu return keluar lebih awal — pola ringkas untuk kasus dasar.
3. Baris 12 (hasil = n * faktorialRekursif(n - 1);): kasus rekursif — n - 1 lebih kecil dari n, sehingga setiap pemanggilan mendekati kasus dasar.

Rantai penguraian faktorialRekursif(4) terlihat seperti ini:

Fase turun (memanggil dengan masukan yang mengecil) berhenti di kasus dasar; fase naik mengalikan hasil tiap level hingga jawaban akhir kembali ke pemanggil pertama.

Batas Kedalaman Rekursi #

Batas 500 membatasi seberapa dalam rekursi boleh menumpuk: faktorialRekursif(499) masih aman, faktorialRekursif(600) melewati batas. Struktur data yang dalam (daftar bersarang, pohon) adalah pengguna sah kedalaman besar; deret sederhana bukan.

Fibonacci: Rekursi yang Mahal #

Deret Fibonacci mendefinisikan F(n) = F(n-1) + F(n-2) dengan F(1) = F(2) = 1. Terjemahan rekursifnya sama polosnya dengan faktorial — dan di sinilah jebakannya:

function f = fibonacciRekursif(n)
% fibonacciRekursif Bilangan Fibonacci ke-n versi rekursif.
%   f = fibonacciRekursif(n) menghitung F(n) dengan F(1) = F(2) = 1 dan
%   F(n) = F(n-1) + F(n-2). PERINGATAN: jumlah pemanggilan tumbuh
%   eksponensial — hanya gunakan n yang kecil.

if n <= 2
    f = 1;   % kasus dasar
    return
end

f = fibonacciRekursif(n - 1) + fibonacciRekursif(n - 2);
end

Masalahnya: baris terakhir memanggil fungsi dua kali, dan masing-masing memanggil dua kali lagi — pohon pemanggilan fibonacciRekursif(n) berisi kira-kira 2 × F(n) pemanggilan. Tabel berikut memperlihatkan ledakannya:

Di lingkungan uji kami, fibonacciRekursif(30) sudah memakan waktu sekitar enam detik; fibonacciRekursif(40) ratusan kali lebih lambat. Penyebab utamanya bukan rekursinya, melainkan perhitungan yang diulang: F(28) dihitung berulang kali di cabang berbeda.

Contoh Praktis: Maksimum Array Rekursif #

Rekursi menjadi terasa berguna ketika masalahnya terpecah alami menjadi “satu elemen + sisanya”. Maksimum sebuah vektor adalah elemen pertama atau maksimum sisanya — dan “sisanya yang tersisa satu elemen” adalah kasus dasar:

function m = maksimumRekursif(v)
% maksimumRekursif Nilai terbesar vektor, dihitung secara rekursif.
%   m = maksimumRekursif(v) membandingkan elemen pertama v dengan
%   maksimum dari sisanya (v(2:end)) hingga tersisa satu elemen.

if numel(v) == 1
    m = v(1);   % kasus dasar: vektor satu elemen
    return
end

sisa = maksimumRekursif(v(2:end));

if v(1) > sisa
    m = v(1);
else
    m = sisa;
end
end

Skrip uji uji_faktorialRekursif.m membandingkan ketiga fungsi rekursif dengan padanan bawaan MATLAB:

fprintf('faktorialRekursif(5)  : %d\n', faktorialRekursif(5));
fprintf('faktorialRekursif(10) : %d\n', faktorialRekursif(10));
fprintf('factorial(10) bawaan : %d\n', factorial(10));

fprintf('fibonacciRekursif(10) : %d\n', fibonacciRekursif(10));
fprintf('fibonacciRekursif(20) : %d\n', fibonacciRekursif(20));

v = [7 2 9 4 11 3];
fprintf('maksimumRekursif(v)   : %d\n', maksimumRekursif(v));
fprintf('max(v) bawaan         : %d\n', max(v));

Output yang Dihasilkan:

faktorialRekursif(5)  : 120
faktorialRekursif(10) : 3628800
factorial(10) bawaan : 3628800
fibonacciRekursif(10) : 55
fibonacciRekursif(20) : 6765
maksimumRekursif(v)   : 11
max(v) bawaan         : 11

Ketiga hasilnya cocok dengan fungsi bawaan factorial dan max — rekursi menghasilkan jawaban yang sama, hanya dengan jalan yang berbeda.

Rekursi vs Loop #

Hampir semua rekursi linear bisa ditulis ulang sebagai loop. Faktorial iteratif memakai for dari Chapter for Loop — hasil = 1; for k = 2:n, hasil = hasil * k; end — menghasilkan 3628800 yang sama untuk n = 10 tanpa satu pun pemanggilan ulang:

Ringkasan #

Fungsi rekursif memanggil dirinya dengan masukan yang mengecil menuju kasus dasar — bagian yang wajib ada, sebab tanpanya MATLAB menghentikan program di kedalaman 500 dengan galat recursion limit. Faktorial dan maksimum array memperlihatkan bentuk rekursi yang sehat; Fibonacci naif memperlihatkan jebakan pohon pemanggilan eksponensial yang diatasi dengan loop atau teknik memoisasi (kita bahas di Section Optimasi dan Performa). Aturan praktisnya: definisi rekursif → tulis rekursif; selain itu → loop atau operasi array bawaan. Berkas faktorialRekursif.m, fibonacciRekursif.m, maksimumRekursif.m, dan uji_faktorialRekursif.m di bagian bawah halaman siap dijalankan.