@TOC

剑指 Offer 64. 求1+2+…+n

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

• 1 <= n <= 10000

解题思路

按常规思路可以直接用等比数列求和公式 sum = n*(n+1)/2即可，但是题目要求不能用乘除法，排除。

使用for循环，遍历一次，将所有数加起来，但是题目要求不能用for和while，排除。

用递归，常规递归如下：

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

但是我们发现其中用了if,同样不符合题目要求，怎么办？

我们想到了&& 和||运算符的短路特性。所以可以用&&来完成结束递归的操作。

Java代码

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