Heim Backend-Entwicklung Python-Tutorial 讲解Python中的递归函数

讲解Python中的递归函数

Jun 06, 2016 am 11:26 AM
python

在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。

举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出:

fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n

Nach dem Login kopieren

所以,fact(n)可以表示为n x fact(n-1),只有n=1时需要特殊处理。

于是,fact(n)用递归的方式写出来就是:

def fact(n):
  if n==1:
    return 1
  return n * fact(n - 1)

Nach dem Login kopieren

上面就是一个递归函数。可以试试:

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

Nach dem Login kopieren

如果我们计算fact(5),可以根据函数定义看到计算过程如下:

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

Nach dem Login kopieren

递归函数的优点是定义简单,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。

使用递归函数需要注意防止栈溢出。在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。可以试试fact(1000):

>>> fact(1000)
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "<stdin>", line 4, in fact
 ...
 File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded

Nach dem Login kopieren

解决递归调用栈溢出的方法是通过尾递归优化,事实上尾递归和循环的效果是一样的,所以,把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。

上面的fact(n)函数由于return n * fact(n - 1)引入了乘法表达式,所以就不是尾递归了。要改成尾递归方式,需要多一点代码,主要是要把每一步的乘积传入到递归函数中:

def fact(n):
  return fact_iter(1, 1, n)

def fact_iter(product, count, max):
  if count > max:
    return product
  return fact_iter(product * count, count + 1, max)

Nach dem Login kopieren

可以看到,return fact_iter(product * count, count + 1, max)仅返回递归函数本身,product * count和count + 1在函数调用前就会被计算,不影响函数调用。

fact(5)对应的fact_iter(1, 1, 5)的调用如下:

===> fact_iter(1, 1, 5)
===> fact_iter(1, 2, 5)
===> fact_iter(2, 3, 5)
===> fact_iter(6, 4, 5)
===> fact_iter(24, 5, 5)
===> fact_iter(120, 6, 5)
===> 120

Nach dem Login kopieren

尾递归调用时,如果做了优化,栈不会增长,因此,无论多少次调用也不会导致栈溢出。

遗憾的是,大多数编程语言没有针对尾递归做优化,Python解释器也没有做优化,所以,即使把上面的fact(n)函数改成尾递归方式,也会导致栈溢出。

有一个针对尾递归优化的decorator,可以参考源码:

http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/

我们后面会讲到如何编写decorator。现在,只需要使用这个@tail_call_optimized,就可以顺利计算出fact(1000):

>>> fact(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Nach dem Login kopieren

小结

使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。

针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的,没有循环语句的编程语言只能通过尾递归实现循环。

Python标准的解释器没有针对尾递归做优化,任何递归函数都存在栈溢出的问题。

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Google AI kündigt Gemini 1.5 Pro und Gemma 2 für Entwickler an Google AI kündigt Gemini 1.5 Pro und Gemma 2 für Entwickler an Jul 01, 2024 am 07:22 AM

Google AI hat damit begonnen, Entwicklern Zugriff auf erweiterte Kontextfenster und kostensparende Funktionen zu bieten, beginnend mit dem großen Sprachmodell Gemini 1.5 Pro (LLM). Bisher über eine Warteliste verfügbar, das vollständige 2-Millionen-Token-Kontextfenster

So laden Sie Deepseek Xiaomi herunter So laden Sie Deepseek Xiaomi herunter Feb 19, 2025 pm 05:27 PM

Wie lade ich Deepseek Xiaomi herunter? Suchen Sie nach "Deepseek" im Xiaomi App Store. Identifizieren Sie Ihre Anforderungen (Suchdateien, Datenanalyse) und finden Sie die entsprechenden Tools (z. B. Dateimanager, Datenanalyse -Software), die Deepseek -Funktionen enthalten.

Wie fragst du ihn Deepseek? Wie fragst du ihn Deepseek? Feb 19, 2025 pm 04:42 PM

Der Schlüssel zur effektiven Verwendung von Deepseek liegt darin, die Fragen klar zu stellen: Die Fragen direkt und spezifisch ausdrücken. Geben Sie spezifische Details und Hintergrundinformationen an. Für komplexe Anfragen sind mehrere Blickwinkel und Widerrufs der Meinungen enthalten. Konzentrieren Sie sich auf bestimmte Aspekte, wie z. B. Leistungs Engpässe im Code. Denken Sie kritisch über die Antworten nach, die Sie erhalten, und fällen Sie anhand Ihres Fachwissens Urteile.

So suchen Sie Deepseek So suchen Sie Deepseek Feb 19, 2025 pm 05:18 PM

Verwenden Sie einfach die Suchfunktion, die mit Deepseek geliefert wird. Für Suchvorgänge, die unpopulär, neueste Informationen oder Probleme sind, die berücksichtigt werden müssen, müssen jedoch Schlüsselwörter angepasst oder spezifischere Beschreibungen verwendet werden, sie mit anderen Echtzeitinformationsquellen kombinieren und verstehen, dass Deepseek nur ein Tool ist, das erfordert aktive, klare und raffinierte Suchstrategien.

So programmieren Sie Deepseek So programmieren Sie Deepseek Feb 19, 2025 pm 05:36 PM

Deepseek ist keine Programmiersprache, sondern ein tiefes Suchkonzept. Die Implementierung von Deepseek erfordert eine Auswahl auf der Grundlage vorhandener Sprachen. Für verschiedene Anwendungsszenarien ist es erforderlich, die entsprechende Sprache und Algorithmen auszuwählen und maschinelles Lernen zu kombinieren. Codequalität, Wartbarkeit und Tests sind von entscheidender Bedeutung. Nur durch die Auswahl der richtigen Programmiersprache können Algorithmen und Tools entsprechend Ihren Anforderungen und das Schreiben von Code von hochwertigem Code erfolgreich implementiert werden.

So verwenden Sie Deepseek, um Konten zu begleichen So verwenden Sie Deepseek, um Konten zu begleichen Feb 19, 2025 pm 04:36 PM

Frage: Ist Deepseek für die Buchhaltung verfügbar? Antwort: Nein, es handelt sich um ein Data Mining- und Analyse -Tool, mit dem Finanzdaten analysiert werden können, aber es gibt nicht die Funktionen zur Erzeugung von Buchhaltungsdaten für Buchhaltungsdaten für Buchhaltungssoftware. Um Deepseek zur Analyse von Finanzdaten zu analysieren, muss das Schreiben von Code geschrieben werden, um Daten mit Kenntnissen von Datenstrukturen, Algorithmen und Deepseek -APIs zu verarbeiten, um potenzielle Probleme zu berücksichtigen (z. B. Programmierkenntnisse, Lernkurven, Datenqualität)

Der Schlüssel zum Programmieren: Die Leistungsfähigkeit von Python für Anfänger freischalten Der Schlüssel zum Programmieren: Die Leistungsfähigkeit von Python für Anfänger freischalten Oct 11, 2024 pm 12:17 PM

Python ist aufgrund seiner einfachen Erlernbarkeit und leistungsstarken Funktionen eine ideale Einführungssprache in die Programmierung für Anfänger. Zu seinen Grundlagen gehören: Variablen: werden zum Speichern von Daten (Zahlen, Zeichenfolgen, Listen usw.) verwendet. Datentyp: Definiert den Datentyp in der Variablen (Ganzzahl, Gleitkomma usw.). Operatoren: werden für mathematische Operationen und Vergleiche verwendet. Kontrollfluss: Kontrollieren Sie den Fluss der Codeausführung (bedingte Anweisungen, Schleifen).

Problemlösung mit Python: Erschließen Sie leistungsstarke Lösungen als Programmieranfänger Problemlösung mit Python: Erschließen Sie leistungsstarke Lösungen als Programmieranfänger Oct 11, 2024 pm 08:58 PM

Python unterstützt Anfänger bei der Problemlösung. Seine benutzerfreundliche Syntax, umfangreiche Bibliothek und Funktionen wie Variablen, bedingte Anweisungen und Schleifen ermöglichen eine effiziente Codeentwicklung. Von der Datenverwaltung über die Steuerung des Programmablaufs bis hin zur Ausführung wiederkehrender Aufgaben bietet Python

See all articles