再帰的プログラムの最適化

関数を書く方法countTo(n)は1からnまでカウントし、明示的なループ（再帰のみ）を使わずに各数値を出力しますか？再帰的プログラムの最適化

ソリューションは、任意に大きなn与え、でも末尾呼び出しの最適化のない空間と時間、における漸近的に最適でなければなりません。

注：最適な時間複雑度は、Oである（1）最適な空間の複雑さがOである（Nログ） - でも繰り返した場合に、（任意の大きさの）番号を印刷する必要があるため。

質問はlesswrong.comから来ており、関連する詳細はそこの議論から取られています（そうしないと、元の声明が誤解を招く仮定をしてしまうため質問に答えることができなくなります）。

出典

2012-02-12 Uros K

"1からnまでカウントする"プログラムを書くことができますか？ :) –

あなたは本当ですか？ –

私は真剣です@yi_Hはどういう意味ですか？ –

書き換え後のバージョンを再帰的にしたい場合は、方法はありません。どの関数呼び出しもスタック領域を消費します。

テールポジションにあるコールがスタックスペースを消費しない言語があります。そのような言語では、あなたの関数をtail-recursiveに書き換えることができるので、O（1）空間で実行されます。しかし、Pythonはそれらの言語の一つではありません。

出典

2012-02-12 19:36:19 sepp2k

なぜCPSベースのPython実装を使用できないのですか？ – apc

@apc thoeryでは、あなたはできます。しかし、実際には、CPSベースのPythonのすべての実装はあいまいです。あなたのPythonコードを遠隔移植できるようにするには、テール再帰の最適化に頼る必要はありません。 – delnan

@delnan、私は間違っている可能性がありますが、私はPyPyがRPythonでサポートしていると信じています。移植性の問題は顕著なようですが、特定の移植性の問題が発生することが知られていますか？ – apc

再帰の代わりに反復を使用します。

出典

2012-02-12 19:35:31 dan04

プログラムは再帰的に留まる必要があります。私はその質問にそれを加えました。 –

Pythonはあなたがこれを行うことが末尾再帰サポートされている場合：

def foo(n): 
    print n 
    if n > 1: 
     foo(n-1)

を現代の任意のgccのバージョンに対応するCプログラムでは、O（1）で実行されます。私は末尾の再帰をサポートするPythonインタプリタは認識していませんが、それを禁止する言語自体の制限はありません。

出典

2012-02-12 19:52:23 Voo

これは数字を間違った順序で印刷します。テール再帰バージョンを作成するには、2つの引数が必要です。 – sepp2k

@ sepp2k私は何とかnから1に数えなければならないという考えを得ました。理由は分かりません。しかし、他の解決方法もかなり明白でなければならず、私が思うように読者に練習として残されています;） – Voo

def foo(n): 
    if n > 1: 
     foo(n-1) 
    print n

（アルゴリズムではなく、言語固有のコードとしてそれを取る。）

我々はすべての数字の印刷がかかることを取れば、ここでの時間の複雑さは、O（N *）N（ログ）になります同時。

出典

2012-02-12 21:30:43 Gangnus

再帰的プログラムの最適化

答えて

関連する問題