Pythonの反復と再帰

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

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

このバージョンのコードは、元々は長い文字列を追加していませんでした。 10桁以上の整数が直接使えるので、longと関係があるのか​​と思いますが、実際には、Pythonがサポートする整数の長さは非常に長いです。前に書いたコード oct()とhex()を使って解いてみましょう

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

実際、前回の再帰エラーの本当の理由が記載されていなかったことをここで初めて知りました

その理由は。再帰エラーの原因は、Python のデフォルトの再帰制限が約 1000 回のみであるためですが、ここでは 10000 以上を実行する必要があり、更新に時間がかかりました: RuntimeError: 最大再帰深度を超えました

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

一般に、Python 言語には利点とクラッシュを防ぐために追加されています。デフォルトでは回数に制限があるので、この制限を変更しても問題ありませんか?

import sys

# 最大深さを 20000 に設定します

sys.setrecursionlimit(20000)

上記のコードを挿入します。思い切って20000に変更しました。今はこの制限がなければ問題ないはずですが、結果は何も出力されず、混乱していたので、友人のlittlehannに相談しました。この問題をさらに深く掘り下げてみましょう。しかし、実際のアプリケーションでの再帰演算の効率に関して言えば、教科書以外で再帰を使用しているのを見るのは確かにまれです

本来の目的は評価するだけなので、深く勉強する必要はありません、使用しましょうあまり感心しませんが、for ステートメントで処理できます。コードは次のとおりです。

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

かなり前のことなので、当時の質問ははっきりとは思い出せませんが、今日の教訓は次のとおりです。ほとんどの場合 (記述されたコードが少なく、感覚に基づいて推定)、再帰の効率は比較的低いです。確かに、授業でも言われました。反復を使用した方が、再帰よりも効率が明らかに高いです (反復の具体的な概念ははっきりとは覚えていません) 少なくとも、何十万回も計算する場合は問題ないと確信しています。しかし、再帰制限を変更しても、やはりストライクに遭遇しました

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

。