递归效率比较低,能用循环尽量用循环

Sierpinski三角形就是递归实现的

斐波那契数列的递归实现

• 如果兔子在出生两个月后就有繁殖能力,一堆兔子每个月能生出一对小兔子来.假设所有兔子都不会死去,那么一年后可以繁殖多少兔子呢?

• 月数-兔子个数

所经过的月数 1   2   3   4   5   6   7   8   9   10   11   12

兔子的总对数 1   1   2   3   5   8   13  21  34  55   89   144

• 我们可以用数学函数来定义

       0,当 n=0
F(n) = 1, 当n = 1
       F(n-1)+F(n-2),当n>1

• 递归实现

int Fib(int i)
{
    if(i<2)
        return i == 0?0:1;
    return Fib(i-1) + Fib(i-2);
}

• 递归树

递归定义

• 在高级语言中,函数调用自己和调用其他函数并没有本质的不同.我们把一个一直调用自己或通过一系列的调用语句简介的调用自己的函数,称作递归函数

• 写递归程序最怕的就是陷入永不结束的无穷递归中.切记每个递归定义必须至少有一个条件,当满足这个条件时递归不再进行,即函数不再调用自身而返回

• 大量的递归会建立函数的副本,会消耗大量的时间和内存,而迭代则不需要

• 递归函数分为调用和回退阶段,递归的回退顺序是它调用顺序的逆序

分治思想

• 当一个问题规模较大且不易求解的时候,就可以考虑将问题分成几个小的模块,逐一求解

• 分治思想和递归算是亲兄弟关系,因为采用分支思想处理问题,其各个小模块通常具有与大问题相同的结构,这种特性也使递归技术有了用武之地.

折半查找算的的递归实现

• 折半查找是一种常用的查找方法,该方法通过不断 缩小一半查找的范围,知道达到目的,所以效率比较高

汉诺塔

• 一位法国数学家曾经编写过一个印度的古老传说:在世界中心拿勒斯的圣庙里,一块黄铜板上插着三根宝石针.印度的主神梵天在创造世界的时候,在其中一根针上从下到上的穿4好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上小片必须在大片上面.

• 我们可以做这样的考虑

  • 先将前63个盘子移动到Y上,确保大盘在小盘下

  • 再将最底下的第64个盘子移动到Z上

  • 最后将Y上的63个盘子移动到Z上

• 在游戏中,我们发现由于每次只能移动一个圆盘,所以在移动的过程中显然要借助另外一根针才行

• 也就是说第1步将1~63个盘子借助Z移动到Y上,第3步将Y针上的63个盘子借助X移动到Z针上.那么我们把所有新的思路聚集为一下两个问题:

  • 问题一:将X上的63个盘子借助Z移动到Y上

  • 问题二:将Y上的63个盘子借助X移动到Z上

• 解决上述两个问题依然用相同的方法:

  • 问题一的圆盘移动步骤为

    • 先将62个盘子移动到Z上,确保大盘在小盘下

    • 再将底下的第36个盘子移动到Y上

    • 最后将Z上的62个盘子移动到Y上

  • 问题二的圆盘移动步骤为:

    • 先将前62个盘子移动到X上,确保大盘在小盘下

    • 再将最底下的第63个盘子移动到Z上

    • 最后将X上的62个盘子移动到Y上

#include <stdio.h>

//将n个盘子从x借助y移动到x
void move(int n,char x,char y,char z)
{
    if(1==n)
    {
        printf("%c-->%c\n",x,z);
    }
    else
    {
        //将n-1个盘子从x借助z移动到y上
        move(n-1,x,z,y);
        //将第n个盘子从x移动到z上
        printf("%c-->%c\n",x,z);
        //将n-1个盘子从y借助x移动到z上
        move(n-1,y,x,z);
    }
}

int main()
{
    int n;
    printf("请输入汉诺塔的层数:");
    scanf("%d",&n);
    printf("移动步骤如下:\n");
    move(n,'X','Y','Z');
    return 0;
}

八皇后问题

• 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题(先用递归算法求解)

• 该问题由十九世纪著名的数学家搞死18550年提出:

• 在8x8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行,同一列或同一斜线上,问有多少种摆法

#include <stdio.h>

int count = 0;

int noDanger(int row,int j,int (*chess)[8])
{
    int i,k,flag1=0,flag2=0,flag3=0,flag4=0,flag5=0;

    //判断列方向
    for(i=0;i<8;i++)
    {
        if(*(*(chess+i)+j)!=0)
        {
            flag1 = 1;
            break;
        }
    }

    //判断左上方
    for(i=row,k=j;i>=0&&k>=0;i--,k--)
    {
        if(*(*(chess+i)+k)!=0)
        {
            flag2 = 1;
            break;
        }
    }

    //判断右下方
    for(i=row,k=j;i<8&&k<8;i++,k++)
    {
        if(*(*(chess+i)+k)!=0)
        {
            flag3 = 1;
            break;
        }
    }

    //判断右上方
    for(i=row,k=j;i>=0&&k<8;i--,k++)
    {
        if(*(*(chess+i)+k)!=0)
        {
            flag4 = 1;
            break;
        }
    }

    //判断左下方
    for(i=row,k=j;i<0&&k>=0;i++,k--)
    {
        if(*(*(chess+i)+k)!=0)
        {
            flag5 = 1;
            break;
        }
    }

    if(flag1||flag2||flag3||flag4||flag5)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

//参数row表示起始行
//参数n表示列数
//参数(*chess)[8]表示指向棋盘每一行的指针
void EightQueen(int row,int n,int (*chess)[8])
{
    int chess2[8][8],i,j;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            chess2[i][j] = chess[i][j];
        }
    }

    if(8==row)
    {
        printf("第%d种\n",++count);
        for(i=0;i<8;i++)
        {
            for(j=0;j<8;j++)
            {
                printf("%d ",*(*(chess2+i)+j));
            }
            printf("\n");
        }
        printf("\n");
    }
    else
    {
        //如果有危险继续往下
        for(j=0;j<n;j++)
        {
            //判断这个位置是否有危险
            if(noDanger(row,j,chess))
            {
                for(i=0;i<8;i++)
                {
                    *(*(chess2+row)+i) = 0;
                }
                *(*(chess2+row)+j) = 1;
                EightQueen(row+1,n,chess2);
            }
        }
    }
}

int main()
{
    int chess[8][8],i,j;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            chess[i][j] = 0;
        }
    }
    EightQueen(0,8,chess);
    printf("总共有%d种方式!\n",count);
    return 0;
}