Table des matières
Python 哪些可以代替递归的算法？
回复内容：
所有的递归调用，都可以做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>
Copier après la connexion
如果不想递归，硬是要循环，那么可以自己手动来维护这个调用栈
这样唯一的好处或许就是解除了最大递归深度的限制吧。。。 给邵大神补一个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>
Copier après la connexion
技巧上倒是可以参照从fortran时代积累的递归转迭代的技术。 不是完全没有解决方案：
Does Python optimize tail recursion? 时代积累的递归转迭代的技术。 然后用自己的栈模拟即可。 ，话j
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Outils d'IA chauds
Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes
AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.
Undress AI Tool
Images de déshabillage gratuites
Clothoff.io
Dissolvant de vêtements AI
Video Face Swap
Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !
Article chaud
Assassin's Creed Shadows: Solution d'énigmes de coquille
3 Il y a quelques semaines
By DDD
Quoi de neuf dans Windows 11 KB5054979 et comment résoudre les problèmes de mise à jour
2 Il y a quelques semaines
By DDD
Où trouver la courte de la grue à atomide atomique
3 Il y a quelques semaines
By DDD
Économie dans R.E.P.O. Expliqué (et enregistrer des fichiers)
1 Il y a quelques mois
By 尊渡假赌尊渡假赌尊渡假赌
Assassin's Creed Shadows - Comment trouver le forgeron et déverrouiller les armes et la personnalisation des armes
4 Il y a quelques semaines
By DDD
Outils chauds
Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit
SublimeText3 version chinoise
Version chinoise, très simple à utiliser
Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP
Dreamweaver CS6
Outils de développement Web visuel
SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)
Comment résoudre le problème des autorisations rencontré lors de la visualisation de la version Python dans le terminal Linux?
Apr 01, 2025 pm 05:09 PM
Solution aux problèmes d'autorisation Lors de la visualisation de la version Python dans Linux Terminal Lorsque vous essayez d'afficher la version Python dans Linux Terminal, entrez Python ...
Comment copier efficacement la colonne entière d'une dataframe dans une autre dataframe avec différentes structures dans Python?
Apr 01, 2025 pm 11:15 PM
Lorsque vous utilisez la bibliothèque Pandas de Python, comment copier des colonnes entières entre deux frames de données avec différentes structures est un problème courant. Supposons que nous ayons deux dats ...
Comment enseigner les bases de la programmation novice en informatique dans le projet et les méthodes axées sur les problèmes dans les 10 heures?
Apr 02, 2025 am 07:18 AM
Comment enseigner les bases de la programmation novice en informatique dans les 10 heures? Si vous n'avez que 10 heures pour enseigner à l'informatique novice des connaissances en programmation, que choisissez-vous d'enseigner ...
Comment éviter d'être détecté par le navigateur lors de l'utilisation de Fiddler partout pour la lecture de l'homme au milieu?
Apr 02, 2025 am 07:15 AM
Comment éviter d'être détecté lors de l'utilisation de FiddlereVerywhere pour les lectures d'homme dans le milieu lorsque vous utilisez FiddlereVerywhere ...
Que sont les expressions régulières?
Mar 20, 2025 pm 06:25 PM
Les expressions régulières sont des outils puissants pour la correspondance des motifs et la manipulation du texte dans la programmation, améliorant l'efficacité du traitement de texte sur diverses applications.
Comment Uvicorn écoute-t-il en permanence les demandes HTTP sans servir_forever ()?
Apr 01, 2025 pm 10:51 PM
Comment Uvicorn écoute-t-il en permanence les demandes HTTP? Uvicorn est un serveur Web léger basé sur ASGI. L'une de ses fonctions principales est d'écouter les demandes HTTP et de procéder ...
Quelles sont les bibliothèques Python populaires et leurs utilisations?
Mar 21, 2025 pm 06:46 PM
L'article traite des bibliothèques Python populaires comme Numpy, Pandas, Matplotlib, Scikit-Learn, Tensorflow, Django, Flask et Demandes, détaillant leurs utilisations dans le calcul scientifique, l'analyse des données, la visualisation, l'apprentissage automatique, le développement Web et H et H
Comment créer dynamiquement un objet via une chaîne et appeler ses méthodes dans Python?
Apr 01, 2025 pm 11:18 PM
Dans Python, comment créer dynamiquement un objet via une chaîne et appeler ses méthodes? Il s'agit d'une exigence de programmation courante, surtout si elle doit être configurée ou exécutée ...
