Ответ 1
Простейшим/наиболее общим способом устранения рекурсии, в общем, является использование вспомогательного стека - вместо того, чтобы делать рекурсивные вызовы, вы вставляете их аргументы в стек и повторяете. Когда вам понадобится результат рекурсивного вызова, чтобы продолжить, опять же в общем случае, что еще сложнее, потому что вам также придется нажать "запрос продолжения" (который выйдет из вспомогательного стек, когда результаты известны); однако в этом случае, поскольку все, что вы делаете со всеми результатами рекурсивного вызова, является суммированием, достаточно держать накопитель, и каждый раз, когда вы получаете результат числа, вместо необходимости делать больше вызовов, добавьте его в аккумулятор.
Однако это само по себе не является фиксированным пространством, так как этот стек будет расти. Итак, еще одна полезная идея: поскольку это чистая функция (без побочных эффектов), каждый раз, когда вы обнаруживаете, что вычислили значение функции для определенного набора аргументов, вы можете memoize соответствие аргументов-результатов. Это ограничит количество вызовов. Другим концептуальным подходом, который приводит к таким же вычислениям, является динамическое программирование [[aka DP]], хотя с помощью DP вы часто работаете снизу вверх результаты должны быть запомнены ", так сказать, вместо того, чтобы начинать с рекурсии и работать над ее устранением.
Возьмите снизу вверх DP на эту функцию, например. Вы знаете, что вы будете в конечном итоге "иметь много способов внести изменения в сумму X с помощью самой маленькой монеты" (поскольку вы уменьшаете вещи до X с различными комбинациями монет из оригинала amount), поэтому вы начинаете вычислять эти amount значения с простой итерацией (f (X) = X/value, если X точно делится на наименьшее значение монеты value, else 0, здесь value равно 1, поэтому f (X) = X для всех X > 0). Теперь вы продолжаете вычислять новую функцию g (X), способы внести изменения для X с двумя наименьшими монетами: снова простая итерация для увеличения X, причем g (x) = f (X) + g (X - value) для value второй наименьшей монеты (это будет простая итерация, потому что к тому времени, когда вы вычисляете g (X), вы уже вычислили и сохранили f (X) и все g (Y) для Y < X - конечно, g (X) = 0 для всех X <= 0). И снова для h (X), способы сделать изменения для X с тремя наименьшими монетами - h (X) = g (X) + g (X- value), как указано выше, - и теперь вы выиграли ' t нужно f (X), чтобы вы могли повторно использовать это пространство. Всем сказали, что для этого потребуется пространство 2 * amount - не "фиксированное пространство", но, приближаясь...
Чтобы сделать окончательный переход к "фиксированному пространству", спросите себя: вам нужно поддерживать все значения двух массивов на каждом шаге (тот, который вы последний раз вычисляли, и тот, который вы сейчас вычисляете), или только некоторые из этих значений, немного изменив ваш цикл...?