Maison développement back-end Tutoriel Python python中尾递归用法实例详解

python中尾递归用法实例详解

Jun 06, 2016 am 11:26 AM
python

本文实例讲述了python中尾递归用法。分享给大家供大家参考。具体分析如下:

如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

原理:

当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。因此,只要有可能我们就需要将递归函数写成尾递归的形式.

代码:

# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException:
 def __init__(self, args, kwargs):
  self.args = args
  self.kwargs = kwargs
def tail_call_optimized(g):
 """
 This function decorates a function with tail call
 optimization. It does this by throwing an exception
 if it is it's own grandparent, and catching such
 exceptions to fake the tail call optimization.
 This function fails if the decorated
 function recurses in a non-tail context.
 """
 def func(*args, **kwargs):
  f = sys._getframe()
  if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
   raise TailRecurseException(args, kwargs)
  else:
   while 1:
    try:
     return g(*args, **kwargs)
    except TailRecurseException, e:
     args = e.args
     kwargs = e.kwargs
 func.__doc__ = g.__doc__
 return func
@tail_call_optimized
def factorial(n, acc=1):
 "calculate a factorial"
 if n == 0:
  return acc
 return factorial(n-1, n*acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
@tail_call_optimized
def fib(i, current = 0, next = 1):
 if i == 0:
  return current
 else:
  return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.
Copier après la connexion

希望本文所述对大家的Python程序设计有所帮助。

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

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

L'interprète Python peut-il être supprimé dans le système Linux? L'interprète Python peut-il être supprimé dans le système Linux? Apr 02, 2025 am 07:00 AM

En ce qui concerne le problème de la suppression de l'interpréteur Python qui est livré avec des systèmes Linux, de nombreuses distributions Linux préinstalleront l'interpréteur Python lors de l'installation, et il n'utilise pas le gestionnaire de packages ...

Comment résoudre le problème de la détection de type pylance des décorateurs personnalisés dans Python? Comment résoudre le problème de la détection de type pylance des décorateurs personnalisés dans Python? Apr 02, 2025 am 06:42 AM

Solution de problème de détection de type pylance Lorsque vous utilisez un décorateur personnalisé dans la programmation Python, le décorateur est un outil puissant qui peut être utilisé pour ajouter des lignes ...

Python 3.6 Chargement du fichier de cornichon MODULENOTFOUNDERROR: Que dois-je faire si je charge le fichier de cornichon '__builtin__'? Python 3.6 Chargement du fichier de cornichon MODULENOTFOUNDERROR: Que dois-je faire si je charge le fichier de cornichon '__builtin__'? Apr 02, 2025 am 06:27 AM

Chargement du fichier de cornichon dans Python 3.6 Erreur d'environnement: modulenotFounonError: NomoduLenamed ...

FastAPI et AIOHTTP partagent-ils la même boucle d'événements mondiaux? FastAPI et AIOHTTP partagent-ils la même boucle d'événements mondiaux? Apr 02, 2025 am 06:12 AM

Problèmes de compatibilité entre les bibliothèques asynchrones Python dans Python, la programmation asynchrone est devenue le processus de concurrence élevée et d'E / S ...

Que dois-je faire si le module '__builtin__' n'est pas trouvé lors du chargement du fichier de cornichon dans Python 3.6? Que dois-je faire si le module '__builtin__' n'est pas trouvé lors du chargement du fichier de cornichon dans Python 3.6? Apr 02, 2025 am 07:12 AM

Chargement des fichiers de cornichons dans Python 3.6 Rapport de l'environnement Erreur: modulenotFoundError: NomoduLenamed ...

Comment s'assurer que le processus de l'enfant se termine également après avoir tué le processus parent via le signal dans Python? Comment s'assurer que le processus de l'enfant se termine également après avoir tué le processus parent via le signal dans Python? Apr 02, 2025 am 06:39 AM

Le problème et la solution du processus enfant continuent d'exécuter lors de l'utilisation de signaux pour tuer le processus parent. Dans la programmation Python, après avoir tué le processus parent à travers des signaux, le processus de l'enfant est toujours ...

See all articles