题目：求1+2+3+...+n

描述:求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

递归思路分析：首先判断当n的值为0时，可以直接返回最后的结果值为0。当n的值大于0时，使用递归算法来计算最终的结果。利用逻辑与关系判别实现递归是否终止。


实例分析：输入：5

输入n的值为5，首先将n的值进行判断分析，设定res为最终结果

1

2

3

4

res = 5

 

 

 

res = res+4

递归法再次执行

 

 

res = res+3

递归法再次执行

 

 

res = res+2

递归法再次执行

 

 

res = res+2

递归法再次执行

 

 


具体C++代码如下所示：  

class Solution {
public:
    int Sum_Solution(int n) {
        if(n <= 1) 
            return n; 
        int res = n; 
        res && ( res = res + Sum_Solution(n-1) ); 
        return res; 
    } 
};

时间复杂度：O(N)，空间复杂度：O(N)。

数学公式推导法：数学中的求和公式为Sum =（（1+n）n）/2，其中n的值可由输入端直接得到，从而直接计算出和的大小。
实例分析：输入：5
        将n = 5直接带入公式计算sum的值：
        

具体C++代码如下所示：  

class Solution {
public:
    int Sum_Solution(int n) {
        int sum = 0;
        sum = n*(n + 1)/2;
        return sum;
    }
};

时间复杂度为O(1)，空间复杂度为O(1)。

解法三：
       思路分析：因为不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句，所以可以采用数学公式法：等差数列法。
        构建一个等差数列，sum = (a1 + an)n/2 => (1 + n)n/2 => (n + n^2)/2
        其java代码为： 
public class Solution {
    public int Sum_Solution(int n) {
        int sum=(int)Math.pow(n, 2)+n;//Math.pow(a,b)表示a^b
        return sum>>1;//右移一位相当于除以2。
    }
};