Yodda saqlash bilan rekursiya

Yodlab qolish (memoization) bilan rekursiya

Rekursiyadan foydalanganda ba’zan bir xil qiymatni bir necha marta hisoblab qo‘yamiz.
Misol uchun, Fibonachchi sonlarini va $F(5)$ qiymatini hisoblash uchun rekursiya ishlash sxemasini ko‘rib chiqamiz.

E’tibor bering, $F(3)$ ikki marta, $F(2)$ esa — butun uch marta hisoblangan!
Bunda ularning qiymatlari hech qachon o‘zgarmaydi, va bir xil qiymatlarni qayta-qayta hisoblamaslik mumkin edi. Buni qanday yaxshilash mumkin?

Bu muammoning yechimi — eslab qolish (memoization).
G‘oya shundan iboratki, massiv yaratib, allaqachon hisoblangan qiymatlarni saqlab boramiz.

Shunda rekursiya $F(n)$ chaqirilganda quyidagi qadamlar bajariladi: