RecursionMenengahFase D–FE1E5

FIBONACCI: MEMO VS NAIVE

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Rekursi
·Array atau map

Real-World Uses

·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

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