递归函数计算1到n的和？

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的和。我做错了什么？

---

^{如需非递归版本，请参见从1到n的整数之和}

- kiasy

Answer 1

有两个问题：

• 在计算 n 的和时调用 sum(n) 不会给你带来太多好处，因为它会无限递归。所以行 return sum(n)+sum(n-1) 是不正确的; 它需要是 n 加上其他 n - 1 值的总和。这也很合理，因为这就是你想要计算的。
• 你需要为基本情况和递归情况返回一个值。

因此，您可以简化您的代码为:

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

- Simeon Visser

---

现在我该如何打印总和？@Simeon Visser - kiasy

print sum(n) - 让 sum 的返回值成为 print 的参数。 - chepner

@kiasy 是的，让 sum 计算结果，然后在它完成后打印出来。 - Simeon Visser

Answer 2

在您的else中，当n==0时，您忘记了return

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

- inspectorG4dget

Answer 3

递归不是计算前n个数字之和的正确方法，因为它会让计算机进行n次计算（这需要O(n)时间），这是一种浪费。

你甚至可以使用内置的sum()函数和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

- SzieberthAdam

Answer 4

我认为您可以使用下面的数学函数（复杂度为O(1)）代替使用递归（复杂度为O(n)）。

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

- anjaneyulubatta505

Answer 5

你可以通过复杂化你的代码来实现：

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的堆栈。

- John La Rooy

Answer 6

使用递归

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

sum_upto(100)

5050

- TheRimalaya

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))

- Alvison Hunter