Was ist die maximale Rekursionstiefe und wie kann sie erhöht werden?

Question

Ich habe diese Endrekursive Funktion hier:

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

Es funktioniert bis n=997, dann bricht es einfach ab und gibt einen RecursionError: maximum recursion depth exceeded in comparison aus. Ist das einfach ein Stacküberlauf? Gibt es einen Weg, das zu umgehen?

Answer 1

Verwenden Sie eine Sprache, die Tail-Call-Optimierung garantiert. Oder verwenden Sie Iteration. Alternativ können Sie sich mit Dekoratoren versuchen.

Answer 2

Ich weiß, dass dies eine alte Frage ist, aber für diejenigen, die dies lesen, würde ich davon abraten, Rekursion für Probleme wie dieses zu verwenden - Listen sind viel schneller und vermeiden Rekursion komplett. Ich würde das so implementieren:

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'Die %.0fte Fibonacci-Zahl ist: %.0f' % (n,f[-1])

(Verwenden Sie n+1 in xrange, wenn Sie Ihre Fibonacci-Folge ab 0 anstatt ab 1 zählen.)

Answer 3

Ich hatte ein ähnliches Problem mit dem Fehler "Maximale Rekursionstiefe überschritten". Ich entdeckte, dass der Fehler durch eine fehlerhafte Datei im Verzeichnis ausgelöst wurde, über das ich mit os.walk iteriert habe. Wenn du Schwierigkeiten hast, dieses Problem zu lösen und mit Dateipfaden arbeitest, achte darauf, es einzugrenzen, da es sich um eine fehlerhafte Datei handeln könnte.

Answer 4

Natürlich können Fibonacci-Zahlen in O(n) berechnet werden, indem die Binet-Formel angewendet wird:

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

Wie die Kommentarschreiber bemerken, ist es nicht O(1), sondern O(n) aufgrund von 2**n. Ein Unterschied besteht auch darin, dass man nur einen Wert erhält, während man mit Rekursion alle Werte von Fibonacci(n) bis zu diesem Wert erhält.

Answer 5

Wenn Sie nur einige Fibonacci-Zahlen erhalten möchten, können Sie die Matrixmethode verwenden.

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

Es ist schnell, da numpy einen schnellen Exponentiierungsalgorithmus verwendet. Sie erhalten die Antwort in O(log n). Und es ist besser als die Formel von Binet, weil sie nur Ganzzahlen verwendet. Wenn Sie jedoch alle Fibonacci-Zahlen bis n erhalten möchten, ist es besser, dies durch Memorierung zu tun.