递归求解1到100求和

递归求解1到100的和是一个常见面试题。

思想：

思考一下，从1加到100可以分解成：

• 1+（2加到100的和）
• 1+2+（3加到100的和）
• 1+2+3+（4加到100的和）
• ……

怎么样，这样是不是有点递归的味道了？递归的出口就是1。

所以，可以编写如下代码：

代码：

int count(int n)
{
	if (n > 1)
	{
		return n + count(n - 1);
	}
	else
	return 1;
}

这样，不仅可以求1到100的和，还可以求任意区间数字的和。只要改变递归出口和上限即可。