递归及递归算法.ppt

递归的实现及应用
:一个直接调用自己或通过一系列的调用语句间接的调用自己的函数,称做递归.
分为直接递归和间接递归
在递归函数的递归调用过程中,当有多个函数构成嵌套调用时,函数之间的信息传递和控制转移必须通过栈来实现。
:
其一:数学函数采用递归定义如:阶乘函数
Fact(n)= 1 n=0
n · Fact(n-1) n>0
其二:有的数据结构,如二叉树,广义表,图的遍历,查找算法等由于结构本身固有的递归特性,其操作可以递归的描述;
其三:没有明显的递归结构但用递归求解更简单,如Hanoi塔问题求解.
3、递归程序的一般形式
Status function (参数表); long fact(int n)
{ {
If 数据为递归出口 if (n <=0)
简单操作; return(1);
else{ 简单操作 else
function(实参表); return n × fact(n-1) ;
简单操作;
}
} }
4、递归程序的编写
首先,要确定本程序的功能描述(定义)及各变量的含义,确定递归出口及描述,然后分别进行以下两方面的设计:
(1)写出程序中与递归出口相对应的操作;
(2)写出在非递归出口处所对应的操作:先假设在数据(参数及全局变量)接近递归出口时,程序功能正确,可通过适当调用这些功能来实现本程序的功能,这些操作的描述便构成了这部分的程序。
(3)通过条件语句将上述两部分操作连接起来,便得到整个程序。
printf(T->data) ;
InOrderTraverse ( T->lchild ) ;
InOrderTraverse ( T->rchild ) ;
If (T) {
}
void InOrderTraverse ( BiTree T )
{
}
//中序遍历
算法 中序遍历递归算法(或其他遍历算法)
树的递归算法思路拓展
设计算法
由此导出许多实用的算法:如求二叉树的高度, 度为0,1,2的结点数,二叉树的相似、复制等。
表达式求值
例1 .设计算法:统计一棵二叉树中所有叶结点的数目及非叶结点的数目。
.void Count(BiTree bt,int *n0,*n) //统计二叉树bt上叶子结点数n0和非叶子结点数n
{if(bt)
{if (bt->lchild==null && bt->rchild==null) *n0++;//叶子结点
else *n++; //非叶结点
Count(bt->lchild,&n0,&n);
Count(bt->rchild,&n0,&n);
} }//结束 Count
例2试写出复制一棵二叉树的算法。二叉树采用标准链接结构。
.BiTree Copy(BiTree t)//复制二叉树t
{BiTree bt;
if (t==null) bt=null;
else{bt=(BiTree)malloc(sizeof(BiNode));
bt->data=t->data;
bt->lchild=Copy(t->lchild);
bt->rchild=Copy(t->rchild);
}
return(bt); }//结束Copy
例3 :用孩子兄弟链表作为树的存储结构,请编写求树的深度的算法。
分析:一棵树的深度定义为:若树为空,则深度为0,否则树的深度为所有子树深度的最大值加1。
A
D
C
B
A
D
C
B
结点类型定义为:type struct node {char data;
struct node *fristchild nextbrother
}Csnode
fristchild 指向结点的第一个孩子结点,nextbrother指向结点的右邻兄弟结点。
由孩子兄弟链表表示的树,求高度的递归模型是:若树为空,高度为零;若第一孩子为空,高度为1和兄弟子树的高度的大者;否则,高度为第一孩子树高度加1和兄弟子树高度的大者。其非递归算法使用队列,逐层遍历树,取得树的高度。
int Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度
{int hc,hs;
if (bt==null) return (0);
else if (!bt->firstchild) return (1+height(bt->nextsibling);//孩子空,查兄弟的深度
else // 结点既有第一孩子又有兄弟,高度取孩子高度+1和兄弟子树高度的大者
{hc=height(bt->firstchild); //第一孩子树高
hs=height(bt->nextsibling);//兄弟