Recursion

Semua fungsi yang kita tulis sejauh ini memanggil fungsi lain yang berbeda. PHP juga membolehkan pola yang terdengar aneh pada pandangan pertama: fungsi yang memanggil dirinya sendiri. Teknik ini disebut recursion (rekursi), dan ia merupakan alat alami untuk masalah yang salinan kecilnya berbentuk sama dengan dirinya — perkalian faktorial, barisan Fibonacci, menu yang berisi submenu, direktori yang berisi subdirektori. Pada Chapter ini kita membedah anatomi rekursi, syarat mutlak bernama base case, risiko stack overflow, perbandingan Fibonacci naif lawan memoized, lalu menutup dengan panduan memilih antara rekursi dan iterasi.

Fungsi yang Memanggil Dirinya Sendiri #

Contoh pembuka paling klasik adalah faktorial: hasil kali semua bilangan bulat positif dari n turun ke 1, dengan kesepakatan 0! = 1! = 1. Faktorial cocok untuk rekursi karena definisi matematisnya sendiri bersifat rekursif — n! sama dengan n × (n-1)!:

<?php
function faktorial(int $n): int
{
    if ($n <= 1) {
        return 1;
    }

    return $n * faktorial($n - 1);
}

echo faktorial(1) . "\n";
echo faktorial(5) . "\n";
echo faktorial(10) . "\n";

Output yang Dihasilkan:

1
120
3628800

Perhatikan tubuh fungsinya: hanya dua jalur. Mari kita telusuri apa yang sebenarnya terjadi saat faktorial(5) dipanggil:

1. faktorial(5) tidak menyentuh kondisi $n <= 1, sehingga fungsi harus menghitung 5 * faktorial(4) — dan berhenti menunggu hasil pemanggilan di dalamnya.
2. faktorial(4) juga memanggil faktorial(3), begitu seterusnya hingga faktorial(1).
3. faktorial(1) mengembalikan 1 — pemanggilan paling dalam akhirnya selesai.
4. Hasil menggelegak naik: 2×1=2, 3×2=6, 4×6=24, 5×24=120.

Setiap pemanggilan yang menunggu hasil pemanggilan berikutnya ditumpuk di call stack — struktur internal yang menyimpan jejak fungsi yang sedang berjalan. Rekursi hanyalah cara memanfaatkan tumpukan itu sebagai penyimpan sementara pekerjaan yang belum selesai.

Base Case dan Bahaya Rekursi Tanpa Batas #

Setiap fungsi rekursif wajib memiliki base case: kondisi ketika fungsi berhenti memanggil dirinya dan langsung mengembalikan nilai — pada faktorial() kondisi tersebut adalah $n <= 1. Tanpa base case, rekursi menjadi tak berujung: setiap pemanggilan menumpuk frame baru di call stack, dan memori yang dialokasikan untuk stack pada akhirnya habis. PHP tidak melakukan optimisasi tail-call seperti beberapa bahasa lain, sehingga rekursi yang sangat dalam benar-benar berbahaya: eksekusi berhenti dengan pesan fatal bahwa memori habis atau jumlah level pemanggilan melebihi batas.

Fibonacci Naif versus Memoized #

Barisan Fibonacci — 0, 1, 1, 2, 3, 5, 8, ... — memiliki definisi rekursif yang tampak elegan: suku ke-n adalah jumlah dua suku sebelumnya, F(n) = F(n-1) + F(n-2), dengan base case F(0) = 0 dan F(1) = 1. Berikut implementasi naifnya, dilengkapi parameter referensi int &$jumlahPanggilan yang menaikkan satu penghitung bersama setiap kali tubuh fungsi berjalan — sehingga kita bisa mengukur seberapa banyak pekerjaan yang benar-benar dilakukan:

<?php
function fibonacciHitung(int $n, int &$jumlahPanggilan): int
{
    $jumlahPanggilan++;

    if ($n <= 1) {
        return $n;
    }

    return fibonacciHitung($n - 1, $jumlahPanggilan)
        + fibonacciHitung($n - 2, $jumlahPanggilan);
}

$jumlahPanggilan = 0;
$hasil = fibonacciHitung(15, $jumlahPanggilan);
echo "fibonacci(15) = $hasil\n";
echo "Jumlah pemanggilan: $jumlahPanggilan\n";

Output yang Dihasilkan:

fibonacci(15) = 610
Jumlah pemanggilan: 1973

Hanya untuk menghitung suku ke-15, tubuh fungsi berjalan 1.973 kali. Penyebabnya terlihat pada bentuk pemanggilannya: fibonacciHitung(15) menghitung fibonacciHitung(13) dua kali, fibonacciHitung(12) tiga kali, dan seterusnya ke bawah — pekerjaan yang sama diulang berkali-kali di cabang yang berbeda. Solusinya bernama memoization: simpan hasil yang sudah dihitung ke dalam cache agar pemanggilan berikutnya cukup membaca:

<?php
function fibonacciMemo(int $n, array &$cache, int &$jumlahPanggilan): int
{
    $jumlahPanggilan++;

    if ($n <= 1) {
        return $n;
    }

    if (isset($cache[$n])) {
        return $cache[$n];
    }

    $hasil = fibonacciMemo($n - 1, $cache, $jumlahPanggilan)
        + fibonacciMemo($n - 2, $cache, $jumlahPanggilan);
    $cache[$n] = $hasil;

    return $hasil;
}

$jumlahPanggilan = 0;
$cache = [];
$hasil = fibonacciMemo(15, $cache, $jumlahPanggilan);
echo "fibonacciMemo(15) = $hasil\n";
echo "Jumlah pemanggilan: $jumlahPanggilan\n";

Output yang Dihasilkan:

fibonacciMemo(15) = 610
Jumlah pemanggilan: 29

Parameter array &$cache adalah array referensi yang dibagikan ke seluruh pemanggilan, sehingga hasil yang tersimpan pada kedalaman mana pun langsung terlihat di kedalaman lain. Perbandingan keduanya mencolok:

Selisih 1.973 lawan 29 baru pembukaan. Menghitung suku ke-40 dengan versi naif menuntut sekitar 331 juta pemanggilan, sementara versi memoized menyelesaikannya hanya dengan sekitar 79 pemanggilan. Setiap kali Anda menulis rekursi yang bercabang lebih dari satu pemanggilan, periksalah apakah ada perhitungan yang diulang; memoization adalah perbaikan termurah sebelum Anda mempertimbangkan beralih ke iterasi.

Menelusuri Struktur Bersarang #

Rekursi benar-benar bersinar ketika data berbentuk pohon — struktur yang kedalamannya tidak diketahui dari awal. Contoh nyatanya: menu navigasi yang boleh memiliki submenu, dan submenu itu sendiri boleh memiliki submenu lagi. Fungsi berikut mencetak seluruh isi menu bertingkat:

<?php
function tampilkanMenu(array $daftar, string $awalan = ''): void
{
    foreach ($daftar as $item) {
        echo $awalan . $item['judul'] . "\n";

        if (isset($item['anak'])) {
            tampilkanMenu($item['anak'], $awalan . '  ');
        }
    }
}

$menu = [
    ['judul' => 'Beranda'],
    [
        'judul' => 'Produk',
        'anak' => [
            ['judul' => 'Kopi'],
            [
                'judul' => 'Kopi Susu',
                'anak' => [
                    ['judul' => 'Reguler'],
                    ['judul' => 'Gula Batu'],
                ],
            ],
        ],
    ],
    ['judul' => 'Kontak'],
];

tampilkanMenu($menu);

Output yang Dihasilkan:

Beranda
Produk
  Kopi
  Kopi Susu
    Reguler
    Gula Batu
Kontak

Loop foreach mengurus satu tingkat menu, lalu pemanggilan tampilkanMenu($item['anak'], $awalan . ' ') mengolah setiap anak dengan indentasi satu tingkat lebih dalam — perhatikan parameter $awalan yang bertambah dua spasi setiap level. Struktur data-lah yang menentukan seberapa dalam rekursi berjalan; base case-nya implisit: elemen tanpa kunci 'anak' tidak memicu pemanggilan baru. Pola ini persis sama dengan penelusuran direktori — folder berisi berkas dan subfolder, yang subfoldernya berisi berkas lagi — yang akan kita praktikkan nanti di Section File System dan Streams .

Pola yang sama bekerja untuk memproses isi array bersarang, bukan sekadar menampilkannya. Contoh berikut menormalkan seluruh string pada semua kedalaman array — pekerjaan yang tidak sanggup ditangani array_map() bawaan karena fungsi tersebut hanya bekerja pada satu tingkat:

<?php
function hurufKecilSemua(array $data): array
{
    $hasil = [];

    foreach ($data as $kunci => $nilai) {
        if (is_array($nilai)) {
            $hasil[$kunci] = hurufKecilSemua($nilai);
        } else {
            $hasil[$kunci] = strtolower($nilai);
        }
    }

    return $hasil;
}

$kategori = [
    'Minuman' => [
        'Panas' => ['KOPI HITAM', 'Teh MELATI'],
        'Dingin' => ['ES JERUK'],
    ],
    'Makanan' => ['ROTI BAKERY'],
];

print_r(hurufKecilSemua($kategori));

Output yang Dihasilkan:

Array
(
    [Minuman] => Array
        (
            [Panas] => Array
                (
                    [0] => kopi hitam
                    [1] => teh melati
                )

            [Dingin] => Array
                (
                    [0] => es jeruk
                )

        )

    [Makanan] => Array
        (
            [0] => roti bakery
        )

)

Pada fungsi di atas, cabang else adalah base case untuk setiap elemen: nilai yang bukan array langsung diolah dengan strtolower(). Adapun cabang is_array($nilai) memanggil fungsi itu sendiri untuk mengolah sub-array, lalu hasilnya ditempatkan kembali pada kunci yang sama. Fungsi rekursif yang mengembalikan nilai baru seperti ini biasanya lebih mudah dipakai ulang daripada yang mengubah data asli, karena data sumber tetap utuh.

Rekursi atau Iterasi #

Setiap rekursi pada prinsipnya dapat ditulis ulang sebagai loop — dan sebaliknya. Pembanding berikut menghitung faktorial yang sama persis tanpa satu pun pemanggilan rekursif:

<?php
function faktorialIteratif(int $n): int
{
    $hasil = 1;
    for ($i = 2; $i <= $n; $i++) {
        $hasil *= $i;
    }

    return $hasil;
}

echo faktorialIteratif(5) . "\n";

Output yang Dihasilkan:

120

Versi iteratif hanya memakai dua variabel dan tidak menumpuk apa pun di call stack. Maka pilihan antara keduanya adalah soal kecocokan, bukan doktrin:

Ringkasan #

Rekursi adalah fungsi yang memanggil dirinya sendiri dengan input yang makin mendekatkan ke base case — syarat yang tanpanya call stack habis dan program berhenti dengan fatal error. Fibonacci naif menunjukkan bagaimana rekursi bercabang mengulang pekerjaan yang sama, dan memoization menyelesaikannya dengan cache hasil. Untuk struktur bersarang seperti menu dan direktori, rekursi adalah alat paling alami, sementara akumulasi sederhana lebih baik ditulis sebagai loop. Dengan seluruh teknik fungsi di tangan — parameter, return value, closure, hingga rekursi — kita siap menutup Section ini dengan satu pertanyaan perancangan pada Chapter Merancang Fungsi yang Baik .

Referensi #

• User-defined functions — php.net
• Functions — php.net
• Returning values — php.net