【剑指offer系列】71. 求1+2+…+n

这里是剑指offer系列的延续，作者将利用C++实现继续完成该系列的学习，剑指offer，喜欢的话可以点赞关注＋收藏，加油更新中ing。

---

题目71. 求1+2+…+n

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

数据范围
1≤n≤1000。

样例

输入：10

输出：55
1
2
3

【题解】— 递归

最直接的想法就是用递归，递归（Recursion），在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。通俗理解就是：我调用我自己。但使用递归时也要 注意：

1. 递归一定要有条件限定，保证递归能够停止下来，否则会发生栈内存溢出。

2. 在递归中虽然有限定条件，但是递归次数不能太多。否则也会发生栈内存溢出。

3. 构造方法,禁止递归。

sum(n) = n+sum(n-1)，但是要注意终止条件;

由于求的是1+2+…+n的和，所以需要在n=0的时候跳出递归，

但是题目要求不能使用if,while等分支判断，可以考虑利用&&短路运算来终止判断。

此外，当然也可以用公式法。

复杂度分析：

递归，复杂度为O(n)。
1

C++代码实现：

class Solution {
public:
    int getSum(int n) {
        int res = n;
        (n>0) && (res += getSum(n-1));//利用短路运算终止递归
        return res;
    }
};

// 公式方法：
class Solution {
public:
    int getSum(int n) {
        return (long long)n*(1+n)/2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

剑指offer系列将后续持续更新，有帮助的话，欢迎点赞👍、收藏⭐️＋关注✌️哟~

---