如何使用递归求序列1+（1*2）+（1*2*3）…（1*2*3*…n）的和？

Question

这就是我目前的情况

def factorial(n):
  if n == 0:
    return 1 
  else: 
    return n * factorial(n-1)

计算阶乘，但我怎么加和呢？你知道吗

Answer 1

增加了在实践中用于这些类型递归函数的记忆，通过消除重复计算来提高效率（即https://www.python-course.eu/python3_memoization.php）

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def sum_of_factorial(n):
  if n==0:
    return 0
  return factorial(n) + sum_of_factorial(n-1)

@memoize
def factorial(n):
  if n == 0:
    return 1 
  else: 
    return n * factorial(n-1)

Answer 2

@DarryIG和@bkbb的答案会起作用，但效率很低，因为它会对相同的数字进行重复的递归调用，对于较高的数字，这些调用的结果是相同的。您可以缓存结果以提高效率。你知道吗

此外，由于：

sum_factorials(n) = (sum_factorials(n-1) - sum_factorials(n-2)) * n + sum_factorials(n-1)

实现递归实际上不需要两个函数：

def sum_factorials(n, cache=[0, 1]):
    if len(cache) > n:
        return cache[n]
    previous = sum_factorials(n - 1)
    cache.append((previous - sum_factorials(n - 2)) * n + previous)
    return cache[n]

因此sum_factorials(4)返回：

33

Answer 3

使用functools.reduce进行乘法的带生成器的替代单一递归解决方案：

from functools import reduce as _r
def fact_sum(n, f = True):
   if not f and n:
      yield from [n, *fact_sum(n - 1, f = False)]
   if f and n:
      new_n = _r(lambda x, y:x*y, list(fact_sum(n, f = False)))
      yield from [new_n, *fact_sum(n - 1, f = True)]

print(sum(fact_sum(3)))
print(sum(fact_sum(4)))

输出：

9
33