【算法】递归系列：递归初介绍，练习：231.2 的幂、

目录

一、理解递归

1、什么是递归？

2、为什么会使用递归？

3、递归使用的场景？

4、那么如何写出递归解法？

二、实践

231. 2的幂

 1.函数头的设计

 2.只关心某一个子问题是如何解决的 ->函数体的书写

  3.注意一下递归函数的出口即可

---

一、理解递归

1、什么是递归？

函数自己调用自己。

2、为什么会使用递归？

遇到一个问题。

这个问题可以被分解为多个子问题，子问题都相同，并且与主问题相同。

3、递归使用的场景？

在解决⼀个规模为n的问题时，如果满足以下条件，
我们可以使用递归来解决：

a. 问题可以被划分为规模更小的子问题，并且这些⼦问题具有与原问题相同的解决方法。
b. 当我们知道规模更小的⼦问题（规模为 n - 1）的解时，我们可以直接计算出规模为 n 的问题的解。
c. 存在⼀种简单情况，或者说当问题的规模⾜够⼩时，我们可以直接求解问题。

⼀般的递归求解过程如下：
a. 验证是否满⾜简单情况。
b. 假设较小规模的问题已经解决，解决当前问题。

4、那么如何写出递归解法？

首先，宏观看待递归的过程
        1.不要在意递归的细节展开图
        2.把递归的函数当成一个黑盒
        3.相信这个黑盒一定能完成这个任务

然后，具体操作。

        1.先找到相同的子问题!!!->函数头的设计
        2.只关心某一个子问题是如何解决的 ->函数体的书写
        3.注意一下递归函数的出口即可

二、实践

231. 2 的幂 - 力扣（LeetCode）

231. 2的幂

分析：

n 为 2 的幂需要满足以下条件：

 1、n 是正整数

 2、n是偶数

 1.函数头的设计

bool isPowerOfTwo(int n)

 2.只关心某一个子问题是如何解决的 ->函数体的书写

之前分析，非正整数不符合n。因此，可以直接进行排除。

if( n <= 0)return false;

检查 n 是否等于 1。因为 20=1，所以 1 是 2 的幂次方，直接返回 true。

if(n == 1)return true;

奇数，也不符合。直接排除

if(n % 2 == 1)return  false;

  3.注意一下递归函数的出口即可

而函数的退出条件则是在 n 为 1 的时候。

class Solution {
public:bool isPowerOfTwo(int n) {if(n == 1)return true;if(n<=0)return false;if(n%2 == 1)return  false;return    isPowerOfTwo(n/2);  }
};