目录
前言
总结算法设计与分析课程期末必记知识点。
第二章递归算法设计技术
1、递归的定义
递归是指在函数的定义中又调用函数自身的方法，若p函数定义中调用p函数，称之为直接递归；若p函数定义中调用q函数，而q函数定义中又调用p函数，称之为间接递归
2、求 n! 的递归算法
int fun(int n){
if(n==1)
return(1);
else
return(fun(n-1)*n);
}3、能够用递归解决的问题应该满足以下3个条件
（1）需要解决的问题可以转换为一个或多个子问题来求解，而这些子问题的求解与原问题完全相同，只是在数量规模上不同。
（2）递归调用的次数必须是有限的。
（3）必须有结束递归的条件来终止递归。
4、三种情况下用递归
（1）定义是递归
（2）数据结构是递归
（3）问题的求解方法是递归。
5、递归模型
递归出口和递归体
6、递归执行是通过系统栈实现的
7、斐波那契数列
斐波那契数列定义
F(n) = 1 , n=1
F(n) = 1 , n=2
F(n) = F(n-1) + F(n-2) , n>2
斐波那契数列对应的递归算法
int Fib(int n){
if(n==1||n==2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}8、提取递归模型的基本步骤
（1）寻找大问题S(n)，小问题S(n-1)
（2）假设S(n-1)已解，构建f(Sn)，f(S(n-1))之间的关系
（3）给出口f(1)或f(0)
9、简单选择排序（大题）
#include<stdio.h>
void swap(int &x,int &y){ //交换x和y的值
int tmp=x;
x=y;
y=tmp;
}
void disp(int a[],int n){ //输出 a 中的所有元素
int i;
for(i=0;i<n;i++)
printf("%d",a[i]);
printf("\n");
}
void SelectSort(int a[], int n,int i){
int j,k;
if(i==n-1)return;
else
{
k=i;
for(j=i+1;j<n;j++){
if(a[j]<a[k]){
k=j;
}
}
if(k!=i)
swap(a[i],a[k]);
SelectSort(a,n,i+1);
}
}
int main(){
int n=7;
int a[]={2,5,1,7,10,16,11};
printf("排序前：");
disp(a,n);
SelectSort(a,n,0);
printf("排序后：");
disp(a,n);
return 0;
}10、冒泡排序（大题）
//冒泡排序
void BubbleSort(int a[],int n,int i){
int j;
bool exchange;
if(i==n-1) return; //满足递归出口条件
else
{
exchange = false; //置exchange为flase
for(j=n-1;j>i;j--){ //将 a[i..n-1] 中的最小元素放到 a[i] 处
if(a[j]<a[j-1]) //当相邻元素反序时
{
swap(a[j],a[j-1]);
exchange=true;
}
}
if(exchange == false)//为发生交换时候直接返回
return;
else
BubbeSort(a,n,i+1);
}
} 11、n皇后问题所有解的完整程序（大题）
#include<stdio.h>
#include<stdlib.h>
#define N 20 //最多皇后个数
int q[N]; //存放各个皇后所在的列号，即（i,q[i]）为一个皇后位置
int count = 0; //累计解个数
void dispasolution(int n) //输出 n 皇后问题的一个解
{
printf(" 第%d个解：", ++count);
for (int i = 1; i <= n; i++)
printf("(%d,%d)", i, q[i]);
printf("\n");
}
bool place(int i, int j) //测试（i,j）位置能否摆放皇后
{
if (i == 1)return true;
int k = 1;
while (k < i)
{
if ((q[k] == j) || (abs(q[k] - j) == abs(i - k)))
return false;
k++;
}
return true;
}
void queen(int i, int n) //放置 1~i 的皇后
{
if (i > n) { //所有皇后放置结束
dispasolution(n);
}
else
{
for (int j = 1; j <= n; j++) { //在第i行上试探每一个列j
if (place(i, j)) //在第i行上找到一个合适位置（i，j）
{
q[i] = j;
queen(i + 1, n);
}
}
}
}
int main() {
int n; //n为存放实际皇后的个数
printf(" 皇后问题（n<20）n=");
scanf("%d", &n);
if (n > 20) {
printf("n值太大，不能求解\n");
}
else
{
printf("%d皇后问题求解如下：\n", n);
queen(1, n); //放置 1 ~ n 的皇后
}
return 0;
}12、递归消除的方法
（1）用循环结构代替
（2）用栈消除递归
结语
第二章递归算法设计技术结束，下一章——第三章分治法
🌌点击下方个人名片，交流会更方便哦~（欢迎到博主主页加入我们的 CodeCrafters联盟一起交流学习）↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
