RekursiMenengahFase D–FE1E5

Fibonacci: Memo vs Naif

Fibonacci naif menghitung ulang subpohon yang sama berkali-kali sehingga pohon rekursi meledak. Memoization menyimpan hasil tiap nilai sekali (cache), sehingga panggilan berulang langsung dipakai ulang. Gerbang paling halus dari rekursi menuju Dynamic Programming.

Contoh kasus

Optimasi fungsi rekursif apa pun yang menghitung ulang hal sama: simpan hasil agar tak dihitung dua kali.

Silabus

Memoization menyimpan hasil tiap perhitungan sekali di cache, mengubah Fibonacci naif yang meledak jadi sangat cepat.

Tujuan Belajar

·Memahami kenapa Fibonacci naif menghitung ulang hal yang sama
·Menjelaskan cara cache menyimpan hasil agar dipakai ulang
·Menerapkan memoization sebagai jembatan ke Dynamic Programming

Cara Kerja

·Fibonacci naif memanggil dirinya dua kali sehingga subpohon berulang
·Siapkan cache untuk menyimpan hasil tiap nilai yang sudah dihitung
·Sebelum menghitung, cek dulu apakah hasilnya sudah ada di cache
·Bila ada, langsung pakai; bila belum, hitung lalu simpan ke cache
·Perhitungan berulang jadi hilang sehingga jauh lebih cepat

Prasyarat

·Rekursi
·Array atau map

Contoh Nyata

·Menyimpan hasil perhitungan berat agar tidak diulang di aplikasi
·Cache skor atau data yang sering diminta ulang di game
·Mempercepat fungsi yang dipanggil berkali-kali dengan input sama

Kompleksitas O(n) dengan memo, dibanding O(2^n) versi naif