本文讲述了python基础编程100例：第87期-基础算法：递归 2的幂！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第87期-基础算法：递归 2的幂

1 问题描述

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

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

示例 1:

输入: n = 1

输出: true

解释: 2**0 = 1

示例 2:

输入: n = 16

输出: true

解释: 2**4 = 16

示例 3:

输入: n = 3

输出: false

示例 4:

输入: n = 4

输出: true

示例 5:

输入: n = 5

输出: false

初始代码

from typing import List

class Solution:

    def isPowerOfTwo(self, n: int) -> bool:

        #在此之间填写代码

print(Solution().isPowerOfTwo(1))

print(Solution().isPowerOfTwo(16))

print(Solution().isPowerOfTwo(3))

print(Solution().isPowerOfTwo(4))

print(Solution().isPowerOfTwo(5))

2 解题思路

标签：递归

判断该数是否可以整除2，若可以，再判断除以2后得到的数是否也可以整除2

若可以一直下去直到结果为1，则返回True

其他情况则返回False

3 解题方法

from typing import List

class Solution:

    def isPowerOfTwo(self, n: int) -> bool:

        if n==0:return False

        if n==1:return True

        return n%2==0 and self.isPowerOfTwo(n/2)

print(Solution().isPowerOfTwo(1))

print(Solution().isPowerOfTwo(16))

print(Solution().isPowerOfTwo(3))

print(Solution().isPowerOfTwo(4))

print(Solution().isPowerOfTwo(5))

第1-3，8-12行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 判断若a等于0，则返回False

第5行： 判断若a等于1，则返回True

第6行： 其他情况下，若n除以2的余数为0且除之后得到的数也是2的幂，则返回True，若有一者不满足，则返回False

代码运行结果为：

算法讲解

这里用到了基础算法：递归，简单讲解下这个算法：

什么是递归

程序调用自身的编程技巧称为递归

递归做为一种算法在程序设计语言中广泛应用。

递归算法一般用于解决三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）

(2)问题解法按递归算法实现。

(3)数据的结构形式是按递归定义的。

递归函数特征

必须有一个明确的结束条件；

每次进入更深一层递归时，问题规模相比上次递归都应有所减少

相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。

递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。