题目描述

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

• $1 <= n <= 10000$

---

算法

(递归) $O(n)$

递归求解替换 $for$ 循环 $1 + 2 + … + n$
只不过需要将 $if$ 替换掉，依据 A && B 的性质，如果 A 为 false，B 就不执行，如果 A 是 true，B 还要进行判断。同样的对于 A || B 依然有类似的性质，如果 A 是 true，B 就不执行，如果 A 是 false，B 还要进行判断。

因此我们可以用逻辑与 &&​ 运算符将 if 完美替换
if (n > 0) res += getSum(n - 1) -> n > 0 && (res += getSum(n - 1))

时间复杂度

递归 $n$ 次，时间复杂度为 $O(n)$

时间复杂度

递归系统调用栈的空间为 $O(n)$

C++ 代码

class Solution {
public:
    int sumNums(int n) {
        int res = n;
        n > 0 && (res += sumNums(n - 1));
        return res;
    }
};