一、函數(shù)調(diào)用時(shí)的棧

函數(shù)調(diào)用時(shí)的棧
程序中的“函數(shù)調(diào)用?！笔菞?shù)據(jù)結(jié)構(gòu)的一種應(yīng)用
函數(shù)調(diào)用棧一般是從高地址向低地址增長的
?棧底為內(nèi)存的高地址處
?棧頂為內(nèi)存的低地址處
函數(shù)調(diào)用棧中存儲的數(shù)據(jù)為活動記錄

程序中的棧
在不斷的壓棧過程中造成棧空間耗盡而產(chǎn)生棧溢出
棧溢出常由于函數(shù)遞歸過深或局部數(shù)組過大造成

目前成都創(chuàng)新互聯(lián)已為上千的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、夏邑網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

二、遞歸的應(yīng)用

?遞歸是一種數(shù)學(xué)上分而自治的思想
遞歸將大型復(fù)雜問題轉(zhuǎn)化為與原問題相同但規(guī)模較小的問題進(jìn)行處理
遞歸需要有邊界條件
?當(dāng)邊界條件不滿足時(shí)，遞歸繼續(xù)進(jìn)行
?當(dāng)邊界條件滿足時(shí)，遞歸停止
斐波拉切數(shù)列
斐波納契數(shù)列以如下被以遞推的方法定義：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; 
    }
}

全排列
假設(shè)集合是{a,b,c},那么這個(gè)集合中元素的全部排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}，顯然，給定n個(gè)元素共同擁有n!種不同的排列，假設(shè)給定集合是{a,b,c,d}，能夠用以下給出的簡單算法產(chǎn)生其全部排列，即集合(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))           //去重的全排列就是從第一個(gè)數(shù)字起每個(gè)數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換
                {
                    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個(gè)金盤。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動一個(gè)盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

/*
   n:需要移動的盤子數(shù)量
   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;
} 

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

#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;                                  //符合要求的個(gè)數(shù) 

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] = ' ';            //????
            }   
        }   
    } 
}

數(shù)字的分解問題

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

a:用于存放分解的數(shù)
n:需要分解的數(shù)的和
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;
} 

網(wǎng)頁題目：五、遞歸與常見問題
文章起源：http://aaarwkj.com/article24/jeicce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站維護(hù)、網(wǎng)站營銷、自適應(yīng)網(wǎng)站、網(wǎng)站設(shè)計(jì)、

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)