6-5: Recursive Function

Objectives

• Memahami recursion
• Membuat recursive function
• Base case dan stack overflow
• Memahami kapan recursion tepat digunakan
• Mengoptimalkan recursion (memoization)

Apa itu Recursion?

Function yang memanggil dirinya sendiri.

┌─────────────────────────────────────────────────────────┐
│   RECURSION = FUNCTION CALLS ITSELF                      │
├─────────────────────────────────────────────────────────┤
│                                                          │
│   function countDown($n) {                              │
│       if ($n <= 0) return;                             │
│       echo "$n\n";                                      │
│       countDown($n - 1);  // Call itself!               │
│   }                                                    │
│                                                          │
└─────────────────────────────────────────────────────────┘

Recursion seperti cermin yang menghadap cermin: ada gambar di dalam gambar di dalam gambar. Setiap pemanggilan function membuat "salinan" baru dari function itu dengan data barunya sendiri, sampai akhirnya mencapai kondisi berhenti.

Dua bagian wajib dari recursion:

1. Base case — kondisi berhenti. Tanpa ini, function memanggil dirinya selamanya.
2. Recursive case — pemanggilan diri sendiri dengan masalah yang lebih kecil (biasanya nilai parameter mengecil).

Basic Recursion

<?php

function countDown($n) {
    if ($n <= 0) {
        return;  // Base case
    }
    echo "$n\n";
    countDown($n - 1);  // Recursive call
}

countDown(5);

/*
Output:
5
4
3
2
1
*/

?>

Mari kita telusuri apa yang terjadi saat countDown(5) dipanggil:

Setiap pemanggilan menunggu pemanggilan di dalamnya selesai dulu. PHP menyimpan "jejak" pemanggilan ini di call stack — tumpukan memori khusus. Jika pemanggilan tidak pernah berhenti, tumpukan ini penuh dan terjadi stack overflow.

Factorial

<?php

// Iterative
function factorialIterative($n) {
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    return $result;
}

// Recursive
function factorialRecursive($n) {
    if ($n <= 1) {
        return 1;  // Base case
    }
    return $n * factorialRecursive($n - 1);
}

echo factorialIterative(5);  // 120
echo factorialRecursive(5);  // 120

?>

Faktorial secara matematis didefinisikan secara rekursif:

5! = 5 × 4 × 3 × 2 × 1 = 120
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1   ← base case

Rumusnya: n! = n × (n-1)!, dan berhenti di 1! = 1. Definisi ini "menyuruh" kita menulis recursion — kode recursive function sering terlihat persis seperti rumus matematikanya.

Fibonacci

<?php

function fibonacci($n) {
    if ($n <= 1) {
        return $n;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}

for ($i = 0; $i < 10; $i++) {
    echo fibonacci($i) . " ";
}
// 0 1 1 2 3 5 8 13 21 34

?>

Deret Fibonacci: setiap angka adalah penjumlahan dua angka sebelumnya (0, 1, 1, 2, 3, 5, 8, ...). Secara rekursif: fib(n) = fib(n-1) + fib(n-2) dengan base case fib(0) = 0 dan fib(1) = 1.

Base Case & Stack Overflow

<?php

// ❌ STACK OVERFLOW - no base case!
function infinite($n) {
    echo "$n ";
    infinite($n + 1);  // Never stops!
}

// infinite(1);  // Will crash!

// ✅ DENGAN BASE CASE
function safe($n) {
    if ($n > 1000) {
        return;  // Base case - stop at 1000
    }
    echo "$n ";
    safe($n + 1);
}

safe(1);  // 1 2 3 ... 1000

?>

Tanpa base case, function memanggil dirinya terus sampai memori penuh. PHP akan melempar error Fatal error: Allowed memory size exhausted atau Maximum function nesting level reached.

Memoization (Optimasi Fibonacci)

Memoization menyimpan hasil perhitungan agar tidak dihitung ulang:

<?php

function fibonacciMemo($n, &$cache = []) {
    if ($n <= 1) {
        return $n;
    }

    // Sudah pernah dihitung? Langsung ambil dari cache
    if (isset($cache[$n])) {
        return $cache[$n];
    }

    // Hitung, simpan, lalu kembalikan
    $cache[$n] = fibonacciMemo($n - 1, $cache) + fibonacciMemo($n - 2, $cache);
    return $cache[$n];
}

echo fibonacciMemo(10) . "\n";   // 55
echo fibonacciMemo(40) . "\n";   // 102334155 — instan!
echo fibonacciMemo(50) . "\n";   // 12586269025 — tetap cepat

?>

Perhatikan penggunaan &$cache — parameter by reference memastikan semua pemanggilan recursive berbagi cache yang sama. Tanpa &, setiap pemanggilan membuat cache baru dan optimasi tidak berfungsi.

Contoh Lain: Sum Array

<?php

function sumArray($numbers) {
    // Base case: array kosong
    if (count($numbers) === 0) {
        return 0;
    }

    // Recursive case: elemen pertama + sisa array
    $first = array_shift($numbers);
    return $first + sumArray($numbers);
}

echo sumArray([1, 2, 3, 4, 5]) . "\n";  // 15

?>

Logikanya: sum([1,2,3,4,5]) = 1 + sum([2,3,4,5]) = 1 + 2 + sum([3,4,5]) = ... sampai array kosong.

Contoh Nyata: Struktur Folder

Recursion unggul untuk data yang bersarang tak tentu — seperti folder di dalam folder:

<?php

function printTree($items, $depth = 0) {
    foreach ($items as $item) {
        $indent = str_repeat("  ", $depth);
        echo $indent . $item["name"] . "\n";

        if (!empty($item["children"])) {
            printTree($item["children"], $depth + 1);  // Recurse!
        }
    }
}

$structure = [
    ["name" => "app", "children" => [
        ["name" => "controllers", "children" => [
            ["name" => "UserController.php", "children" => []],
        ]],
        ["name" => "models", "children" => []],
    ]],
    ["name" => "public", "children" => [
        ["name" => "index.php", "children" => []],
    ]],
];

printTree($structure);

/*
Output:
app
  controllers
    UserController.php
  models
public
  index.php
*/

?>

Coba bayangkan menulis ini dengan loop bersarang — kedalaman folder tidak tentu, jadi kamu tidak tahu berapa banyak loop yang dibutuhkan. Recursion menyelesaikannya dengan elegan: setiap kedalaman menangani levelnya sendiri.

When to Use Recursion

Panduan Memilih

• Gunakan recursion jika masalahnya terdefinisi secara rekursif (folder, tree, parsing) — kode jadi singkat dan jelas.
• Gunakan iteration untuk tugas linear sederhana — lebih cepat (tanpa overhead pemanggilan function) dan tanpa risiko stack overflow.
• Untuk kinerja kritis, iteration hampir selalu menang; recursion menang dalam keterbacaan untuk struktur bersarang.

Common Mistakes

Lupa Base Case

<?php

// ❌ Tidak ada base case — stack overflow!
// function countUp($n) {
//     echo "$n ";
//     countUp($n + 1);
// }

// ✅ Base case dulu, baru recursive call
function countUp($n, $max) {
    if ($n > $max) {
        return;
    }
    echo "$n ";
    countUp($n + 1, $max);
}

countUp(1, 5);  // 1 2 3 4 5

?>

Base Case Salah Arah

<?php

// ❌ Base case tidak akan pernah tercapai
// function down($n) {
//     if ($n > 100) return;  // $n mengecil, tidak akan pernah > 100
//     down($n - 1);
// }

// ✅ Base case sesuai arah perubahan parameter
function down($n) {
    if ($n <= 0) return;
    down($n - 1);
}

?>

Recursion Terlalu Dalam

<?php

// ⚠️ Setiap pemanggilan recursive memakai memori stack
function big($n) {
    if ($n <= 0) return;
    big($n - 1);
}

// big(1000000);  // Fatal error: Maximum function nesting level

?>

PHP memiliki batas kedalaman nesting (default xdebug.max_nesting_level atau batas memori). Untuk iterasi yang sangat banyak, gunakan loop biasa, bukan recursion.

Pro Tips

1. Tulis base case pertama — sebelum logika recursive, supaya tidak lupa.
2. Pastikan parameter "mengecil/membesar" menuju base case di setiap pemanggilan.
3. Gunakan memoization (&$cache) untuk recursion yang menghitung ulang nilai sama.
4. Jangan gunakan recursion untuk loop sederhana — loop biasa lebih cepat dan aman.
5. Uji dengan nilai kecil dulu (misal fibonacci(5)) sebelum nilai besar.

Exercise

1. Buat recursive function untuk calculate power ($base^$exp)
2. Buat recursive function untuk reverse string
3. Kenapa recursion untuk Fibonacci lambat? Bagaimana optimasinya?
4. Buat recursive function hitungMundur($n) yang mencetak angka dari $n sampai 1, lalu "Waktu habis!"
5. Buat recursive function untuk menghitung jumlah digit sebuah angka (misal 12345 → 15)
6. Buat function fibonacciMemo dan bandingkan kecepatannya dengan fibonacci biasa untuk n=35

Summary