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

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

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;
        }
    }
}

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

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

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

Глядя на свой код как на функцию и игнорируя побочные эффекты, я думаю, вы могли бы просто вернуть 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

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

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

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

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 — нет.)

So:

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);
}

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

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

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

@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;
    }
}