跟着姚桑学算法-求1+2+…+n

题. 求1+2+…+n

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

数据范围
1≤n≤1000。

样例

输入：10

输出：55

        

          
        
        
        

          

          AI 代码解读
        
      
      

【题解】--- 递归

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

1. 递归一定要有条件限定，保证递归能够停止下来，否则会发生栈内存溢出。
2. 在递归中虽然有限定条件，但是递归次数不能太多。否则也会发生栈内存溢出。
3. 构造方法,禁止递归。

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

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

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

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

复杂度分析：

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

        

          
        
        
        

          

          AI 代码解读
        
      
      

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;
    }
};

        

          
        
        
        

          

          AI 代码解读