3

すべての再帰関数には同等の for ループがありますか? (どちらも同じ結果になります)。

私はこの再帰関数を持っています:

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

words が Set[] であるとすると、words[i] = 長さ i の単語のセットです。

やろうとしていることは次のとおりです。単語で再帰を開始します（たとえば、「stackoverflow」、スペースなし）。この単語をサブワード（「stack」、「over」、「flow」）に分割できるかどうかを確認しようとしています.. サブワードの最小長は 3 であり、長さ i のサブワードが Set words[i] にあるとします。

このコードが動作することは確認できますが、メモリに問題がある可能性があるため、可能であればループにしたいと考えています。

もっと情報が必要ですか??

ありがとう。

4

5 に答える 5

6

末尾再帰は常にループに展開でき、コードは末尾再帰にかなり近いので、そうです。

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

このコードはさらに最適化できることに注意してください。再帰をループに変える「自動」方法を示したかっただけです。

于 2011-02-10T11:21:12.930 に答える
5

一般的な質問: はい、すべての再帰はループ内で変換できます。再帰によって作成および使用されるスタックを明示的にモデル化し、ループ内で変更できます。

特定の問題について：

コードを関数として見て、副作用を無視すると、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
于 2011-02-10T11:22:02.717 に答える
2

短い答え: 一般的にはできますが、この場合は簡単にできますが、コードのロジックのバグを修正する場合は、自分でスタックを維持することを心配する必要があります。

長い答え:

まず、再帰メソッドの反復バージョン:

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

ここで、これを反復メソッドに変えるのは難しくなります。2 つの再帰呼び出しがある場合があります。つまり、2 回目の呼び出しのパラメーターを計算するには、パラメーターの元の値が必要になるため、単純にパラメーターに割り当てるだけでは機能しません。スタックまたはキューをすべて異なる値で明示的に管理する必要があります。これは、言語がそれを行っていないためです。

于 2011-02-10T11:19:57.327 に答える
1

あなたの最初の質問に答えます: はい、すべての再帰関数には同等の反復があります。続きを読む.

これもCPSに関連しています (一般的な Java VM ではテール コールが実際にサポートされていないためではありません)。末尾再帰関数 (問題の関数など) の変換は特に簡単です。

于 2011-02-10T11:18:32.903 に答える
0

@biziclop は、コードを非再帰的にリファクタリングする方法を示しています。さらに進んでコードを削減します。

  • はlength引数として渡されなくなりました。
  • ロジックを単純化するために 2 つのループが使用されます。
  • 単純化するためにローカル ワード値を変更します。

コード

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;
    }
}
于 2011-02-10T11:44:20.463 に答える