五、遞歸與常見問題

一、函數調用時的棧

函數調用時的棧
?程序中的“函數調用?！笔菞祿Y構的一種應用
?函數調用棧一般是從高地址向低地址增長的
??棧底為內存的高地址處
??棧頂為內存的低地址處
?函數調用棧中存儲的數據為活動記錄

程序中的棧
?在不斷的壓棧過程中造成?？臻g耗盡而產生棧溢出
?棧溢出常由于函數遞歸過深或局部數組過大造成

二、遞歸的應用

?遞歸是一種數學上分而自治的思想
?遞歸將大型復雜問題轉化為與原問題相同但規(guī)模較小的問題進行處理
?遞歸需要有邊界條件
??當邊界條件不滿足時，遞歸繼續(xù)進行
??當邊界條件滿足時，遞歸停止
斐波拉切數列
斐波納契數列以如下被以遞推的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*)

int fibolac(int n)
{
    if((1 == n)||(2 == n))
    {
        return 1;   
    }
    else
    {
        return fibolac(n-1)+fibolac(n-2);
    }

}

字符串長度
求取字符串長度可使用遞歸的方式來求取

int string_len(const char* p)
{
    if(p == NULL)
    {
        return -1;
    }
    else if(*p == '\0')
    {
        return 0; 
    }
    else
    {
        return string_len(p+1) + 1; 
    }
}

全排列
假設集合是{a,b,c},那么這個集合中元素的全部排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}，顯然，給定n個元素共同擁有n!種不同的排列，假設給定集合是{a,b,c,d}，能夠用以下給出的簡單算法產生其全部排列，即集合(a,b,c,d)的全部排列有以下的排列組成
?以a開頭后面跟著(b,c,d)的排列
?以b開頭后面跟著(a,c,d)的排列
?以c開頭后面跟著(a,b,d)的排列
?以d開頭后面跟著(a,b,c)的排列

int permutation(char s[],int b,int e)
{
    if((b>=0) && (b<=e))
    {
        if(b == e)
        {
            printf("%s\n",s);
        }
        else
        {
            int i = 0;
            for(i = b; i<=e; i++)
            {
                if(isswap(s,b,i))           //去重的全排列就是從第一個數字起每個數分別與它后面非重復出現(xiàn)的數字交換
                {
                    char c = s[b];          //交換位置
                    s[b] = s[i];
                    s[i] = c;
                    permutation(s,b+1,e);

                    c = s[b];              //交換位置
                    s[b] = s[i];
                    s[i] = c;
                }
            }
        }
    }
} 

漢諾塔問題
該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤。游戲的目標：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

/*
   n:需要移動的盤子數量
   a:起始位置
   b:需要借助的柱子 
   c:需要移動到的柱子 
*/
int hannoi(int n, char a, char b, char c)
{
    if(1 == n)
    {
        printf("%c-->%c\n",a,c);
    }
    else
    {
        hannoi(n-1, a, c, b);
        printf("%c-->%c\n",a,c);
        hannoi(n-1, b, a, c);
    }
    return 0;
} 

八皇后問題
八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

#define N 8

typedef struct _tag_Pos
{
    int ios;
    int jos;
} Pos;                     //位置檢查 

static char board[N+2][N+2];
static Pos pos[] = { {-1, -1}, {-1, 0}, {-1, 1} };     //偏移位置 
static int count = 0;                                  //符合要求的個數 

void display()
{
    int i = 0;
    int j = 1;

    for(i=0; i<N+2; i++)
    {
        for(j=0; j<N+2; j++)
        {
            printf("%c", board[i][j]);
        }

        printf("\n");
    }
}

void init_queen()
{
    int i,j;
    for(i=0;i<N+2;i++)
    {
        board[0][i] = '#';
        board[i][0] = '#';
        board[N+1][i] = '#';
        board[i][N+1] = '#';    
    }

    display();
}

int check(int i,int j)
{
    int ret = 1;
    int p = 0;

    for(p=0; p<3; p++)
    {
        int ni = i;
        int nj = j;

        while( ret && (board[ni][nj] != '#') )
        {
            ni = ni + pos[p].ios;
            nj = nj + pos[p].jos;

            ret = ret && (board[ni][nj] != '*');
        }
    }
    return ret; 
}

int find(int i)                       //查找的第i行 
{
    int j;
    if(i > N)
    {
        count++;
        printf("Solution: %d\n", count);
        display();                   //顯示 
        getchar(); 
    }
    else
    {
        for(j=1;j<=N;j++)
        {
            if(check(i,j))
            {
                board[i][j] = '*';          
                find(i+1);
                board[i][j] = ' ';            //????
            }   
        }   
    } 
}

數字的分解問題

輸出正整數和等于n的所有不增的正整數和式，如：
4=4
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1

a:用于存放分解的數
n:需要分解的數的和
k:分解的深度 
int integer_fac(int a[],int n,int k)
{
    int j,p;
    for(j=n; j>=1; j--)
    {
        if(j <= a[k-1])
        {
            a[k] = j;
            if(j == n)
            {
                printf("%d = %d",a[0],a[1]);
                for(p=2;p<=k;p++)
                {
                    printf("+%d",a[p]);
                }
                printf("\n");
            } 
            else
            {
                integer_fac(a,n-j, k+1);
            }   
        }
    }  
    return 0;
}