分治策略与递归

分治策略

分治概念

任何可以用计算机求解的问题所需要的时间都与其规模有关。问题规模越小，所解题所需要的时间就越小，从而也较容易处理。例如：对于n个元素的排序问题，当n=1时，不需要任何计算，当n=2时，只要做一次比较即可排序好，n=3时，只要进行两次比较即可，当n越来越大，这个问题的就不那么容易处理了。要想直接解决一个较大的问题，比较困难。就需要用到分治思想。
分治法的设计思想是将一个难以直接解决的问题，分割成一些规模较小的相同问题，便于各个击破，分而治之，如果原问题可以分割成k个子问题，1

递归概念

递归：若一个函数直接或间接的调用自己，则称这个函数是递归函数。（自己调用自己）

分治策略的特征

分治法能解决的问题一般具有以下四个特征：

• 该问题的规模缩小到一定程度上可以很容易的解决。
• 该问题可以分解为若干个规模较小的相同问题。
• 使用小规模的解可以合并成为原问题规模的解。
• 该问题所解组合原规模问题的解。

分治法步骤

在分治策略中递归地求解一个问题，在每层递归中应用步骤如下：

• 分解：将问题划分成一些子问题，子问题的形式和原问题一样，知识规模更小。
• 解决：递归的求解子问题。如果子问题的规模足够小，则停止递归，直接求解。
• 合并：将小规模的解合成原问题规模的解。

举例

阶乘

循环的方法：

int fun(int n){
int sum=1;
  for(int i=1;i<=n;++i){
  sum*=i;
  }
  return sum;
}
1
2
3
4
5
6
7

递归：
加入n=4，便是如下图，n=4时将n-1的用作参数调用自身函数一直调用下去直到遇到最小的子问题n=1，n=1即可。

int fac(int n){
if(n==1) return n;
else return fac(n-1)*n;
}
1
2
3
4

有了阶乘这个举例，我们从内存来看递归，每调用一次函数，系统就会开辟一个栈桢，不可能无限开辟，因为栈的大小是有限的，所以也不可能无限递归。一直递归下去，直到找到最小问题的解，才会开始释放空间，原理和栈一样，先开辟的后释放，

斐波那契数列

循环：

int fib(int n){
 int a=1,b=1,c=1;
 for(int i=3;i<n;++i){
 c=a+b;
 a=b;
 b=c;
 }
 return c;
 }
1
2
3
4
5
6
7
8
9

递归程序：

int fib(int n){
if(n==1||n==2) return 1;
else return fib(n-1)+fib(n-2);
}
1
2
3
4

其很明显第n位等于第n-1位与第n-2位的和，其递推关系图就是二叉树的样子，用这样递归的话其时间复杂度位O(2^n)，空间复杂度时S(n)，而循环时间复杂度为O(n),有没有其他办法使得其时间复杂度为O(n)呢，我们看如下代码：

int fibc(int n,int a,int b) {
	if (n == 1 || n == 2) return a;
	else {
		return fibc(n - 1, b,a+b);
	}
	
}
int fun(int n) {
	int a = 1, b = 1;
	return fibc(n, a, b);
}
1
2
3
4
5
6
7
8
9
10
11

这时怎么样一个思想呢，其实就是将循环的代码转换成了递归，循环中我们将c作为中间变量进行输出，此处呢我们没有用到循环变量，直接将b和a+b作为参数调用自身函数。

打印数组

代码：

void Print(const int *arr,int n){
    Print(*arr,n-1);
    Print("%5d",arr[n-1]);
}
void Printar(const int *arr,int n) {
	if (arr == nullptr||n<1) return;
	Print(arr,n);
	printf("\n");
}
1
2
3
4
5
6
7
8
9

我们通过仔细观察就会发现Print（）函数中，如果先输出就会输出倒着打印，如果先调用函数就会顺序打印。

数组中查找元素

int Find(const int *arr,int n,const int val) {
	if (n == 0 || arr[n-1]==val) return n-1;
	else return Find(arr, n-1,val);
	
}
int Findvalue(const int *arr,int n,const int val) {
	if (arr == nullptr || n < 1) return -1;
	else return Find(arr, n, val);
}
/*
int Findvalue(const int *arr,int n,const int val) {
	if (arr == nullptr||n<1) return -1;
	else {
		if(val==arr[n-1]) return n-1;
		Findvalue(arr, n - 1, val);
	}
}
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

通过做题便可以让自己的逻辑更加鲜明，下去可以多做一写题来找到递归的技巧。