描述

这是一篇针对初学者的题解。
知识点：逻辑运算符
难度：一星

题解

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

方法一：求和公式

可知求和公式*n%7D%7B2%7D "图片标题")
这种方法不行，因为需要用到乘法
代码如下：

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

时间复杂度：O(1)
空间复杂度：O(1)

方法二：循环求和

从1到n以步长为1，循环一下，但是此方法也不行，需要用到循环。
代码如下：

class Solution {
public:
    int Sum_Solution(int n) {
        int sum = n;
        for (int i=1; i<n; ++i)
            sum += i;
        return sum;
    }
};

时间复杂度：O(N)
空间复杂度：O(1)

方法三：递归

递归函数f(n)表示求1-n的和。
递推公式：f(n) = f(n-1) + n
递归终止条件：f(1) = 1
此方法也不行，递归终止条件需要用到if关键字
代码如下：

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

时间复杂度：O(N)
空间复杂度：O(N),需要开辟大约N个局部变量

方法四：递归变形

如果我们把方法三种的if换成别的，就可以了。
if (n==1) return 1;
也就是说如果n==1,需要终止递归，所以我们想到了逻辑与&&连接符。
A&&B，表示如果A成立则执行B，否则如果A不成立，不用执行B
因此我们可以这样。在n>1的时候，执行递归函数。
代码如下：

class Solution {
public:
    int Sum_Solution(int n) {
        bool x = n > 1 && (n += Sum_Solution(n-1)); // bool x只是为了不报错
        return n;
    }
};

时间复杂度：O(N)
空间复杂度：O(N),需要开辟大约N个局部变量