如何获取Python算法的数学公式？

Question

好吧，我有点不好意思，因为我不知道这个，但同事问了这个问题，所以我也来问一下：我写了一个Python算法来解决他的难题。给定一个大于0的数字x，要把从1加到x的所有数字加在一起。

def intsum(x):
  if x > 0:
    return x + intsum(x - 1)
  else:
    return 0

intsum(10)
55

首先，这种类型的数学问题是什么？用什么正确的方法来得到这个答案呢？显然，使用其他方法会更简单一些。

Answer 1

下面是如何证明一个等差数列的封闭形式的方法。

S  = 1 +   2   + ... + (n-1) + n
S  = n + (n-1) + ... +   2   + 1
2S = (n+1) + (n+1) + ... + (n+1) + (n+1)
     ^ you'll note that there are n terms there.
2S = n(n+1)
S = n(n+1)/2

Answer 2

把递归定义的整数序列转变成可以用简单公式表达的形式，是离散数学中一个很有趣的部分。我强烈推荐一本书，叫做《具体数学：计算机科学的基础》，作者是罗纳德·格雷厄姆、唐纳德·克努斯和奥伦·帕塔什尼克（你可以看看维基百科上的介绍）。

不过，你提到的这个具体序列fac(x) = fac(x - 1) + x，有个有趣的故事。传说高斯在他上小学一年级的时候就解决了这个问题。老师给学生们布置了一个任务，让他们把1到100的数字加起来，以便让他们安静一会儿。结果两分钟后，小高斯就跑来了，给出了答案5050，并解释说：“我注意到，第一和最后的数字1和100加起来是101；第二和倒数第二的数字2和99加起来也是101；这明显重复了50次，所以就是50乘以101，得5050。”虽然这个证明不够严谨，但对于一个6岁的孩子来说，这个思路是非常正确的。

同样的道理（加上一点非常基础的代数），你可以看到一般情况下，正如很多人已经说过的，结果是(N * (N+1)) / 2（这个乘法的结果总是偶数，因为其中一个数字一定是奇数，另一个是偶数；所以除以2后总会得到一个整数，没有余数）。

Answer 3

这是递归，不过你却把它标记成了阶乘，真是奇怪。

无论如何，从1加到n的和其实也很简单：

n * ( n + 1 ) / 2

（如果你愿意的话，可以单独处理负数的情况。）