递归的概念

递归算法:直接或间接调用自身的算法称为递归算法。

适合递归算法的问题：

递归函数：用函数自身给出定义的函数。

递归结构：二叉树。

可以转化为递归算法解决。

例1：求阶乘（递归函数）

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

例2：求二叉树叶子结点数（递归结构）

void BinaryCount()
{
    typedef struct node
    {
        char data;
        struct node *lchild,*rchild;
    }BNode,*BiTree;
    int LeafCount(BiTree T)
    {
        if(!T)    
            return 0;
        else if(T->lchild==NULL&&T->rchild==NULL)
            return 1;
        else
            return LeafCount(T->lchild)+LeafCount(T->rchild);
        
    }
}

递归算法设计步骤：

1.分析问题，寻找递归关系

找出大规模问题和小规模问题的关系，这样通过递归使问题的规模逐渐变小

2.设置边界，控制递归

找出停止条件，即算法可解的最小规模问题

3.设计函数，确定参数

和其他算法一样设计函数体中的 *** 作及相关参数

递归解决实际问题-汉诺塔问题

Hanoi问题起源于一个类似的传说故事，在Hanoi这个地方有一个寺庙，这里有3根柱子和64个大小不同的金碟子。每个碟子有一个孔可以穿过。所有的碟子都放在第一个柱子上，而且按照从大到小碟子的大小依次增大的顺序摆设。现在，假定寺庙里的僧侣要移动这些碟子，将它们从柱子a移动到柱子b上。不过移动的规则如下：

1.每次只能从一个柱子的最上面移动一个碟子到另外一个柱子上。

2.不能将大碟子放在小碟子的上面。

按照前面这个规则，我们该怎么去移动这些碟子呢？

解决方法：

1.递归关系：将n-1个碟子借助b移到c，将最后一个移到b，再将n-1个碟子借助a从c移到b

2.终止条件：n=0，没有碟子需要移动了

3.确定参数：n，a，b，c

Hanoi的具体实现

void hanoi(int n,char a,char b,char c) //将n个碟子从a移到b
{
    if(n==0)
    return;
    else
    {
        hanoi(n-1,a,c,b); //将n-1个碟子借助b移动到c
        move(a,b);    //将最后一个碟子移动到b
        hanoi(n-1,c,b,a);  //将n-1个碟子借助a移动到b
    }
}

递归解决实际问题-排列问题

问题描述：设R={r1,r2,...,rn}是要进行排列的n个元素，求R的全排列Perm(R)。

问题分析：设(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。

解决方法：

1.递归关系

perm(R)由（r1)perm(R1),(r2)perm(R2),...,(rn)perm(Rn)构成，其中Ri=R-{ri}

2.终止条件

n=1时，Perm(R)=r,r是R中的唯一元素。

3.参数设置：

待排序数组List，开始下标k，终止下标m。

实现思想：将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。

示例:

当n=3，并且E={a，b，c}，对集合E中元素进行全排列，则

perm(E)=a.perm({b,c})+b.perm({a,c})+c.perm({a,b})

prem({b,c})=b.prem(c)+c.prem(b)

a.perm({b,c})=ab.prem(c)+ac.prem(b)=ab.c+ac.b=(abc,acb)

同理可得b，c。

代码：

void Perm(int list[],int k,int m)
{
    if(k==m)//到达结尾
    {
        for(int i=0;i

#include
using namespace std;
const int N=10;
int a[N];
void perm(int a[],int k,int m)
{
    if(k==m)
    {
        for(int i=0;in;
    for(int i=0;i