Превратить рекурсивную функцию в цикл for?

Question

У каждой рекурсивной функции есть эквивалент для цикла? (Оба достигают одного и того же результата).

У меня есть эта рекурсивная функция:

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    if(words[length].contains(word.substring(0, length)))
        return recur(word.substring(length), word.length() - length);
    return recur(word, length-1);
}

Учитывая, что слова - это Набор [], и где слова [i] = набор со словами длиной i.

Что я пытаюсь сделать, это: инициировать рекурсию со словом (скажем, «stackoverflow», без пробелов), я пытаюсь найти, можно ли это слово разрезать на подслова («stack», «over», «flow») .. минимальная длина подслова равно 3, и учитывая, что подслово длины i находится в наборе слов [i].

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

Вам нужна дополнительная информация?

Спасибо.

Answer 1

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

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    int nextLength;
    String nextWord;
    if(words[length].contains(word.substring(0, length))) {
      nextWord = word.substring(length);
      nextLength = word.length() - length;
    } else {
      nextWord = word;
      nextLength = length - 1;
    }
    return recur(nextWord, nextLength);
}

Теперь это правильная хвостовая рекурсияТеперь, чтобы превратить его в цикл:

private static boolean recur(String word, int length) {
    int nextLength = length;
    String nextWord = word;
    while( true ) {
        if(nextLength == 1 || nextLength == 2)
            return false;
        if(nextLength == 0)
            return true;
        if(words[nextLength].contains(nextWord.substring(0, nextLength))) {
            nextWord = nextWord.substring(nextLength);
            nextLength = nextWord.length() - nextLength;
        } else {
            nextWord = nextWord;
            nextLength = nextLength - 1;
        }
    }
}

Обратите внимание, что этот код может быть дополнительно оптимизирован, я просто хотел продемонстрировать «автоматический» метод превращения рекурсии в цикл.

Answer 2

Для общего вопроса: Да, каждая рекурсия может быть преобразована в цикл.Вы можете явно моделировать стек, созданный и используемый рекурсией, и изменить его в цикле.

Для конкретной проблемы:

Рассматривая свой код как функцию и игнорируя побочные эффекты, я думаю, вы можете просто вернуть false.

Если вам действительно нужны разделенные слова, попробуйтеследующее:

have a list with the word to split.
iterate until list after iteration is the same as before.
    iterate over list
        if the word can be split, replace it in the list with its parts
    end of loop
end of loop

Answer 3

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

Длинный ответ:

Во-первых, итерационная версия вашего рекурсивного метода:

private static boolean recur(String word, int length) {
    while(true) {
        if(length == 1 || length == 2)
            return false;
        if(length == 0)
            return true;
        if(words[length].contains(word.substring(0, length))) {
            int newlen = word.length() - length;
            word = word.substring(length);
            length = newlen;
        }
        else {
            --length;
        }
    }
}

Это работает, заменяя рекурсивный вызов назначением параметров и помещая все это в цикл.

Но, как и ваш оригинальный код, он содержит ошибку!

(Я не могу вспомнить реальные слова, с которыми работает эта ошибка, поэтому представьте, что мои выдуманные слова - настоящие слова.)

Предположим, ваше длинное слово - ABCDEFGH, а ABCD, EFGH и ABCDE - все слова, но FGH - нет. recur сначала ищет самое длинное слово, поэтому оно будет соответствовать ABCDE, затем обнаружит, что FGH - не слово, и скажет вам, что ABCDEFGH нельзя разрезать на подслово.

Но это можно разделить на ABCD и EFGH! Он пропускает более короткое начальное совпадение, потому что вы не рассматриваете другие варианты, как только нашли совпадение. (И если ваш код начинается с поиска более короткого соответствия, он все равно не сработает, если ABC будет словом, а DEFGH - нет.)

Итак:

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    return (words[length].contains(word.substring(0, length)))
            && recur(word.substring(length), word.length() - length))
           || recur(word, length-1);
}

Теперь превратить это в итеративный метод сложнее: иногда у вас есть два рекурсивных вызова. Это означает, что простое назначение параметров не будет работать, потому что вам нужны исходные значения параметров для расчета параметров для второго вызова. Вы должны явно управлять стеком или очередью со всеми различными значениями, потому что теперь язык не делает это за вас.

Answer 4

Я отвечаю на ваш первый вопрос: да, у каждой рекурсивной функции есть итерационный эквивалент. Читать дальше .

Это также отчасти связано с CPS (не совсем потому, что хвостовые вызовы не поддерживаются популярными виртуальными машинами Java). Преобразование хвостовой рекурсивной функции (такой как в вопросе) должно быть особенно простым.

Answer 5

@ biziclop демонстрирует, как сделать код нерекурсивным.Я бы пошел дальше и сократил код так, чтобы.

• length больше не передавался в качестве аргумента.
• Два цикла используются для упрощения логики.
• изменить значение локального слова для упрощения.

код

private static boolean recur(String word) {
    LOOP: for(;;) {
        for (int len = word.length(); len >= 3; len--)
            if (words[len].contains(word.substring(0, len))) {
                word = word.substring(len);
                continue LOOP;
            }
        return word.length() == 0;
    }
}