【前言】：HelloHello，大家好咩，我又来了哦。今天是力扣打卡第三天！大家看到这个标题是不是打心底认为太简单了，其实不然哦，难倒是不难，不过有很多限制哦，不信你朝后看。

原题：剑指Offer64.求1+2+...+n

题目描述：

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

注意题目约束条件哦！！

示例1：

  

   

    

     

    
    

     

      输入：3
     
    
   

    

     

    
    

     

      输出：6
     
    
  
 

示例2：

  

   

    

     

    
    

     

      输入：9
     
    
   

    

     

    
    

     

      输出：45
     
    
  
 

在之前蓝桥杯算法竞赛系列——深入理解重难点之递归中讲解过这道题的递归解法，忘了的童鞋可以再回顾一下哦。

https://blog.csdn.net/weixin_57544072/article/details/120836167

由于众多条件限制，就我们熟悉的解法中，还是只能选择递归了，但是终止条件不能用if语句，这又是一件麻烦的事，怎么办呢？请朝后看...

对，没错，逻辑操作符 &&和|| 具有一个重要的特性——短路求值

• 对于&& ，如果左侧表达式的值为false, 则表达式整体的值一定是false,此时无需计算右侧；
• 对于|| ，如果左侧表达式的值为true,则表达是整体的值一定是true,此时无需计算右侧

本题需要实现 “当 n ==1 时终止递归” 的需求，可通过短路效应实现。

n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归
 

代码执行：

方法一：

  

   

    

     

    
    

     

      int sumNums(int n){
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     

          n > 1 && (n += sumNums(n - 1));
     
    
   

    

     

    
    

     
    return n;
     
    
   

    

     

    
    

     

      }
     
    
  
 

 方法二：

  

   

    

     

    
    

     

      int sumNums(int n){
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     

          n == 1 || (n += sumNums(n - 1));
     
    
   

    

     

    
    

     
    return n;
     
    
   

    

     

    
    

     

      }
     
    
  
 

 复杂度分析

• 时间复杂度：O(N)  递归函数调用了 n 次，每次调用建立一个栈帧，每个栈帧使用了常数个空间O(1)     注意：调用时建立栈帧，返回时销毁。
• 空间复杂度：O(N)  递归函数的空间复杂度取决于递归调用栈的深度，这里递归函数调用栈深度为 O(N)

总结​​​​​​​

今天是力扣打卡第三天！冲冲冲，再忙也要刷题呀！！

感谢力扣里面的大佬给予的帮助，向大佬看齐！

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121090676