目录

• 分治策略
• • 分治概念
  • 递归概念
  • 分治策略的特征
  • 分治法步骤
• 举例
• • 阶乘
  • 斐波那契数列
  • 打印数组
  • 数组中查找元素

分治策略

分治概念

任何可以用计算机求解的问题所需要的时间都与其规模有关。问题规模越小，所解题所需要的时间就越小，从而也较容易处理。例如：对于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;
}

递归：
加入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;
}

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

斐波那契数列

循环：

int fib(int n){int a=1,b=1,c=1;for(int i=3;ic=a+b;a=b;b=c;}return c;}

递归程序：

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

其很明显第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);
}

这时怎么样一个思想呢，其实就是将循环的代码转换成了递归，循环中我们将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");
}

我们通过仔细观察就会发现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);}
}
*/

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