您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

递归算法

  1. 递归的定义

直接递归:在定义一个过程或函数时出现调用过程或本函数的成分。

间接递归:过程或函数p调用过程或函数q,而q又调用p。

尾递归:一个递归过程或递归函数中递归调用语句是最后一条执行语句。

例:设计求n!的递归算法:

#include <stdio.h>
int Fac(int n);
int main(){
	int n;
	printf("请输入n的值:  ");
	scanf("%d",&n);
	printf("%d\n",n);
	printf("Fac=%d \n",Fac(n));
	return 0;
}

int Fac(int n){
	if(n<=0){
		return -1;
	}else if(1==n){
		return 1;
	}else{
		return n*Fac(n-1);
	}
}

运行结果:
运行结果

2.递归的类型

定义是递归的

例如求n!和Fibonacci数列等。

数据结构是递归的

例如单链表:

typedef struct LNnode{
ElemType data;
struct LNode * next;
}LinkList;

问题的求解方法是递归的:

已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.

3.递归模型

f(n)=1               n=1     //递归出口  求值过程
f(n)=n*f(n-1)  n>1         //递归体   分解过程

例如:用递归算法求一个整数数组a[]中的最大元素。

递归模型:
f(a,i)=a[0]                        //i=1
f(a,i)=MAX{f(a,i-1),a[i-1]}       //i>1

对应递归算法:

int fmax(int a[],int i){
 if(i==1)
 {
      return 0;
 }else{
      return (fmax(a,i-1),a[i-1]);
}
}

4.假设二叉树采用二叉链存储结构,设计一个递归算法输出从根结点到值为x的结点的路径,假设二叉树中所有结点不同,且均为单个字符:

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100

typedef char ElemType;

typedef struct node{
	ElemType data;
	struct node * lchild; //定义了两个struct node * 类型的变量 lchild返回的是node类型的结构体
	struct node * rchild;  //由于子节点和父节点的类型一样,故运用了struct node
	//https://zhidao.baidu.com/question/266853329788770565.html  讲述结构体指针和结构体中的指针较为清楚
}BTNode;

void CreateBTNode(BTNode * &b,char * str){  //*a的“a”是指针变量,其内容是地址,*&a的“a”是变量a或a数组的首字节,其内容是数据。 
	BTNode * St[MaxSize],* p=NULL;  //*&a[1] = a[1]  &a[1]表示a[1]的地址,*后面跟地址表示地址里的值,所以*&a[1] = a[1]。可以理解为,*和&在C语言里互为逆运算。      由于[ ] 的优先级高于* 所以a先和 [ ]结合,他还是一个数组,数组中的元素才是char *
	int top=-1,k,j=0; //等于:int top=-1;int k; int j=0;
	char ch;
	b=NULL;       //建立的二叉树初始值为空
	ch=str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		case'(':top++;St[top]=p;k=1;break;
		case')':top--;break;
		case',':k=2;break;
		default:p=(BTNode *)malloc(sizeof(BTNode));  //sizeof返回一个对象或者类型所占的内存字节数。
			p->data=ch;p->lchild=p->rchild=NULL;
			if(b==NULL)
				b=p;
			else
			{
				switch(k)
				{
					case 1:St[top]->lchild=p;break;//case 1 表示switch()匹配的是整型;  case '1' 匹配的是字符型
					case 2:St[top]->rchild=p;break;
				
				}
			
			}
		}
	
	j++;
	ch=str[j];
	}

}




void DisBTNode(BTNode * b)
{
	if(b!=NULL)
	{
		printf("%c",b->data);
		if(b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			DisBTNode(b->lchild);
			if(b->rchild !=NULL)
				printf(",");
			DisBTNode(b->rchild);
			printf(")");
		
		}
	
	}

}



void DestroyBTNode(BTNode * &b){
	if(b!=NULL){
		DestroyBTNode(b->lchild);
		DestroyBTNode(b->rchild);
		free(b);
	}

}

bool Ancestor(BTNode * b,char x,char path[],int &d)    
{
	if(b==NULL)                   //二叉树b若不存在,返回false
		return false;                  
	if(b->data==x)                 //若二叉树b为根路径
	{ 
	 	d++;                        //依次查找通往G的路径
	 	path[d]=x;                   //分支路径为x
		return true;
	
	}else if(Ancestor(b->lchild,x,path,d)||Ancestor(b->rchild,x,path,d))  //若二叉树b是分支路径
	{
		d++;
		path[d]=b->data;    //查找二叉树的路径名               
		return true;
	}
}


void main(){
	BTNode * b;
	char x='G';                //查找二叉树为G的数据
	char path[MaxSize];         //定义二叉树组路径空间大小
	int d=-1,i;
	CreateBTNode(b,"A(B(D(,G)),C(E,F))");   //递归调用。创建二叉树b A(B(D(,G)),C(E,F))
	printf("二叉树b:");
	DisBTNode(b);                           //输出创建的二叉树
	printf("\n");
	if(Ancestor(b,x,path,d))                //查找到G的路径
	{
		printf("在b中找到值为%c的结点\n",x);
		printf("从根结点到%c的路径:",x);
		for(i=d;i>=0;i--)
			printf("%c",path[i]);
		printf("\n");
		
		}
		else printf("在b中没有找到值为%c的结点\n",x);
		printf("销毁树b\n");
		DestroyBTNode(b);                //递归调用 销毁二叉树
}

在这里插入图片描述
5. Horner(霍纳)规则;
解决多项式问题:A(x) = a[n]x^n + a[n-1]x^(n-1) + … + a[1]x^1 + a[0]x^0
本文采用递归思想,C++语言:


#include <stdio.h>
int horner(int *a,int n,int x);
int main()
{	
	int a[]={0,1,2,3,4,5};   //多项式的系数  从左往右依次系数指数渐增
	printf("多项式ax=%d\n",horner(a,5,3));  //输出指数为3的多项式的值
	return 0;
}

int horner(int *a,int n,int x){                     //霍纳函数
	int ax=a[n]*x+a[n-1];                           // ax=a[5]*x+a[4]
	for(int i=n-2;i>=0;i--)                         //i=3时;  ax={a[5]*x+a[4]}*x+a[3]
	{                                               //i=2时;  ax={a[5]*x^2+a[4]*x+a[3]}*x+a[2]
		ax=ax*x+a[i];                               //i=1时;  ax={a[5]*x^3+a[4]*x^2+a[3]*x+a[2]}*x+a[1]                           
	}                                               //i=0时;  ax={a[5]*x^4+a[4]*x^3+a[3]*x^2+a[2]*x+a[1]}*x+a[0]
		return ax;                                  //i=0时;  ax=a[5]*x^5+a[4]*x^4+a[3]*x^3+a[2]*x^2+a[1]*x+a[0]
}

运行结果:
在这里插入图片描述
6.递归算法设计思想 (简单选择排序和冒泡排序)

问题描述:对于给定的含有n个元素的数组a,对其按元素值递增排序。

//简单选择排序

#include <stdio.h>

void disp(int a[],int n)     //遍历输出数组
{
	int i;
	for(i=0;i<n;i++)
		printf("%d",a[i]);
	printf("\n");
}


void SelectSort(int a[],int n,int i) 
{
	int k,j,temp;
	if(i==n-1)                     //i是首数据,n-1是尾部数据,如果数组只有一个元素则直接返回
	{
		return;
	}else {
		k=i;                         
		for(j=k+1;j<n;j++)         //k记录a[i...n-1]中最小元素的下标
			if(a[j]<a[k])          //将i与i+1,i+2^…i+n-1比较
				k=j;               //如果最小值为K+1,则将最小值下标k改为k+1
			if(k!=i){              //如果k不等于i
				temp=a[i];         //交换k与i的值
				a[i]=a[k];
				a[k]=temp;
			}
			SelectSort(a,n,i+1);    //递归执行i+1...n;i+2...n;i+n-2,n-1;  
	}
}



void main()
{
	int n=10;
	int a[]={1,0,5,6,3,8,7,4,9,2};
	printf("排序前:");
	disp(a,n);
	SelectSort(a,n,0);     //数组默认从0开始
	printf("排序后:");
	disp(a,n);
}

在这里插入图片描述



//冒泡排序

#include <stdio.h>

void disp(int a[],int n)     //遍历输出数组
{
	int i;
	for(i=0;i<n;i++)
		printf("%d",a[i]);
	printf("\n");
}


void BubbleSort(int a[],int n,int i) 
{
	int j,temp;
	bool exchange;
	if(i==n-1)                     //i是首数据,n-1是尾部数据,如果数组只有一个元素则直接返回
	{
		return;
	}else {
		exchange=false;
		for(j=n-1;j>i;j--)         
			if(a[j]<a[j-1])     //a[]中的元素两两相互比较
			{          
				temp=a[j];         
			     a[j]=a[j-1];
				 a[j-1]=temp;
				 exchange=true;
			}
			if(exchange=false){              
				return;
			}
			else
				BubbleSort(a,n,i+1);      
	}
}



void main()
{
	int n=10;
	int a[]={1,0,5,6,3,8,7,4,9,2};
	printf("排序前:");
	disp(a,n);
	BubbleSort(a,n,0);     //数组默认从0开始
	printf("排序后:");
	disp(a,n);
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进