Pythonの反復法と再帰法を詳しく解説

再帰操作が必要な状況に遭遇しましたが、再帰の回数は非常に多く、10,000回を超えていました。 10,000 回を超える再帰については話さないでください。元のテスト コードは Java にあります。JDK やコンパイル環境はインストールされていません。まず、元の Java コードを見てみましょう。あまり Java で遊んだことはありませんが、これらのコード行はストレスフリーなようです。混乱をすぐに解消して、Python コードに変更しました

public class UpCount {
    private long calc(int depth) {
        if (depth == 0) return 1;
        long cc = calc(depth - 1);
        return cc + (depth % 7) + ((((cc ^ depth) % 4) == 0) ? 1 : 0); 
    }
    public static void main(String[] args) {
        UpCount uc = new UpCount();
        System.out.println(uc.calc(11589));
    }
}

。コードを貼り付けて、F5 キーを押すと問題が発生しました

。コードはもともとlongを追加しませんでした。以前は10個の文字列だったので、いくつかの

整数
を直接使用できるので、それがlongと何か関係があるとは思えません

もちろん、実際には、それはlongとは何の関係もありません

Python でサポートされている整数の長さは非常に長いので、以下のコードを参照してください:

def calc(depth):
    if depth == 0:
        return 1
    cc = long(calc(depth-1))
    xor_mod = (cc ^ depth)%4
    if xor_mod == 0:
        return cc+(depth%7)+1
    else:
        return cc+(depth%7)
 
number = long(calc(11589))
print number

上記のコードは、10 進数の長い文字列を 16 進数に変換することもできます。 8進数と16進数に変換できます。 oct()、hex() 以上です。ユークリッド割り算を使って解いてみましょう

以上で、数値の大きさに誤差がないことがわかります。すべて、11589 は、今日のコンピューター、2^16 と 65536 にとっては朝飯前のことです

実際、ここで、前回の再帰エラーの本当の理由が言及されていないことに気づき、その理由に疲れ果てました。再帰エラーは、Python のデフォルトの再帰制限は約 1,000 回のみですが、ここでは 10,000 回以上実行する必要があるということです。更新に時間がかかりました: Run
time

Error: Maximum recursion Depth Overceed

そこで、すぐに実行しました。確認したところ、再帰の制限を自分で設定できることがわかりました。拡張機能として、公式 Web サイトのドキュメントを確認することもできます

一般に、Python 言語の利点とクラッシュを防ぐには、デフォルトでは回数に制限があるので、この制限を変更しても問題ありませんか?上記のコードを思い切って 20000 に変更しました。この制限がなければ問題はありませんでしたが、結果は衝撃的でした。私は友人の littlehann に相談しました。この質問に対する答えはありませんでした。しかし、実際のアプリケーションでの再帰演算の効率に関して言えば、教科書以外で再帰を使用しているのを見るのは確かにまれです

本来の目的は評価するだけなので、深く勉強する必要はありません、使用しましょうあまり感銘を受けませんが、コードは次のとおりです:

cimal = 7
original = 28679718602997181072337614380936720482949
array = ""
result= ""
while original !=0:
    remainder = original % cimal
    array += str(remainder)
    original /= cimal
length = len(array)
for i in xrange(0,length):
    result += array[length-1-i]
print result

ほんの数行のコードで、すぐに完了しました。前回のインタビューのことを思い出して、tx のインタビュアーがアルゴリズムについて質問したのですが、そのとき彼は、再帰を使用して演算を実装することについて言及していました。それで、反復も使用できるのではないかと考えました。

かなり前のことなので、当時の質問ははっきりとは思い出せませんが、今日の教訓は次のとおりです。ほとんどの場合 (コードの作成量が少なく、感覚に基づいて推定)、再帰の効率は比較的低いです。確かに、授業でも言われました。反復を使用する方が、再帰よりも明らかに効率が高くなります (反復の具体的な概念ははっきりとは覚えていません) 少なくとも、私は

loop

を使用することで、何十万回の操作を行っても問題はないと確信しています。ただし、再帰制限を変更しても、やはりストライクに遭遇しました

最後に、Python Long VS C Long Long への別のリンクを掲載しますので、興味のある方はチェックしてみてください。

以上がPythonの反復法と再帰法を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。