Qayta chaqirishlarni samaradorligini oshirish uchun qanday optimallashtirish mumkin?

Rekursiv chaqiriqlarni optimallashtirish uchun ko'pincha quyidagi usullar qo'llaniladi:

1. Memoizatsiya — allaqachon hisoblangan chaqiriqlarning natijalarini saqlash, takroriy hisoblashlarni oldini olish uchun. Bu, ayniqsa, qisman qoplanadigan muammolar, masalan, Fibonacci sonlarini hisoblashda foydalidir.

2. Tayt rekursiya — agar rekursiv chaqiriq funksiya oxirgi operatsiya bo'lsa, kompilyator chaqirishni optimallashtirib, uni siklga aylantirishi mumkin, bu esa stekdagi xotira sarfini kamaytiradi.

3. Rekursiyani iteratsiyaga aylantirish — ba'zan, rekursiv algoritmni sikl shaklida yozish mumkin, bu esa funksiya chaqiruvlarining ortiqcha xarajatlarini butunlay olib tashlaydi.

C++ da Fibonacci sonlarini hisoblash uchun memoizatsiya misoli:

#include <unordered_map>

std::unordered_map<int, long long> memo;

long long fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Bu yondashuv naiv rekursiyaga qaraganda hisoblashlarni sezilarli darajada tezlashtiradi.