递归求和

思路

求 1 到 N 的和就是从 1 一直加到 N 本身，比如求 1 到 5 的和就是 SUM(5) = 5+4+3+2+1，6 的和就是 SUM(6) = 6+5+4+3+2+1。同时，我们可以看出，其实 6 的和也可以简化为 SUM(6) = 6 + SUM(5)。

同理，可以推断出 SUM(N) = N + SUM(N-1)，那么这个问题我们就可以使用递归来解决，递归的出口就是 N 等于 1 时，和为 1。具体过程可以简化如下：

SUM(1) = 1
SUM(2) = 2 + 1 = 2 + SUM(1)
SUM(3) = 3 + 2 + 1 = 3 + SUM(2)
SUM(4) = 4 + 3 + 2 + 1 = 4 + SUM(3)
SUM(5) = 5 + 4 + 3 + 2 + 1 = 5 + SUM(4)
SUM(6) = 6 + 5 + 4 + 3 + 2 + 1 = 6 + SUM(5)
...
SUM(N) = N + (N-1) + (N-2) + ... + 1 = N + SUM(N-1)

实现

#include <stdio.h>
int sum(int n)
{
	int ret = 0;
	int i = 0;
	for(i = 1; i <= n; i++)
	{
		ret += i;
	}
	return ret;
}
int sum2(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return n+sum2(n-1);
	}
}
int main()
{
	printf("嗨客网（www.haicoder.net）\n\n");
	int sum100 = sum(100);
	int sum101 = sum(101);
	printf("使用for循环实现和100 = %d, 和101 = %d\n\n", sum100, sum101);
	int sum100_2 = sum2(100);
	int sum101_2 = sum2(101);
	printf("使用递归实现和100 = %d, 和101 = %d\n", sum100_2, sum101_2);
	return 0;
}

运行结果如下：

我们分别使用了 for 循环 的方式和递归的方式来实现了求和，for 循环的思路就是从 1 一直加到 N 即可。递归的方式就是用 N 加上 N-1 的和，出口就是当 N = 1 时，直接返回 1 即可。