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

import sys
sys.setrecursionlimit(1500)

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

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

Answer 2

Viele empfehlen, dass die Erhöhung des Rekursionslimits eine gute Lösung ist, jedoch ist es das nicht, da es immer eine Grenze geben wird. Verwenden Sie stattdessen eine iterative Lösung.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

Answer 3

Ich bin mir nicht sicher, ob ich jemanden wiederhole, aber vor einiger Zeit hat jemand Gutes die Y-Operator für rekursiv aufgerufene Funktionen geschrieben, wie:

def tail_recursive(func):
  y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func)
  def wrap_func_tail(*args):
    out = y_operator(*args)
    while callable(out): out = out()
    return out
  return wrap_func_tail

und dann braucht die rekursive Funktion die Form:

def my_recursive_func(g):
  def wrapped(some_arg, acc):
    if : return acc
    return g(some_arg, acc)
  return wrapped

# und schließlich rufen Sie es im Code auf

(tail_recursive(my_recursive_func))(some_arg, acc)

für Fibonaccizahlen sieht Ihre Funktion so aus:

def fib(g):
  def wrapped(n_1, n_2, n):
    if n == 0: return n_1
    return g(n_2, n_1 + n_2, n-1)
  return wrapped

print((tail_recursive(fib))(0, 1, 1000000))

Ausgabe:

..684684301719893411568996526838242546875

(eigentlich eine Menge Ziffern)

Answer 4

Wir könnten auch eine Variation des dynamischen Programmieransatzes von unten nach oben verwenden

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))