快速解析 递归与分治思想

分治思想：      斐波那契数列的迭代实现：（兔子繁殖问题）   #include <stdio.h>int main(){    int i;    int a[40];    a[0] = 0;    a[1] = 1;    for(i = 2; i < 40; i++)    {        a[i] = a[i - 1] + a[i - 2];        printf("%d", a[i]);    }    return 0;}      斐波那契数列的递归实现：（兔子繁殖问题）   int Fib(int i){    if(i < 2)        return i == 0 ? 0 : 1;    return Fib(i - 1) + Fib(i - 2);}      对比以上两个代码发现 迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构 使用递归使程序的结构更清晰，更简洁，更容易让人理解，从而减少读懂代码的时间大量的递归调用会减少函数的副本，会消耗大量的时间和内存，而迭代则不需要此种付出递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序        折半查找算法的递归实现：          折半查找法是一种常用的查找方法，该方法通过不断缩小一半查找的范围，知道达到目的。      汉诺塔问题实现：   //将 n 个盘子从 x 借助 y 移动到 zvoid 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);    move(n, 'X','Y', 'Z');    return 0;}       八皇后问题：          在 8 X 8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列或同一斜线上，共用多少种摆法？   #include <stdio.h>int count = 0;int notdanger(int row, int j, int (*chess)[8]){    int i, flag1, flag2, flag3, flag4, flag5;    //判断列方向    for(i = 0; i < 8; i++)    {        if(*(*(chess + i) + j) != 0)        {         flag1 = 1;          break;        }    }    //判断左上方    for(i = row, k = j; i < 8 && k < 8; 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 种"， 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) + i) = 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; }