前言

我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！

一.简介

1.递归：

在数学和计算科学中是指在函数的定义中使用函数自身的方法，在将数据科学中还额外指一种通过将重复问题分解为子问题，而解决问题方法

2.分治：

把一个复杂问题分成两个或者多个子问题，子问题相互独立，直到最后子问题可以简单求解 （其中的子问题可以用递归）

二.解决办法

1.递归

1.1步骤：

1.找到递归出口（一般是最后一步）
2.找到递归条件：试着用小数据推一下，在站在第i个问题的角度去考虑

注：在递归过程中，将该函数认为是已完成函数

1.2例题

力扣面试题 08.06. 汉诺塔问题

class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {int n = A.size();move(n, A, B, C);}void move(int n, vector<int>& A, vector<int>& B, vector<int>& C){if(n == 1){C.push_back(A.back());A.pop_back();return;}move(n - 1, A, C, B);C.push_back(A.back());A.pop_back();move(n - 1, B, A, C);}
};

2.分治

2.1例题

力扣53. 最大子数组和

class Solution {
public:int maxMid(vector<int>& nums, int l, int r, int m) {//寻找中间最大值函数int lsum = INT_MIN;//左边最大值int rsum = INT_MIN;//右边最大值int sum = 0;//当前值for (int i = m; i >= l; i--) {//找左边sum += nums[i];lsum = max(sum, lsum);}sum = 0;for (int i = m + 1; i <= r; i++) {//找右边sum += nums[i];rsum = max(sum, rsum);}return lsum + rsum;//返回中间最大值}int maxSub(vector<int>& nums, int l, int r) {//寻找最大值if (l == r) {//结束条件return nums[l];}int mid = l + (r - l) / 2;//中间值int lsum = maxSub(nums, l, mid);//左int rsum = maxSub(nums, mid + 1, r);//右int msum = maxMid(nums, l, r, mid);//中间return max({ lsum, rsum, msum });//最大值}int maxSubArray(vector<int>& nums) {int n = nums.size();return maxSub(nums, 0, n - 1);}
};

2.2解释

取中心点M=(l + r) / 2。和的最大区间要么在中心点的左边，要么在中心点的右边，要么横跨中心点，所以问题分解为求这三个部分的最大区间和，然后再求这三个哪个最大—分成3个独立的小问题，分治
1.左边：递归
2.右边：递归
3.中间：贪心：lmax + rmax

三.总结

递归是一种编程技巧，一种解决问题的思维方式；
分治算法很大程度上是基于递归的，解决更具体问题的算法思想；