【前言】：上面的博文中讲解的2的幂除了运用位运算和利用约数来解题，其实还可以利用递归的思想，这里就向大家详细介绍一下，利用递归求2.3.4的幂

原题1: 2的幂

题目描述：

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。

示例1：

  

   

    

     

    
    

     

      输入：n = 1
     
    
   

    

     

    
    

     

      输出：true
     
    
   

    

     

    
    

     

      解释：2^0 = 1
     
    
  
 

示例2：

  

   

    

     

    
    

     

      输入：n = 3
     
    
   

    

     

    
    

     

      输出：false
     
    
  
 

在讲解递归解法之前，铁汁可以先把之前的方法再回顾一下，链接放在下面咯。

【手把手带你刷LeetCode】——01.2的幂_安然无虞的博客-CSDN博客

代码执行： 

  

   

    

     

    
    

     

      bool isPowerOfTwo(int n){
     
    
   

    

     

    
    

     
    if(n == 1){
     
    
   

    

     

    
    

     
        return true;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return (n > 0 && n % 2 == 0) ? isPowerOfTwo(n / 2) : false;
     
    
   

    

     

    
    

     

      }
     
    
  
 

 看起来是不是很简单，下面来分析一下复杂度。

时间复杂度：O(N)

空间复杂度：O(N)

为啥呢？因为递归调用了n / 2次，每次调用递归都需要建立一个栈帧，而每个栈帧又都使用了常数个空间，递归函数的空间复杂度取决于递归调用栈的深度，所以很明显，本题时间复杂度和空间复杂度都是O(N)。

原题2: 3的幂

题目描述：

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

示例1：

  

   

    

     

    
    

     

      输入：n = 27
     
    
   

    

     

    
    

     

      输出：true
     
    
  
 

示例2：

  

   

    

     

    
    

     

      输入：n = 0
     
    
   

    

     

    
    

     

      输出：false
     
    
  
 

代码执行：

  

   

    

     

    
    

     

      bool isPowerOfThree(int n){
     
    
   

    

     

    
    

     
    if(n == 1){
     
    
   

    

     

    
    

     
        return true;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return (n > 0 && n % 3 == 0) ? isPowerOfThree(n / 3) : false;
     
    
   

    

     

    
    

     

      }
     
    
  
 

复杂度分析： 

时间复杂度：O(N)

空间复杂度：O(N) 

哈哈，除了变了数字，其他都一样，所以4的幂留给铁汁咯，自己尝试一下哈。

力扣

总结

今天是力扣打卡第四天！！

每天都进步一点点是多么幸福的一件事，和铁汁们共勉哦，咱们明天再见！！！ 

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

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