Pythonの再帰的な和関数ですか？

Question

本質的に、最初の "n"個の逆数の合計を返す関数r_sum（n）を作成しようとしています。 sum（5）= 1 + 1/2 + 1/3 + 1/4 + 1/5です。再帰が新しく、実装に問題があります。ここで私はこれまで持っているコードです：

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

私は機能のベースを作成していると思いますが、私は関数が自分自身を呼び出す必要がありますどこか分かりません。今のところ、関数は1/nの値を返すことに気付きました。私はこの合計を計算する関数自体を呼び出すようにこれにどのように追加できますか？

Answer 1

問題の一部を解決して、それ以外の部分が同じ問題の別のインスタンスであるように考えてみてください。

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

思う：最後の場合はする必要があります

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

そしてこうして：

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

として次のような

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 

return 1/n + sum_to(n - 1) 

Answer 3

これらの数値は、Harmonic Numbersとしてよく知られています。 H は通常定義されていませんが、それはポイントの横にあります。

何をしたいですか？sum_to(n)リターン？あなたはおそらく1/n + 1/(n-1) + ...を期待していますか？だから、単に1/nを返すべきではありません。その式の残りの部分を見て、sum_to(n - 1)がどこにあるのかを調べるべきです。ここで

• ストップ場合
• （再帰的に定義されている）他の一般的なケース

、あなたの停止の場合は、次のとおりです。

Answer 4

あなたは再帰関数を書くとき、あなたは二つのことを必要とします我々はsum_to(0) == 0を知っている。
一般的なケースは、sum_to(n) == 1.0/n + sum_to(n - 1)です。

すべてのことを行うには残っているが、関数内でこれらを結合です：

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

    return 1.0/n + sum_to(n - 1) 

Answer 5

発電機を使用するには、この問題を解決するための（杓子定規ではなく）Python的な方法です。

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) 

タイミングは、ジェネレーター解が約であることを示します。二倍の速さ：

• ジェネレータ：
  • %timeit -n 10000 v1 = g_sum(100)
  • 10000 loops, best of 3: 9.94 µs per loop
• 再帰：
  • %timeit -n 10000 v2 = r_sum(100)
  • 10000 loops, best of 3: 22 µs per loop

はまた、再帰的な実装では、実際の使用のために、それは非常に実用的でない非常に迅速に再帰制限をヒットします。具体的に

：r_sum(1000)はRecursionError: maximum recursion depth exceeded in comparison

Answer 6

であなたは二つの方法

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

または

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