Как перевести внешнюю рекурсивную программу в нерекурсивную форму (используя стек, а не CPS)？

Question

Есть много вопросов о том, как преобразовать рекурсивные в нерекурсивные, и я также могу преобразовать некоторые рекурсивные программы в нерекурсивную форму. Я использую Java, поэтому не могу использовать ключевое слово GOTO.

Не всегда все идет хорошо, когда я встречаюсь с Backtracking, я застреваю. например, проблема подмножества. и мой код здесь: рекурсивный вызов с циклом

когда я использую пользовательский стек, чтобы превратить его в нерекурсивную форму. Я не знаю, как бороться с циклом (в цикле существует рекурсивный вызов).

Я гуглил, обнаружил, что есть много методов, таких как CPS. и я знаю, что есть итерационный шаблон проблемы подмножества. но я только хочу использовать пользовательский стек для решения.

Может ли кто-нибудь дать некоторые подсказки, чтобы превратить этот вид рекурсии (рекурсивный с циклом) в нерекурсивную форму (используя пользовательский стек, а не CPS и т. Д.)?

Вот мой код, рекурсивный к нерекурсивному ( Inorder -Traversal), потому что нет цикла с рекурсивным вызовом, так что я могу легко это сделать. также, когда рекурсивная программа с возвращаемым значением, я могу использовать ссылку и передать ее функции в качестве параметра. Исходя из кода, я использую Stack для имитации рекурсивного вызова и использую переменную "state" для следующей точки вызова (потому что Java не позволяет использовать GOTO).

Ниже приведена информация, которую я собрал. Кажется, что все они не удовлетворяют упомянутому мною вопросу (некоторые используют goto, что java не разрешен, некоторые очень просты рекурсивно, что означает отсутствие вложенного рекурсивного вызова или рекурсивного вызова с циклом).

1 Университет Старого Доминиона

2 кодпроекта

---------------------------------- Разделить линию -------------- ------------------------

Спасибо всем. после того, как я отправлю вопрос... Мне потребовалась вся ночь, чтобы понять это. вот мое решение: нерекурсивное решение проблемы подмножества, и комментарий кода - моя идея.

Подводить итоги. То, что я застрял раньше, это как обращаться с циклом foo, на самом деле, мы можем просто проигнорировать это. Поскольку мы используем loop+stack, мы можем сделать простое суждение о том, выполнять ли условия.

Answer 1

Задумывались ли вы над своим стеком над i (переменная итерации)? Делая это, когда вы выталкиваете это значение, вы знаете, на какой итерации цикла вы были до того, как вы поместили в стек, и, следовательно, вы можете перейти к следующему i и продолжить свой алгоритм.

Answer 2

Неотрицательные числа только для простоты. (Также нет IntFunction.)

power Функция, как определено здесь, является очень простым случаем.

int power(int x, int exponent) {
    if (exponent == 0) {
        return 1;
    } else if (exponent % 2 == 0) {
        int y = power(x, exponent /2);
        return y * y;
    } else {
        return x * power(x, exponent - 1);
    }
}

Теперь этот стек нужно сделать в порядке, обратном частичному результату, что вы сделали в рекурсии с результатом.

int power(final int x, int exponent) {
    Stack<Function<Integer, Integer>> opStack = new Stack<>();
    final Function<Integer, Integer> square = n -> n * n;
    final Function<Integer, Integer> multiply = n -> x * n;
    while (exponent > 0) {
        if (exponent % 2 == 0) {
            exponent /= 2;
            opStack.push(square);
        } else {
            --exponent;
            opStack.push(multiply);
        }
    }
    int result = 1;
    while (!opStack.isEmpty()) {
        result = opStack.pop().apply(result);
    }
    return result;
}

Альтернативой может быть "кодирование" двух ветвей if-else (нечетная / четная экспонента) с помощью логического значения:

int power(final int x, int exponent) {
    BooleanStack stack = new BooleanStack<>();
    while (exponent > 0) {
        boolean even = exponent % 2 == 0;
        stack.push(even);
        if (even) {
            exponent /= 2;
        } else {
            --exponent;
        }
    }
    int result = 1;
    while (!stack.isEmpty()) {
        result *= stack.pop() ? result : x;
    }
    return result;
}

Так что надо расстраивать

• что нужно сделать, чтобы подготовить рекурсивные аргументы
• что делать с частичными результатами рекурсивных вызовов
• как можно объединить / обработать несколько рекурсивных вызовов в функции
• эксплуатировать хорошие вещи, как x будучи последней константой

Не сложно, может быть загадочно, так что веселитесь.