python - 递归函数计算总和？

Question

这就是我所拥有的，我不确定为什么它不起作用

def sum(n):
    if (n>0):
        print (n)
        return sum(n)+sum(n-1)
    else:
        print("done doodly")

number = int(input(":  "))
sum(number)

例如，如果使用输入 5，我想编程计算 5+4+3+2+1 的总和。我究竟做错了什么 ？

Answer 1

两件事情：

• sum(n)在计算sumfor时调用n不会对你有多大好处，因为你会无限期地递归。所以这条线return sum(n)+sum(n-1)是不正确的；它需要n加上n - 1其他值的总和。这也是有道理的，因为这就是您想要计算的。
• 您需要为基本情况和递归情况返回一个值。

因此，您可以将代码简化为：

def sum(n):
    if n == 0:
        return 0
    return n + sum(n - 1)

Answer 2

递归是计算第一个 n 数之和的错误方法，因为您让计算机进行n计算（这在 O(n) 时间内运行。）这是一种浪费。

你甚至可以使用内置sum()函数 with range()，但是尽管这段代码看起来很干净，它仍然在 O(n) 中运行：

>>> def sum_(n):
...     return sum(range(1, n+1))
...
>>> sum_(5)
15

相反，我建议使用算术级数总和方程，因为它在 O(1) 时间内运行：

>>> def sum_(n):
...     return (n + n**2)//2
...
>>> sum_(5)
15

Answer 3

你忘了return什么时候n==0（在你的else）

>>> def Sum(n):
...   if not n:
...     return 0
...   else:
...     return n + Sum(n-1)
... 
>>> Sum(5)
15

Answer 4

您可以将代码复杂化为：

def my_sum(n, first=0):
    if n == first:
        return 0
    else:
        return n + my_sum(n-1, (n+first)//2) + my_sum((n+first)//2, first)

好处是现在你只使用log(n)堆栈而不是n堆栈

Answer 5

使用递归

def sum_upto(n):
  return n + sum_upto(n-1) if n else 0

sum_upto(100)

5050

Answer 6

我认为您可以使用以下数学函数（复杂度 O(1)）而不是使用递归（复杂度 O(n)）

def sum(n):
    return (n*(n+1))/2

Answer 7

请查看以下关于您的请求的代码段。我当然希望这会有所帮助。干杯!

def recursive_sum(n):
    return n if n <= 1 else n + recursive_sum(n-1)

# Please change the number to test other scenarios.
num = 100

if num < 0:
   print("Please enter a positive number")
else:
   print("The sum is",recursive_sum(num))