数据结构和算法：递归

06_递归

标签（空格分隔）： 数据结构和算法

---

• 斐波那契数列的迭代实现
• 斐波那契数列的递归实现
• 递归定义
• 实例分析
• 分治思想
• 汉诺塔
• 八皇后问题

6.1 斐波那契数列的迭代实现

#include <stdio.h>

int main()
{
    int i;
    int a[40];

    a[0] = 0;
    a[1] = 1;
    printf("%d %d ", a[0], a[1] );

    for( i=2; i<40; i++ )
    {
        a[i] = a[i-1] + a[i-2];
        printf("%d ", a[i]);
    }

    return 0;
}

6.2 斐波那契数列的递归实现

#include <stdio.h>

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

int main()
{
    int i = 0;
    printf("请输入需要打印的斐波那契列数： "); 
    scanf("%d", &i);
    printf("%d ", Fib(i)); 

    return 0；
} 

6.3 递归定义

• 在高级语言中，函数调用自己和调用其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
• 每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数调用不再自身而是返回。
• 对比两种实现斐波那契数列的代码，迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。
• 大量的递归调用会建立函数的副本，会消耗大量的时间和内存，而迭代则不需要此种付出。
• 递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。

例 计算 n 的阶乘 n!

#include <stdio.h>

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

int main()
{
    int n = 0;
    printf("请输入需要计算阶乘的数字 n ： ");
    scanf("%d", &n);
    printf("%d\n", factorial(n));

    return 0; 
}

6.4 实例分析

例 编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。

#include <stdio.h>

void print()
{
    char a;
    scanf("%c", &a);
    if( a != '#' )
        print();
    if( a != '#' )
        printf("%c", a);
}

int main()
{
    printf("请输入字符串，并以 # 作为结束标志！\n");    
    print();

    return 0;
}

6.5 分治思想

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

例 折半查找法的迭代实现

//折半查找法的迭代实现 1
#include <stdio.h>
#include <stdlib.h>

int bin_serach(int str[], int n, int key)
{
    int low, mid, high;

    low = 0;
    high = n - 1;

    while(low <= high)
    {
        mid = (low + high)/2;
        if (str[mid] == key)
        {
            return mid;
        }
        else if (str[mid] < key)
        {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return 0;
}

int main()
{
    const int SIZE = 10;
    int c;
    int i = 0;
    int str[SIZE];

    printf("请输入 %d 个数字作为初始数组：\n", SIZE);

    while( i < SIZE )
    {
        scanf("%d", &c);
        str[i] = c;
        i++;
    }

    int n, addr;

    printf("\n请输入要查询的数字：");
    scanf("%d", &n);

    addr = bin_serach(str, SIZE, n);

    if (-1 != addr)
    {
        printf("查找成功，查询数字 %d 所在的位置是： %d\n", n, addr+1);
    }
    else
    {
        printf("查找失败!");
    }

    return 0;
}

//折半查找法的迭代实现 2
#include <stdio.h>
#include <stdlib.h>

int getAddr(int str[], int key, int low, int high)
{
    if (low > high)
        return -1;

    int mid = (low + high) / 2;

    if (key == str[mid])
        return mid;

    if (str[mid] < key)
    {
        low = mid + 1;
    }
    else if (str[mid] > key)
    {
        high = mid - 1;
    }

    return getAddr(str, key, low, high);
}

int main()
{
    const int SIZE = 10;
    int c;
    int i = 0;
    int str[SIZE];

    printf("请输入 %d 个数字作为初始数组：\n", SIZE);

    while( i < SIZE )
    {
        scanf("%d", &c);
        str[i] = c;
        i++;
    }

    int n, addr;

    printf("\n请输入要查询的数字：");
    scanf("%d", &n);

    addr = getAddr(str, n, 0, SIZE);

    if (-1 != addr)
    {
        printf("查找成功，查询数字 %d 所在的位置是： %d\n", n, addr+1);
    }
    else
    {
        printf("查找失败!");
    }

    return 0;
}

例 折半查找法的递归实现

//折半查找法的递归实现

#include <stdio.h>

typedef int ElemType;

int half_search(ElemType *str, int low, int high, ElemType n)
{
    int mid = (low + high)/2;

    if(low > high)
        return -1;

    if( str[mid] == n )
    {
        return mid;
    }
    else if( str[mid] < n )
    {
        return half_search(str, mid+1, high, n);
    }
    else
    {
        return half_search(str, low, mid-1, n);
    }
}

int main()
{
    const int SIZE = 10;
    ElemType str[SIZE];
    int c;
    int i = 0;

    printf("请输入 %d 个数字作为初始数组：\n", SIZE);

    while( i < SIZE )
    {
        scanf("%d", &c);
        str[i] = c;
        i++;
    }

    printf("\n"); 
    for( i=0; i<SIZE; i++ )
    {
        printf("%d ", str[i]);        
    }

    int n;
    printf("\n请输入要查询的数字：");
    scanf("%d", &n);

    int addr = half_search(str, 0, SIZE, n);

    if (-1 != addr)
    {
        printf("查找成功，查询数字 %d 所在的位置是： %d\n", n, addr+1);
    }
    else
    {
        printf("查找失败!");
    }

    return 0;
}

6.6 汉诺塔

#include <stdio.h>

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

int main()
{
    int n;

    printf("请输入汉诺塔的层数： ");
    scanf("%d", &n);
    printf("移动的步骤如下：\n");
    move(n, 'x', 'y', 'z');

    return 0;
}

6.7 八皇后问题

#include <stdio.h>

int count = 0;

int notDanger( 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<8 && 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+1);
        for( i=0; i<8; i++ )
        {
            for( j=0; j<8; j++ )
            {
                printf("%d ", *(*(chess2+i)+j));
            }
            printf("\n");
        }
        printf("\n");
        count++;
    }
    else
    {
        for( j=0; j<n; j++ )
        {
            if( notDanger(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;
}