递归算法设计技术

递归的定义

在定义一个过程或函数时出现调用本过程或本函数的成分。称之为递归。
若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归。
任何间接递归都可以等价地转换为直接递归。
如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。

需要满足的条件

一般来说，能够用递归解决地问题应该满足以下三个条件：

1. 需要求解的问题可以转换为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同
2. 递归调用的次数必须是有限的
3. 必须有结束递归的条件来终止递归

何时使用递归

1. 定义是递归的，例如求n！和Fibonacci数列
2. 数据结构是递归的，例如单链表就是一种递归数据结构

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

3. 问题的求解方法是递归的，例如Hanoi塔问题的求解

递归模型

一般的，一个递归模型是由递归出口和递归体两部分组成，前者确定递归到何时结束，后者确定递归求解时的递推关系。

递归算法的执行过程

每递归调用一次，就需进栈一次，最多的进栈元素个数称为递归深度，当n越大，递归深度越深，开辟的栈空间也越大。
每当遇到递归出口或完成本次执行时，需退栈一次，并恢复参量值，当全部执行完毕时，栈应为空。
在递归函数执行时，形参会随着递归调用发生变化，但每次调用后会恢复调用前的形参，将递归函数的非引用型形参的取值称为状态。
递归函数的引用型形参在执行后会回传给实参，有时类似全局变量，不作为状态的一部分，在调用过程中状态会发生变化，而一次调用后会自动恢复为调用前的状态。

递归算法设计

数学归纳法是递归的基础。
获取递归模型的步骤如下：

1. 对原问题f(sn)进行分析，抽象出合理的“小问题”f(sn-1)（与数学归纳法中假设n=k-1时等式成立相似）；
2. 假设f(sn-1)是可解的，在此基础上确定f(sn)的解，即给出f(sn)与f(sn-1)之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）；
3. 确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口（与数学归纳法中求证n=1或n=0时等式成立相似）。

递归数据结构及其递归算法设计

单链表的递归算法设计

在设计不带头结点的单链表的递归算法时：
设求解以L为首结点指针的整个单链表的某功能为“大问题”。
而求解除首结点外余下结点构成的单链表（由L->next标识，而该运算为递归运算）的相同功能为“小问题”。
由大小问题之间的解关系得到递归体。
再考虑特殊情况，通常是单链表为空或者只有一个结点时，这时很容易求解，从而得到递归出口。
例：有一个不带头结点的单链表L，设计一个算法释放其中所有结点。
解：设L={a1，a2，…，an}，f(L)的功能是释放a1～an的所有结点，则f(L->next)的功能是释放a2～an的所有结点，前者是“大问题”，后者是“小问题”。
假设f(L->next)是已实现，则f(L)就可以采用先调用f(L->next)，然后释放L所指结点来求解。
对应的递归模型如下：

void DestroyList(LinkNode *&L)
//释放单链表L中所有结点
{  if (L!=NULL)
   {	DestroyList(L->next);
	free(L);
   }
}

二叉树的递归算法设计

二叉树是一种典型的递归数据结构，当一棵二叉树采用二叉链b存储时：
设求解以b为根结点的整个二叉树的某功能为“大问题”。
求解其左、右子树的相同功能为“小问题”。
由大小问题之间的解关系得到递归体。
再考虑特殊情况，通常是二叉树为空或者只有一个结点时，这时很容易求解，从而得到递归出口。
例：对于含n（n>0）个结点的二叉树，所有结点值为int类型，设计一个算法由其先序序列a和中序序列b创建对应的二叉链存储结构。

BTNode *CreateBTree(ElemType a[],ElemType b[],int n) 
//由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链存储结构bt
{   int k;
    if (n<=0) return NULL;
    ElemType root=a[0];				//根结点值
    BTNode *bt=(BTNode *)malloc(sizeof(BTNode));
    bt->data=root;
    for (k=0;k<n;k++)			//在b中查找b[k]=root的根结点
       if (b[k]==root)
	    break;
    bt->lchild=CreateBTree(a+1,b,k);			//递归创建左子树
    bt->rchild=CreateBTree(a+k+1,b+k+1,n-k-1);	//递归创建右子树
    return bt;
}

基于归纳思想的递归算法设计

基于归纳思想的递归算法设计通常不像基于递归数据结构的递归算法设计那样直观，需要通过对求解问题的深入分析，提炼出求解过程中的相似性而不是数据结构的相似性，这就增加了算法设计的难度。
但现实世界中的许多问题的求解都隐含这种相似性，并体现计算思维的特性。
例：设计一个递归算法，输出一个大于零的十进制数n的各数字位，如n=123，输出各数字位为123。
解：设n为m位十进制数am-1am-2…a1a0（m>0），则有:n%10=a0，n/10=am-1am-2…a1。
设f(n)的功能是输出十进制数n的各数字位，则f(n/10)的功能是输出除a0（即n%10）外的各数字位，前者是“大问题”，后者是“小问题”。

void digits(int n)
{  if (n!=0)
   {	digits(n/10);
	printf("%d"，n%10);
   }
}