33. 递归计算累加和

一. 问题

给定一个数 n ，用递归的手法求出从 1 到 n 的累加和。

1. 实例分析

假设传入参数 n = 5。

（方法一）高斯公式

1 int gauss_sum(int n) {
2     int sum = (1 + n) * n / 2;
3 
4     return sum;
5 }

利用公式，一次即可算出答案，时间复杂度为 O(1)。

（方法二）循环计算

1 int normal_sum(int n) {
2     int sum = 0;
3     for (int i = 1; i <= n; ++i) {
4         sum += i;
5     }
6 
7     return sum;
8 }

用一个累加器，从 1 累加到 n ，时间复杂度为 O(n)。

（方法三）递归计算

1 int recursion_sum(int n) {
2     if (n == 1) {
3         return 1;
4     }
5 
6     return n + recursion_sum(n - 1);
7 }

这种手法是从后面加到前面，先加 n ，再加 (n - 1)，最后一直加到 1 。当 n = 1时，函数把 1 返回，然后逐层返回，直到计算出结果。