datawhale学习笔记（Leetcode基础算法202312）：task02递归算法与分治算法
递归算法是一种编程技术，其基本思想是将一个复杂的问题分解为更小的子问题，然后逐个解决这些子问题。在递归中，函数会直接或间接地调用自身，这就是为什么它被称为"递归"。每个递归函数通常都有两个基本部分：基线条件（base case）和递归条件（recursive case）。基线条件（base case）是递归结束的条件，也就是说，当满足这个条件时，函数将停止调用自身。递归条件（recursive case）是在满足这个条件的情况下，函数会继续调用自身，通常是在处理一个更小的子问题。
递归算法与分治算法
一、递归算法
1. 递归算法的定义
递归算法是一种编程技术，其基本思想是将一个复杂的问题分解为更小的子问题，然后逐个解决这些子问题。在递归中，函数会直接或间接地调用自身，这就是为什么它被称为“递归”。每个递归函数通常都有两个基本部分：基线条件和递归条件。
- 基线条件：是递归结束的条件，也就是说，当满足这个条件时，函数将停止调用自身。
- 递归条件：是在满足这个条件的情况下，函数会继续调用自身，通常是在处理一个更小的子问题。
2. 递归算法的中心思想
递归算法的实质是把问题分解成规模缩小的同类问题的子问题。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。递归算法具有以下显著特点：
- 基本部分：即那些可以直接满足条件并输出的情况；
- 递归部分：即通过改变问题的规模（例如参数
n），逐步使问题满足基本部分的条件，从而得出输出。 在实现的过程中，递归算法通常采用分治法的思想，即将整体问题分解为多个子问题，分别求解后再将结果合并。
3. 递归与迭代的比较
递归算法和迭代算法都是用来解决复杂问题的有效手段，它们将复杂问题分解为更小的子问题，然后逐步求解。然而，在实际操作中，二者具有显著的差异：
- 递归算法：通过函数自我调用来解决问题。其基本思想是将一个复杂的问题分解为更小的同类子问题，然后对子问题进行同样的处理，直到子问题无需进一步分解就可以解决。
- 迭代算法：通过重复执行某一段代码或某个过程，每次处理的结果都作为下一次处理的输入，从而逐步逼近问题的解。迭代过程中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
优缺点对比：
- 递归算法：代码简洁、易读、易理解，但可能会消耗更多的系统资源，并可能导致栈溢出错误。
- 迭代算法：通常具有更高的效率和更低的内存消耗，但可能缺乏递归的直观和简洁。 因此，选择使用哪种算法应根据具体的问题和环境来决定。
4. 递归算法的注意事项
使用递归需要注意避免出现死循环。为了确保递归正确工作，递归程序应该包含两个重要属性：
- 基本情况：用于保证程序调用能够及时返回，不再继续递归，从而保证了程序的可终止性。
- 递推关系：可以将所有其他情况拆分到基本情况中去。
二、分治算法
1. 分治算法的定义与中心思想
分治算法，字面上解释为“分而治之”，是一种在计算机科学中非常重要的算法设计策略。其核心思想是将一个规模较大的问题分解为两个或更多的相同或相似的子问题，然后将这些子问题进一步分解为规模更小的子问题，直到最后这些子问题可以简单地直接求解。原问题的解即子问题的解的合并。
基本步骤包括：
- 将一个复杂的问题分成两个或更多的相同或相似的子问题；
- 将这些子问题再分成规模更小的子问题；
- 对这些子问题进行求解；
- 将子问题的解合并得到原问题的解。
适用场景：
- 原问题规模大且不易解决，但可以缩小到一定程度就可以容易解决；
- 原问题可以分解为多个规模较小、求解方式相似的子问题，且各个子问题之间相互独立、互不影响。
2. 分治算法与递归算法的关系
分治算法和递归算法既有区别又有联系：
- 解决问题的方式不同：
- 分治法是一种算法设计思想，它将问题分解成更小的子问题，然后将子问题的解合并起来得到原问题的解。它是一种解决复杂问题的策略，适用于处理一些可以分解为多个独立子问题的问题。
- 递归是一种算法实现方法，它是通过函数调用自身来解决问题，即在函数内部直接或间接地自己调用自己。
- 联系与区别：
- 分治法可以使用递归来实现，但并非必须。递归只是一种编程技巧，一种解决问题的思维方式，可以在很多算法中看到它的身影（如深度优先搜索、回溯等）。
- 分治法还可以不用递归来实现，比如使用队列加循环也可以完成任务。
三、练习题
1. 递归算法练习题
题目一：斐波那契数列
(1) 题目描述
斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中n > 1给定n，请计算F(n)。
(2) 输入输出示例
示例 1：
输入：
n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：
n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2
(3) 代码思路
- A. 定义一个函数，名为
fib，接收一个参数n。 - B. 如果
n为 0 或 1，直接返回n（作为基线条件，停止递归）。 - C. 否则，返回
self.fib(n-1) + self.fib(n-2)的结果（作为递归条件，不断向下拆解问题）。
(4) 代码实现
class Solution(object):
def fib(self, n):
if n == 0 or n == 1:
return n
else:
return self.fib(n-1) + self.fib(n-2)
题目二：爬楼梯
(1) 问题描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
(2) 输入输出示例
示例 1：
输入：
n = 2输出：2解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入：
n = 3输出：3解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
(3) 代码思路
- A. 定义一个递归函数，输入参数为楼梯的阶数
n。 - B. 如果
n为 0 或 1，说明已经到达楼顶，返回 1（作为基线条件）。 - C. 如果
n大于 1，那么可以从当前台阶爬 1 阶或者 2 阶到达楼顶。因此，我们需要计算爬到n-1阶和n-2阶的方法数之和（作为递归条件）。 - D. 最后返回爬到
n阶的方法数。
(4) 代码实现
class Solution(object):
def climbStairs(self, n):
if n == 0 or n == 1:
return 1
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
2. 分治算法练习题
题目一：Pow(x, n)
(1) 问题描述
实现 pow(x, n)，即计算 x 的 n 次幂函数。
(2) 输入输出示例
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
(3) 代码思路
处理 n 为负数的情况；利用分治思想，每次将指数减半计算，若指数为偶数，则为半数幂的平方；若为奇数，则需额外乘以一次底数 x。
(4) 代码实现
class Solution(object):
def myPow(self, x, n):
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
return self.fast_pow(x, n)
def fast_pow(self, x, n):
if n == 1:
return x
self.half_pow = self.fast_pow(x, n // 2)
if n % 2 == 0:
return self.half_pow * self.half_pow
else:
return x * self.half_pow * self.half_pow