Python 哪些可以代替递归的算法？-Python チュートリアル-php.cn

ホームページ

バックエンド開発

Python チュートリアル

Python 哪些可以代替递归的算法？

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 06, 2016 pm 04:22 PM

回复内容：

所有的递归调用，都可以做CPS变换改写成尾递归形式，然后尾递归可以改写成循环：

<span class="k">def</span> <span class="nf">fact</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
        <span class="k">return</span> <span class="mi">1</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">fact</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>


<span class="nb">id</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">x</span>


<span class="k">def</span> <span class="nf">factCPS</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">k</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">k</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">f</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">k</span><span class="p">(</span><span class="n">n</span> <span class="o">*</span> <span class="n">x</span><span class="p">))</span>

    <span class="k">return</span> <span class="n">f</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="nb">id</span><span class="p">)</span>


<span class="k">def</span> <span class="nf">factNoRec</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">factory</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">k</span><span class="p">):</span>
        <span class="k">return</span> <span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">k</span><span class="p">(</span><span class="n">n</span> <span class="o">*</span> <span class="n">x</span><span class="p">)</span>

    <span class="n">k</span> <span class="o">=</span> <span class="nb">id</span>
    <span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
        <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">k</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">k</span> <span class="o">=</span> <span class="n">factory</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">k</span><span class="p">)</span>
            <span class="n">n</span> <span class="o">-=</span> <span class="mi">1</span>


<span class="k">def</span> <span class="nf">factHolyCrap</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="n">k</span> <span class="o">=</span> <span class="p">()</span>
    <span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
        <span class="k">if</span> <span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="n">x</span> <span class="o">=</span> <span class="mi">1</span>
            <span class="k">while</span> <span class="n">k</span><span class="p">:</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">k</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">*</span> <span class="n">x</span>
                <span class="n">k</span> <span class="o">=</span> <span class="n">k</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
            <span class="k">return</span> <span class="nb">id</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">k</span> <span class="o">=</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">k</span><span class="p">)</span>
            <span class="n">n</span> <span class="o">-=</span> <span class="mi">1</span>

<span class="k">if</span> <span class="n">__name__</span> <span class="o">==</span> <span class="s">'__main__'</span><span class="p">:</span>
    <span class="k">print</span><span class="p">([</span><span class="n">f</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span> <span class="k">for</span> <span class="n">f</span> <span class="ow">in</span> <span class="p">[</span><span class="n">fact</span><span class="p">,</span> <span class="n">factCPS</span><span class="p">,</span> <span class="n">factNoRec</span><span class="p">,</span> <span class="n">factHolyCrap</span><span class="p">]])</span>

递归过程中需要维护一个调用栈

如果不想递归，硬是要循环，那么可以自己手动来维护这个调用栈

这样唯一的好处或许就是解除了最大递归深度的限制吧。。。给邵大神补一个java sample

<span class="kd">public</span> <span class="kd">class</span> <span class="nc">RecursionEliminationSample</span> <span class="o">{</span>
    <span class="kt">int</span> <span class="nf">factorRec</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span>
            <span class="k">return</span> <span class="mi">1</span><span class="o">;</span>
        <span class="k">else</span>
            <span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">factorRec</span><span class="o">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="o">);</span>
    <span class="o">}</span>

    <span class="kt">int</span> <span class="nf">factor</span><span class="o">(</span><span class="kt">int</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Function</span><span class="o"><</span><span class="n">Integer</span><span class="o">,</span> <span class="n">Integer</span><span class="o">></span> <span class="n">k</span> <span class="o">=</span> <span class="o">(</span><span class="n">x</span><span class="o">)</span> <span class="o">-></span> <span class="n">x</span><span class="o">;</span>
        <span class="k">while</span><span class="o">(</span><span class="kc">true</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="o">)</span>
                <span class="k">return</span> <span class="n">k</span><span class="o">.</span><span class="na">apply</span><span class="o">(</span><span class="mi">1</span><span class="o">);</span>
            <span class="k">else</span> <span class="o">{</span>
                <span class="kd">final</span> <span class="n">Function</span><span class="o"><</span><span class="n">Integer</span><span class="o">,</span> <span class="n">Integer</span><span class="o">></span> <span class="n">k0</span> <span class="o">=</span> <span class="n">k</span><span class="o">;</span>
                <span class="kd">final</span> <span class="kt">int</span> <span class="n">n0</span> <span class="o">=</span> <span class="n">n</span><span class="o">;</span>

                <span class="n">k</span> <span class="o">=</span> <span class="o">(</span><span class="n">x</span><span class="o">)</span> <span class="o">-></span> <span class="n">k0</span><span class="o">.</span><span class="na">apply</span><span class="o">(</span><span class="n">n0</span> <span class="o">*</span> <span class="n">x</span><span class="o">);</span>
                <span class="n">n</span> <span class="o">-=</span> <span class="mi">1</span><span class="o">;</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>

用循环实现？可以自己建个栈来保存状态。你只需要搞明白在递归的时候程序往栈上面放了些什么，然后用自己的栈模拟即可。
技巧上倒是可以参照从fortran时代积累的递归转迭代的技术。不是完全没有解决方案：
Does Python optimize tail recursion? 时代积累的递归转迭代的技术。然后用自己的栈模拟即可。，话j

声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

Python vs. C：比較されたアプリケーションとユースケースApr 12, 2025 am 12:01 AM

Pythonは、データサイエンス、Web開発、自動化タスクに適していますが、Cはシステムプログラミング、ゲーム開発、組み込みシステムに適しています。 Pythonは、そのシンプルさと強力なエコシステムで知られていますが、Cは高性能および基礎となる制御機能で知られています。

2時間のPython計画：現実的なアプローチApr 11, 2025 am 12:04 AM

2時間以内にPythonの基本的なプログラミングの概念とスキルを学ぶことができます。 1.変数とデータ型、2。マスターコントロールフロー（条件付きステートメントとループ）、3。機能の定義と使用を理解する4。

Python：主要なアプリケーションの調査Apr 10, 2025 am 09:41 AM

Pythonは、Web開発、データサイエンス、機械学習、自動化、スクリプトの分野で広く使用されています。 1）Web開発では、DjangoおよびFlask Frameworksが開発プロセスを簡素化します。 2）データサイエンスと機械学習の分野では、Numpy、Pandas、Scikit-Learn、Tensorflowライブラリが強力なサポートを提供します。 3）自動化とスクリプトの観点から、Pythonは自動テストやシステム管理などのタスクに適しています。

2時間でどのくらいのPythonを学ぶことができますか？Apr 09, 2025 pm 04:33 PM

2時間以内にPythonの基本を学ぶことができます。 1。変数とデータ型を学習します。2。ステートメントやループの場合などのマスター制御構造、3。関数の定義と使用を理解します。これらは、簡単なPythonプログラムの作成を開始するのに役立ちます。

プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は？Apr 02, 2025 am 07:18 AM

10時間以内にコンピューター初心者プログラミングの基本を教える方法は？コンピューター初心者にプログラミングの知識を教えるのに10時間しかない場合、何を教えることを選びますか...

中間の読書にどこでもfiddlerを使用するときにブラウザによって検出されないようにするにはどうすればよいですか？Apr 02, 2025 am 07:15 AM

fiddlereveryversings for the-middleの測定値を使用するときに検出されないようにする方法

Python 3.6にピクルスファイルをロードするときに「__Builtin__」モジュールが見つからない場合はどうすればよいですか？Apr 02, 2025 am 07:12 AM

Python 3.6のピクルスファイルのロードレポートエラー：modulenotFounderror：nomodulenamed ...

風光明媚なスポットコメント分析におけるJieba Wordセグメンテーションの精度を改善する方法は？Apr 02, 2025 am 07:09 AM

風光明媚なスポットコメント分析におけるJieba Wordセグメンテーションの問題を解決する方法は？風光明媚なスポットコメントと分析を行っているとき、私たちはしばしばJieba Wordセグメンテーションツールを使用してテキストを処理します...

See all articles

ホットAIツール

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

脱衣画像を無料で

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

SublimeText3 Mac版

神レベルのコード編集ソフト（SublimeText3）

DVWA

Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、

SublimeText3 中国語版

中国語版、とても使いやすい

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。