Python 哪些可以代替递归的算法？-Tutorial Python-php.cn

Jadual Kandungan

回复内容：

Rumah

pembangunan bahagian belakang

Tutorial 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>
Salin selepas log masuk

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

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

这样唯一的好处或许就是解除了最大递归深度的限制吧。。。

给邵大神补一个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>
Salin selepas log masuk

用循环实现？

可以自己建个栈来保存状态。你只需要搞明白在递归的时候程序往栈上面放了些什么，然后用自己的栈模拟即可。
技巧上倒是可以参照从fortran时代积累的递归转迭代的技术。

不是完全没有解决方案：
Does Python optimize tail recursion?

时代积累的递归转迭代的技术。

然后用自己的栈模拟即可。

，话j

Kenyataan Laman Web ini

Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Tunjukkan Lagi

Artikel Panas

Assassin's Creed Shadows: Penyelesaian Riddle Seashell

3 minggu yang lalu By DDD

Apa yang Baru di Windows 11 KB5054979 & Cara Memperbaiki Masalah Kemas Kini

2 minggu yang lalu By DDD

Di mana untuk mencari kad kunci kawalan kren di atomfall

3 minggu yang lalu By DDD

Assassin's Creed Shadows - Cara Mencari Orang Panda

1 bulan yang lalu By DDD

<🎜>: Rails Dead - Cara Melengkapkan Setiap Cabaran

3 minggu yang lalu By DDD

Tunjukkan Lagi

Alat panas

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Tunjukkan Lagi

Topik panas

Di manakah pintu masuk log masuk untuk e-mel gmail?

7626

Tutorial CakePHP

1389

Apakah format nama akaun stim

kunci pengaktifan win11 kekal

Sambungan NYT menunjukkan dan jawapan

140

Tunjukkan Lagi

Related knowledge

Bagaimana untuk menyelesaikan masalah kebenaran yang dihadapi semasa melihat versi Python di Terminal Linux? Apr 01, 2025 pm 05:09 PM

Penyelesaian kepada Isu Kebenaran Semasa Melihat Versi Python di Terminal Linux Apabila anda cuba melihat versi Python di Terminal Linux, masukkan Python ...

Bagaimana Mengajar Asas Pengaturcaraan Pemula Komputer Dalam Kaedah Projek dan Masalah Dikemukakan Dalam masa 10 Jam? Apr 02, 2025 am 07:18 AM

Bagaimana Mengajar Asas Pengaturcaraan Pemula Komputer Dalam masa 10 jam? Sekiranya anda hanya mempunyai 10 jam untuk mengajar pemula komputer beberapa pengetahuan pengaturcaraan, apa yang akan anda pilih untuk mengajar ...

Bagaimana cara menyalin seluruh lajur satu data ke dalam data data lain dengan struktur yang berbeza di Python? Apr 01, 2025 pm 11:15 PM

Apabila menggunakan Perpustakaan Pandas Python, bagaimana untuk menyalin seluruh lajur antara dua data data dengan struktur yang berbeza adalah masalah biasa. Katakan kita mempunyai dua DAT ...

Bagaimana untuk mengelakkan dikesan oleh penyemak imbas apabila menggunakan fiddler di mana-mana untuk membaca lelaki-dalam-tengah? Apr 02, 2025 am 07:15 AM

Cara mengelakkan dikesan semasa menggunakan fiddlerevery di mana untuk bacaan lelaki-dalam-pertengahan apabila anda menggunakan fiddlerevery di mana ...

Bagaimanakah uvicorn terus mendengar permintaan http tanpa serving_forever ()? Apr 01, 2025 pm 10:51 PM

Bagaimanakah Uvicorn terus mendengar permintaan HTTP? Uvicorn adalah pelayan web ringan berdasarkan ASGI. Salah satu fungsi terasnya ialah mendengar permintaan HTTP dan teruskan ...

Bagaimana secara dinamik membuat objek melalui rentetan dan panggil kaedahnya dalam Python? Apr 01, 2025 pm 11:18 PM

Di Python, bagaimana untuk membuat objek secara dinamik melalui rentetan dan panggil kaedahnya? Ini adalah keperluan pengaturcaraan yang biasa, terutamanya jika perlu dikonfigurasikan atau dijalankan ...

Bagaimana menyelesaikan masalah kebenaran apabila menggunakan perintah Python -version di Terminal Linux? Apr 02, 2025 am 06:36 AM

Menggunakan Python di Terminal Linux ...

Bagaimana untuk mengendalikan parameter pertanyaan senarai yang dipisahkan koma di FastAPI? Apr 02, 2025 am 06:51 AM

Fastapi ...

See all articles