KAL
Menu

Rekursi

Kasus dasar rekursi dan penelusuran direktori yang praktis.

Daftar isi

Rekursi adalah teknik memecahkan masalah dengan membuat fungsi memanggil dirinya sendiri pada versi masukan yang lebih kecil. Topik ini membahas kasus dasar dan langkah rekursif, yaitu dua komponen yang wajib ada pada setiap fungsi rekursif, contoh klasik faktorial, serta penerapan nyata berupa penelusuran direktori bertingkat. Setelah topik ini dibaca, fungsi rekursif sederhana dapat ditulis dan dijalankan, sedangkan batas kedalamannya dapat diantisipasi.

Kasus dasar dan langkah rekursif#

Fungsi rekursif selalu tersusun atas dua bagian. Kasus dasar (base case) adalah kondisi yang langsung mengembalikan nilai tanpa memanggil dirinya lagi. Langkah rekursif adalah bagian yang memanggil fungsi itu sendiri dengan masukan yang lebih dekat ke kasus dasar. Tanpa salah satu dari keduanya, pemanggilan tidak pernah berhenti. Pada perhitungan faktorial, hubungan n!=n×(n−1)!n! = n \times (n-1)! menjadi langkah rekursifnya, sedangkan 0!=10! = 1 dan 1!=11! = 1 menjadi kasus dasarnya.

Skrip berikut mendeklarasikan faktorial() dengan kedua bagian tersebut. Pernyataan if memeriksa kasus dasar terlebih dahulu, dan pemanggilan faktorial($n - 1) memastikan setiap tahap menurunkan nilai $n hingga kasus dasar tercapai.

php faktorial.php 
<?php
declare(strict_types=1);

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

foreach ([1, 3, 6, 10] as $n) {
    echo $n, '! = ', faktorial($n), "\n";
}
text Keluaran 
1! = 1
3! = 6
6! = 720
10! = 3628800

Cara kerjanya dapat ditelusuri pada faktorial(3). PHP menunda setiap perkalian hingga pemanggilan terdalam selesai, karena nilai $n * faktorial($n - 1) baru dapat dihitung setelah pemanggilan dalam mengirimkan hasilnya. Diagram berikut memperlihatkan pemanggilan yang menumpuk sampai kasus dasar tercapai, lalu nilai kembali satu per satu hingga hasil akhir terbentuk.

pemanggilan menumpukfaktorial(3)faktorial(2)faktorial(1)kasus dasarmengembalikan 1mengembalikan 2mengembalikan 6nilai kembali menurun
Tumpukan panggilan faktorial(3) sampai kasus dasar, lalu nilai kembali berurutan

Penelusuran direktori#

Penelusuran direktori adalah penerapan rekursi yang muncul terus-menerus pada pekerjaan nyata, karena struktur folder bertingkat adalah data berbentuk pohon. Fungsi rekursifnya membaca isi satu direktori, mencetak setiap berkas yang ditemukan, dan memanggil dirinya lagi untuk setiap subdirektori. Kasus dasarnya tidak ditulis eksplisit sebagai pernyataan if. Kondisi itu muncul secara alami, yaitu entri yang bukan direktori langsung dicetak tanpa pemanggilan lanjutan.

Fungsi scandir() mengembalikan isi direktori sebagai array nama, termasuk entri . dan ... Kedua entri tersebut merujuk pada direktori itu sendiri dan induknya, sehingga keduanya harus dilewati agar penelusuran tidak berputar tanpa akhir. Fungsi is_dir() memisahkan subdirektori dari berkas biasa dan menjadi penentu apakah fungsi memanggil dirinya lagi.

Siapkan struktur arsip contoh berikut, lalu simpan dan jalankan skrip penelusurannya. Keluarannya berupa jalur relatif terhadap direktori kerja, dengan urutan yang mengikuti urutan alfabetis hasil scandir().

bash 
# buat struktur arsip contoh
mkdir -p arsip/2024
mkdir -p arsip/2025/laporan
touch arsip/2024/catatan.txt
touch arsip/2025/ringkasan.txt
touch arsip/2025/laporan/q1.txt
touch arsip/2025/laporan/q2.txt
php telusuri.php 
<?php
declare(strict_types=1);

function telusuri(string $direktori): void
{
    foreach (scandir($direktori) as $entri) {
        if ($entri === '.' || $entri === '..') {
            continue;
        }
        $jalur = $direktori . '/' . $entri;
        if (is_dir($jalur)) {
            telusuri($jalur);
        } else {
            echo $jalur, "\n";
        }
    }
}

telusuri('arsip');
text Keluaran 
arsip/2024/catatan.txt
arsip/2025/laporan/q1.txt
arsip/2025/laporan/q2.txt
arsip/2025/ringkasan.txt

Skrip ini dapat langsung digunakan sebagai kerangka untuk pekerjaan lanjutan, misalnya menghitung ukuran total arsip atau mencari berkas yang memuat kata tertentu, karena logika tambahan ditempatkan pada cabang else.

Batas kedalaman dan alternatif#

Setiap pemanggilan fungsi menyisakan satu bingkai pada tumpukan panggilan (call stack), yaitu data yang menyimpan parameter dan variabel lokal pemanggilan tersebut. Bingkai tersebut baru selesai diproses setelah kasus dasar tercapai, sehingga rekursi yang dalam menumpuk banyak bingkai pada saat bersamaan. Apabila kedalaman itu melebihi batas memori yang diizinkan PHP, eksekusi berhenti dengan error fatal, dan error itu baru muncul setelah tumpukan benar-benar penuh.

Karena itu, rekursi paling tepat digunakan pada data yang memang berbentuk pohon dengan kedalaman wajar, misalnya struktur direktori, array bersarang, atau kategori bertingkat. Untuk masukan yang datar dan panjang, perulangan biasa lebih hemat memori karena tidak menumpuk bingkai. PHP juga menyediakan kelas RecursiveDirectoryIterator pada pustaka SPL yang menangani penelusuran direktori tanpa menulis rekursi secara manual, sehingga penelusuran produksi yang berat dapat diserahkan ke kelas tersebut.

Ukuran satu bingkai tidak besar, tetapi jumlahnya bertambah satu untuk setiap tingkat kedalaman, sehingga rekursi dengan masukan ribuan tingkat sudah menumpuk ribuan bingkai. Apabila kebutuhan seperti itu muncul, tuliskan ulang algoritmanya dengan perulangan dan struktur data perantara, misalnya array yang berperan sebagai tumpukan eksplisit, sehingga penggunaan memorinya dapat dikendalikan.

Kesalahan umum#

  • Kasus dasar tidak pernah tercapai. Fungsi yang memanggil faktorial($n) alih-alih faktorial($n - 1) berputar pada masukan yang sama terus-menerus, sehingga eksekusi berhenti karena kehabisan memori. Periksa setiap langkah rekursif dan pastikan masukannya mendekati kasus dasar.
  • Hasil pemanggilan dalam tidak dikembalikan. Menulis faktorial($n - 1); tanpa return membuang hasil perhitungan pemanggilan tersebut, sehingga fungsi mengembalikan nilai yang salah atau null. Setiap pemanggilan rekursif yang hasilnya digunakan harus berada pada pernyataan return.
  • Lupa melewati entri . dan .. saat menelusuri direktori. Kedua entri itu merujuk pada direktori sendiri dan induknya, sehingga pemanggilan rekursif atas keduanya berputar tanpa akhir. Lewati keduanya di awal perulangan sebelum pemanggilan lanjutan.
  • Menelusuri direktori tanpa menguji izin aksesnya. Fungsi scandir() mengembalikan false pada direktori yang tidak dapat dibaca, sehingga perulangan foreach atas nilai false langsung memicu peringatan. Periksa hasil scandir() sebelum perulangan bila struktur direktori belum tentu dapat diakses seluruhnya.

Contoh berikut hanya memperlihatkan bentuk fungsi tanpa kasus dasar. Skripnya sengaja tidak dijalankan karena eksekusinya tidak akan berhenti.

php Contoh: rekursi tanpa kasus dasar 
// tidak-dijalankan
function tanpaHenti(int $n): int
{
    return $n * tanpaHenti($n - 1);  // tidak pernah mencapai kasus dasar
}

Ringkasan#

  • Fungsi rekursif memanggil dirinya dengan masukan yang lebih kecil dan wajib memuat kasus dasar yang menghentikan pemanggilan.
  • PHP menunda perhitungan di titik pemanggilan sampai pemanggilan terdalam selesai, sehingga hasil akhir terbentuk saat bingkai tumpukan dilepas satu per satu.
  • Penelusuran direktori menggunakan rekursi secara alami, dengan scandir(), is_dir(), dan penanganan entri . serta .. sebagai bagian intinya.
  • Setiap pemanggilan menyisakan bingkai pada call stack, sehingga rekursi yang dalam berisiko kehabisan memori dan masukan datar sebaiknya ditangani perulangan biasa.

Referensi#