Rekursive Summenfunktion in Python?

Question

Im Wesentlichen versuche ich eine Funktion zu erstellen, r_sum (n), die die Summe der ersten "n" reziproken zurückgibt: z.B. sum (5) = 1 + 1/2 + 1/3 + 1/4 + 1/5. Ich bin neu in der Rekursion und habe Probleme mit der Implementierung. Hier ist der Code, den ich bisher habe:

def r_sum(n): 
    if n == 0: 
     return 0 
    elif n == 1: 
     return 1 
    else: 
     return 1/n 

Ich glaube, ich habe die Basis der Funktion erstellt, aber ich bin nicht sicher, wo ich hätte die Funktion selbst aufrufen. Jetzt weiß ich, dass die Funktion nur den Wert 1/n zurückgibt. Wie kann ich das hinzufügen, so dass ich die Funktion habe selbst anrufen, um diese Summe zu berechnen?

Answer 1

Versuchen Sie zu denken, ein Teil des Problems zu lösen, so dass der Rest eine weitere Instanz des gleichen Problems ist, nur für einen kleineren Brocken.

def sum_to(n): 
    if n == 0: 
     return 0.0 
    elif n == 1: 
     return 1.0 
    else: 
     return 1.0/n + sum_to(n-1) 

Answer 2

Denken Sie an:

sum(5) = 1 + 1/2 + 1/3 + 1/4 + 1/5 

als:

sum(5) = 1/5 + sum(4) 
sum(4) = 1/4 + sum(3) 
sum(3) = 1/3 + sum(2) 
sum(2) = 1/2 + sum(1) 
sum(1) = 1 

Als solche:

sum(x) = 1/x + sum(x-1) 
sum(1) = 1 

Und somit der letzte Fall sollte sein:

return 1/n + sum_to(n - 1) 

Answer 3

Diese Nummern sind besser bekannt als Harmonic Numbers. Es ist erwähnenswert, dass H normalerweise nicht definiert ist, aber das ist neben dem Punkt.

Was möchten Sie sum_to(n) zurückgeben? Sie erwarten wahrscheinlich 1/n + 1/(n-1) + ... richtig? Also sollten wir nicht einfach 1/n zurückgeben. Sie sollten den Rest dieses Ausdrucks betrachten und finden, wo Sie sum_to(n - 1) finden können.

Answer 4

Wenn Sie eine rekursive Funktion schreiben, müssen Sie zwei Dinge:

• ein Stopp Fall
• der andere allgemeine Fall

(die rekursiv definiert ist)

Hier ist Ihr Stop-Fall 0. Wir wissen sum_to(0) == 0. Der allgemeine Fall ist: sum_to(n) == 1.0/n + sum_to(n - 1).

, dass alle noch zu tun ist, diese in einer Funktion verbinden:

def sum_to(n): 
    if n == 0: 
     return 0 

    return 1.0/n + sum_to(n - 1) 

Answer 5

Mit Generatoren die Pythonic ist Art und Weise (im Gegensatz zu der pedantischen Gegensatz) Um dieses Problem zu lösen.

def g_sum(n): 
    """ 
    Solution using generators instead of recursion. 
    Input validation suppressed for clarity. 
    """ 
    return sum(1/x for x in range(1, n+1)) 

def r_sum(n): 
    """ 
    Recursive solution proposed by @Alfe 
    """ 
    return 0 if n == 0 else 1/n + r_sum(n-1) 

Das Timing der Funktion zeigt, dass die Generatorlösung ca.doppelt so schnell:

• Generator:
  • %timeit -n 10000 v1 = g_sum(100)
  • 10000 loops, best of 3: 9.94 µs per loop
• Rekursion:
  • %timeit -n 10000 v2 = r_sum(100)
  • 10000 loops, best of 3: 22 µs per loop

Darüber hinaus wird die rekursive Implementierung sehr schnell eine Rekursion Grenze trifft es sehr unpraktisch für realen Gebrauch.

Im Einzelnen: r_sum(1000) schlägt mit RecursionError: maximum recursion depth exceeded in comparison

Answer 6

Sie dies auf zwei Arten tun können

def r_sum(n): 
    if n == 1: 
     return 1 
    return (1/n) + r_sum(n-1) 

oder

def r_sum(n): 
    return sum(map(lambda x:1.0/x, xrange(1, n+1)))