Python Rekursion Anfrage

Question

Ich möchte bestätigen, wenn ich verstehe, wie diese Funktion in rekursive Form in Python geschrieben wird. Die Funktion ist:

# Recurrence Relation 
# F(n) = 7 * F(n-1) + 2 * F(n-2) 
# F(1) = 1; F(2) = 1 
# print (rr(4)) 

und meine rekursive Code ist:

def rr(n): 
    return (2 * rr(n-1) + 2 * rr(n-2)) 

dies richtig ist? Wie könnte ich auch "rr" (4) "drucken", da ich dachte, es könnte nur ausgewertet werden, wenn Sie das Programm ausführen.

Answer 1

Ihr Code wird einen reinen Stapelüberlauf verursachen, da Sie nicht Ihre Stoppbedingungen definiert haben, also die Startwerte von F (1) und F (2). Fügen Sie in Ihrer Funktion Tests hinzu, abhängig vom Wert n, um diese Fälle zu behandeln.

Answer 2

Sie vermissen die Basisfälle.

# F(1) = 1; F(2) = 1 

Bedenken Sie:

def rr(n): 
    if n == 1: 
     return 1 
    elif n == 2: 
     return 1 
    else: 
     return 7 * rr(n-1) + 2 * rr(n-2) 

Auch Ihre rekursive Fall nicht die Rekursion überein. Es hatte eine 2 wo eine 7 erschien.

>>> def rr(n): 
...  if n == 1: 
...   return 1 
...  elif n == 2: 
...   return 1 
...  else: 
...   return 7 * rr(n-1) + 2 * rr(n-2) 
... 
>>> print rr(4) 
65 

Answer 3

Sie haben die Basisfälle, die die Basis für die Rekursion bilden würden, nicht hinzugefügt.

def rr(n): 
    if n < 1: 
     raise "Invalid input" 
    if n <= 2: 
     return 1 
    return 7 * rr(n-1) + 2 * rr(n-2) 

Dies wird wie folgt durchgeführt:

rr(4) = 7 * rr(4-1) + 2 * rr(4-2) 
     = 7 * rr(3) + 2 * rr(2) 
     = 7 * (7 * rr(3-1) + 2 * rr(3-2)) + 2 * 1 
     = 7 * (7 * r(2) + 2 * r(1)) + 2 
     = 7 * (7 * 1 + 2 * 1) + 2 
     = 7 * 9 + 2 
     = 65 

Wie Sie sehen können, ohne dass die Basis Fälle mit, Ihre Funktion wird unendlich laufen, weil rr(2) und rr(1) nie lösen; Stattdessen rufen sie den gleichen rekursiven Pfad rr(1).. rr(0).. rr(-1)..etc.