社群
學習
工具庫
AI工具
休閒
搜尋
繁体中文
目錄
回复内容：
首頁 後端開發 Python教學 Python 哪些可以代替递归的算法？

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
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

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序，用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！

顯示更多

熱門文章

<🎜>：種植花園 - 完整的突變指南
3 週前 By DDD
<🎜>：泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
如何修復KB5055612無法在Windows 10中安裝？
3 週前 By DDD
北端：融合系統，解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
藍王子：如何到達地下室
1 個月前 By DDD
顯示更多

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版，非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

顯示更多

熱門話題

Java教學
1664
14
CakePHP 教程
1423
52
Laravel 教程
1318
25
PHP教程
1268
29
C# 教程
1248
24
顯示更多
Related knowledge
Python vs.C：申請和用例 Python vs.C：申請和用例 Apr 12, 2025 am 12:01 AM

Python适合数据科学、Web开发和自动化任务，而C 适用于系统编程、游戏开发和嵌入式系统。Python以简洁和强大的生态系统著称，C 则以高性能和底层控制能力闻名。

Python：遊戲，Guis等 Python：遊戲，Guis等 Apr 13, 2025 am 12:14 AM

Python在遊戲和GUI開發中表現出色。 1)遊戲開發使用Pygame，提供繪圖、音頻等功能，適合創建2D遊戲。 2)GUI開發可選擇Tkinter或PyQt，Tkinter簡單易用，PyQt功能豐富，適合專業開發。

Python與C：學習曲線和易用性 Python與C：學習曲線和易用性 Apr 19, 2025 am 12:20 AM

Python更易學且易用，C 則更強大但複雜。 1.Python語法簡潔，適合初學者，動態類型和自動內存管理使其易用，但可能導致運行時錯誤。 2.C 提供低級控制和高級特性，適合高性能應用，但學習門檻高，需手動管理內存和類型安全。

2小時的Python計劃：一種現實的方法 2小時的Python計劃：一種現實的方法 Apr 11, 2025 am 12:04 AM

2小時內可以學會Python的基本編程概念和技能。 1.學習變量和數據類型，2.掌握控制流（條件語句和循環），3.理解函數的定義和使用，4.通過簡單示例和代碼片段快速上手Python編程。

Python和時間：充分利用您的學習時間 Python和時間：充分利用您的學習時間 Apr 14, 2025 am 12:02 AM

要在有限的時間內最大化學習Python的效率，可以使用Python的datetime、time和schedule模塊。 1.datetime模塊用於記錄和規劃學習時間。 2.time模塊幫助設置學習和休息時間。 3.schedule模塊自動化安排每週學習任務。

Python vs.C：探索性能和效率 Python vs.C：探索性能和效率 Apr 18, 2025 am 12:20 AM

Python在開發效率上優於C ，但C 在執行性能上更高。 1.Python的簡潔語法和豐富庫提高開發效率。 2.C 的編譯型特性和硬件控制提升執行性能。選擇時需根據項目需求權衡開發速度與執行效率。

Python：自動化，腳本和任務管理 Python：自動化，腳本和任務管理 Apr 16, 2025 am 12:14 AM

Python在自動化、腳本編寫和任務管理中表現出色。 1)自動化：通過標準庫如os、shutil實現文件備份。 2)腳本編寫：使用psutil庫監控系統資源。 3)任務管理：利用schedule庫調度任務。 Python的易用性和豐富庫支持使其在這些領域中成為首選工具。

學習Python：2小時的每日學習是否足夠？ 學習Python：2小時的每日學習是否足夠？ Apr 18, 2025 am 12:22 AM

每天學習Python兩個小時是否足夠？這取決於你的目標和學習方法。 1)制定清晰的學習計劃，2)選擇合適的學習資源和方法，3)動手實踐和復習鞏固，可以在這段時間內逐步掌握Python的基本知識和高級功能。

See all articles