Python 递归函数来计算总和？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19966290/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive function to calculate sum?
提问by kiasy
This is what I've got and I'm not sure why it's not working
这就是我所拥有的，但我不确定为什么它不起作用
def sum(n):
if (n>0):
print (n)
return sum(n)+sum(n-1)
else:
print("done doodly")
number = int(input(": "))
sum(number)
For example if the use inputs 5, I want to program to calculate the sum of 5+4+3+2+1. What am I doing wrong ?
例如如果使用输入5，我想编程来计算5+4+3+2+1的总和。我究竟做错了什么 ？
回答by inspectorG4dget
You forgot to returnwhen n==0(in your else)
你忘了return什么时候n==0（在你的else）
>>> def Sum(n):
... if not n:
... return 0
... else:
... return n + Sum(n-1)
...
>>> Sum(5)
15
回答by Simeon Visser
Two things:
两件事情：
- Calling
sum(n)when computingsumfornwon't do you much good because you'll recurse indefinitely. So the linereturn sum(n)+sum(n-1)is incorrect; it needs to benplus the sum of then - 1other values. This also makes sense as that's what you want to compute. - You need to return a value for the base case and for the recursive case.
sum(n)在计算时调用sumforn不会对你有多大好处，因为你会无限期地递归。所以这条线return sum(n)+sum(n-1)是不正确的；它需要n加上n - 1其他值的总和。这也是有道理的，因为这就是您想要计算的。- 您需要为基本情况和递归情况返回一个值。
As such you can simplify your code to:
因此，您可以将代码简化为：
def sum(n):
if n == 0:
return 0
return n + sum(n - 1)
回答by John La Rooy
You can complicateyour code to:
您可以将代码复杂化为：
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)
The advantage is that now you only use log(n)stack instead of nstack
好处是现在你只用log(n)stack 而不是nstack
回答by SzieberthAdam
Recursion is a wrong way to calculate the sum of the first n number, since you make the computer to do ncalculations (This runs in O(n) time.) which is a waste.
递归是计算前 n 个数字之和的错误方法，因为您让计算机进行n计算（这在 O(n) 时间内运行。）这是一种浪费。
You could even use the built-in sum()function with range(), but despite this code is looking nice and clean, it still runs in O(n):
您甚至可以将内置sum()函数与 一起使用range()，但尽管这段代码看起来不错且干净，但它仍然以 O(n) 运行：
>>> def sum_(n):
... return sum(range(1, n+1))
...
>>> sum_(5)
15
Instead recursion I recommend using the equation of sum of arithmetic series, since It runs in O(1) time:
相反，我建议使用算术级数和的等式递归，因为它在 O(1) 时间内运行：
>>> def sum_(n):
... return (n + n**2)//2
...
>>> sum_(5)
15
回答by anjaneyulubatta505
I think you can use the below mathematical function(complexity O(1)) instead of using recursion(complexity O(n))
我认为你可以使用下面的数学函数（复杂度 O(1)) 而不是使用递归（复杂度 O(n)）
def sum(n):
return (n*(n+1))/2
回答by TheRimalaya
Using Recursion
使用递归
def sum_upto(n):
return n + sum_upto(n-1) if n else 0
sum_upto(100)
5050
