Превратить рекурсивную функцию в итеративную
У меня есть рекурсивная функция для экспорта информации, и я хочу преобразовать ее в итеративную из соображений эффективности (игрушечная задача ниже). Однако, поскольку после вызова рекурсивной функции в рекурсивной функции есть операторы, я не получаю рабочего итеративного решения.
#include <iostream>
#include <stack>
using namespace std;
int n = 100;
int iMax = 2;
void fRecursive(int x)
{
int u = 2 * x + 1;
cout << u - 10 << ": ";
if (u > n)
return;
for (int i = 0; i < iMax; ++i)
{
cout << u << "-" << i << " ";
fRecursive(u);
cout << "break" << endl;
}
}
void fIterative(int x0)
{
std::stack<int> myStack;
myStack.push(x0);
while (!myStack.empty())
{
int curx = myStack.top();
myStack.pop();
int u = 2 * curx + 1;
cout << u - 10 << ": ";
if (u > n)
continue;
for (int i = 0; i < iMax; ++i)
{
myStack.push(u);
cout << u << "-" << i << " ";
cout << "break\n";
}
}
}
int main()
{
int x0 = 10;
cout << "Start Recursion" << endl;
fRecursive(x0);
cout << "End Recursion" << endl << endl;
cout << "Start Iterative" << endl;
fIterative(x0);
cout << "End Iterative" << endl << endl;
return 0;
}
Мне удалось поменять рекурсивные функции на итеративные, когда после вызова рекурсивной функции нет блока кода, но не удалось это сделать, когда эта функция есть.
Способ кодирования итеративной версии может быть не намного более эффективным, чем рекурсивный (если вообще будет). Это, конечно, более непрозрачно. Вычисление полинома — более частый и конкретный пример, когда итеративные методы побеждают рекурсивные.
@PepijnKramer Ну, есть «автоматический»/«механический» способ, поскольку вы всегда можете заменить стек вызовов на std::vector (или какой-то реальный контейнер стека) и, по сути, сделать то же самое, что и рекурсивная реализация, эмулируя рекурсия. Тем не менее, я определенно согласен с той частью, где это нежизнеспособное решение, и что все это следует пересмотреть - или оставить как рекурсивный, если нет хорошего решения и нет реальной выгоды от того, чтобы сделать его нерекурсивным (например, только имеет небольшой стек и сталкивается с переполнением).
Мое правило: максимальная глубина рекурсии для рекурсивной функции должна быть O(log n). Если глубина равна O(log n), как в этом примере, обычно лучше использовать рекурсивный метод. Однако наличие глубины O(n) вызвало бы проблемы: оно быстро рухнет с (не очень) большим n. И этот тип рекурсивной функции можно очень легко преобразовать в цикл, который легче понять, легче отлаживать, безопаснее и быстрее.
Ответы 1
В качестве общего решения вы можете имитировать помещение состояния в стек. Соответствующий контекст, который вам нужен, также включает значение i, поэтому вы можете складывать пары x и i. В некоторых практических сценариях (например, в этом игрушечном примере) вы можете найти способы сделать это без этого дополнительного элемента в стеке, но я считаю, что для более общего подхода вы бы хотели, чтобы это i (или что-то еще, с чем вы выполняете итерацию) складывалось как хорошо.
Вот как это будет выглядеть для вашего примера:
#include <tuple>
void fIterative(int x) {
std::stack<std::pair<int, int>> myStack;
while (true) {
int u = 2 * x + 1, i = 0;
std::cout << u - 10 << ": ";
myStack.push({u, 0});
while (true) {
std::tie(x, i) = myStack.top(); // or [x, i] = ... C++17
myStack.pop();
if (i < iMax && x <= n) {
break;
}
if (myStack.empty()) {
return;
}
std::cout << "break" << std::endl;
}
std::cout << x << "-" << i << " ";
myStack.push({x, i+1});
}
}
В качестве примечания: я обычно не использую std::pair или std::tuple — я предпочитаю классы с участниками, имеющими описательные имена, а не «первый» и «второй». Ваш случай еще хуже, поскольку оба имеют один и тот же тип, поэтому компилятор ничего не сможет сделать, если вы случайно перепутаете использование «первого» и «второго».
Обычно я не «конвертирую» алгоритмы. Я понимаю, что алгоритм пытается решить, и реализую новый код. Автоматизированного способа не существует, и, возможно, использование стека тоже не так уж и хорошо. Вот что вы можете прочитать: baeldung.com/cs/factorial-recursion-to-iteration