社区
学习
工具库
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脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

显示更多

热门文章

R.E.P.O.能量晶体解释及其做什么（黄色晶体）
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
2 周前 By DDD
R.E.P.O.如果您听不到任何人，如何修复音频
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25：如何解锁Myrise中的所有内容
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
显示更多

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里
7513
15
CakePHP 教程
1378
52
steam的账户名称是什么格式
78
11
win11激活密钥永久
53
19
NYT连接提示和答案
19
64
显示更多
Related knowledge
如何解决Linux终端中查看Python版本时遇到的权限问题？ 如何解决Linux终端中查看Python版本时遇到的权限问题？ Apr 01, 2025 pm 05:09 PM

Linux终端中查看Python版本时遇到权限问题的解决方法当你在Linux终端中尝试查看Python的版本时，输入python...

在Python中如何高效地将一个DataFrame的整列复制到另一个结构不同的DataFrame中？ 在Python中如何高效地将一个DataFrame的整列复制到另一个结构不同的DataFrame中？ Apr 01, 2025 pm 11:15 PM

在使用Python的pandas库时，如何在两个结构不同的DataFrame之间进行整列复制是一个常见的问题。假设我们有两个Dat...

如何在10小时内通过项目和问题驱动的方式教计算机小白编程基础？ 如何在10小时内通过项目和问题驱动的方式教计算机小白编程基础？ Apr 02, 2025 am 07:18 AM

如何在10小时内教计算机小白编程基础？如果你只有10个小时来教计算机小白一些编程知识，你会选择教些什么�...

如何在使用 Fiddler Everywhere 进行中间人读取时避免被浏览器检测到？ 如何在使用 Fiddler Everywhere 进行中间人读取时避免被浏览器检测到？ Apr 02, 2025 am 07:15 AM

使用FiddlerEverywhere进行中间人读取时如何避免被检测到当你使用FiddlerEverywhere...

什么是正则表达式？ 什么是正则表达式？ Mar 20, 2025 pm 06:25 PM

正则表达式是在编程中进行模式匹配和文本操作的强大工具，从而提高了各种应用程序的文本处理效率。

Uvicorn是如何在没有serve_forever()的情况下持续监听HTTP请求的？ Uvicorn是如何在没有serve_forever()的情况下持续监听HTTP请求的？ Apr 01, 2025 pm 10:51 PM

Uvicorn是如何持续监听HTTP请求的？Uvicorn是一个基于ASGI的轻量级Web服务器，其核心功能之一便是监听HTTP请求并进�...

Python中如何通过字符串动态创建对象并调用其方法？ Python中如何通过字符串动态创建对象并调用其方法？ Apr 01, 2025 pm 11:18 PM

在Python中，如何通过字符串动态创建对象并调用其方法？这是一个常见的编程需求，尤其在需要根据配置或运行...

哪些流行的Python库及其用途？ 哪些流行的Python库及其用途？ Mar 21, 2025 pm 06:46 PM

本文讨论了诸如Numpy，Pandas，Matplotlib，Scikit-Learn，Tensorflow，Tensorflow，Django，Blask和请求等流行的Python库，并详细介绍了它们在科学计算，数据分析，可视化，机器学习，网络开发和H中的用途

See all articles