Ответ
Основные способы оптимизации рекурсии в C++ — это мемоизация (кэширование результатов) и переход на итеративный алгоритм.
1. Мемоизация (сверху вниз): Сохраняем результаты вычислений для уже обработанных входных данных, чтобы избежать повторных вызовов.
#include <unordered_map>
#include <iostream>
std::unordered_map<int, long long> fib_cache;
long long fib_memo(int n) {
if (n <= 1) return n;
// Проверяем кэш
auto it = fib_cache.find(n);
if (it != fib_cache.end()) {
return it->second;
}
// Вычисляем и сохраняем
long long result = fib_memo(n - 1) + fib_memo(n - 2);
fib_cache[n] = result;
return result;
}
int main() {
std::cout << fib_memo(50) << std::endl; // Считает быстро
return 0;
}2. Итеративный подход (снизу вверх): Полностью заменяем рекурсивные вызовы циклом. Это устраняет накладные расходы на вызов функции и работу со стеком.
long long fib_iterative(int n) {
if (n <= 1) return n;
long long a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) {
c = a + b;
a = b;
b = c;
}
return b;
}3. Ручное управление стеком: Для сложных рекурсивных алгоритмов (например, обход дерева) можно эмулировать стек вызовов.
#include <stack>
struct Frame {
TreeNode* node;
int state; // 0: посетить левое поддерево, 1: обработать узел, 2: посетить правое
};
void inorder_iterative(TreeNode* root) {
std::stack<Frame> st;
st.push({root, 0});
while (!st.empty()) {
auto& f = st.top();
if (!f.node || f.state == 2) {
st.pop();
continue;
}
if (f.state == 0) {
f.state = 1;
st.push({f.node->left, 0});
} else if (f.state == 1) {
std::cout << f.node->val << " ";
f.state = 2;
st.push({f.node->right, 0});
}
}
}Выбор подхода: Мемоизация проще для внедрения, когда рекурсивная структура сохраняется. Итеративный подход обычно даёт максимальную производительность и предсказуемое использование памяти.
Ответ 18+ 🔞
Давай разберем, как эти рекурсивные выверты в C++ можно приструнить, а то они иногда жрут память и время, как не в себя.
1. Мемоизация, или "запоминайка" (сверху вниз): Суть проще пареной репы: раз уж посчитал что-то — запиши, чтобы второй раз не ебаться. Как будто шпаргалку ведёшь.
#include <unordered_map>
#include <iostream>
std::unordered_map<int, long long> fib_cache; // Вот наш тайник
long long fib_memo(int n) {
if (n <= 1) return n;
// Сначала лезем в кэш — вдруг уже считали?
auto it = fib_cache.find(n);
if (it != fib_cache.end()) {
return it->second; // О, повезло! Уже есть!
}
// Не повезло — придётся считать по-честному
long long result = fib_memo(n - 1) + fib_memo(n - 2);
fib_cache[n] = result; // Обязательно прячем результат на будущее
return result;
}
int main() {
std::cout << fib_memo(50) << std::endl; // Считает быстро, а без кэша был бы пиздец
return 0;
}2. Итеративный подход (снизу вверх): А это вообще красота — выкидываем рекурсию нахуй и делаем всё циклом. Никакого стека, никаких вызовов — чистая арифметика. Просто и гениально.
long long fib_iterative(int n) {
if (n <= 1) return n;
long long a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) {
c = a + b; // Новое число
a = b; // Сдвигаемся
b = c;
}
return b; // Вот и ответ
}3. Ручное управление стеком (для сложных случаев): Бывает, рекурсия такая хитрая, что просто так в цикл не перепишешь — например, обход дерева. Тогда делаем финт ушами: сами эмулируем стек, как настоящие пацаны.
#include <stack>
struct Frame {
TreeNode* node;
int state; // 0: лезть влево, 1: обработать узел, 2: лезть вправо
};
void inorder_iterative(TreeNode* root) {
std::stack<Frame> st;
st.push({root, 0});
while (!st.empty()) {
auto& f = st.top();
if (!f.node || f.state == 2) {
st.pop(); // Всё, с этим узлом покончили
continue;
}
if (f.state == 0) {
f.state = 1; // Готовимся к обработке
st.push({f.node->left, 0}); // Лезем в левого потомка
} else if (f.state == 1) {
std::cout << f.node->val << " "; // Делаем что надо
f.state = 2;
st.push({f.node->right, 0}); // Теперь правый
}
}
}Что в итоге выбирать? Мемоизация — это как костыль, но золотой: влепил в существующую рекурсию и сразу хорошо. Итеративный подход — это полный пересмотр алгоритма, зато потом летает и памяти почти не жрёт. Для особо изощрённых случаев, где рекурсия — ёперный театр, бери ручное управление стеком. Главное — не тупи и думай, что тебе на самом деле нужно, а то можно и так и эдак переписать, а толку — хуй с горы.