函数调用栈一般是从高地址向低地址增加的

栈底：高地址

栈顶：低地址

函数调用栈中存储的数据为活动记录

程序中的栈空间可以看做一个顺序栈

栈溢出通常是由于函数递归过深或局部数组过大造成

 

递归将大型复杂问题转化为与原问题相同但规模较小的问题进行处理。（找递推关系式 ）

递归需要有边界条件：

当不满足边界条件时，递归继续进行

当满足边界条件时，递归停止

递归函数要一直走到一个临界点上才能计算出结果。

所有递归算法都可以借助堆栈转换成循环结构的非递归算法。 

 

递归方式逆序字符串

#include 
     
      void reverse(char* s){    if( (s != NULL) && (*s != '\0') )    {        reverse(s + 1);                printf("%c", *s);    }}int main(){    reverse("12345");        printf("\n");        return 0;}
     

 

斐波那契数列：

#include 
     
      /** * An = An-1 + An-2 * A1 = 1 * A0 = 0  * @param n * @return  */int fibonacci(int n){    if( n > 1 )    {        return fibonacci(n-1) + fibonacci(n-2);    }    else if( n == 1 )    {        return 1;    }    else if( n == 0 )    {        return 0;    }}int main(){    int i = 0;        for(i=1; i<=10; i++)    {        printf("fibonacci(%d) = %d\n", i, fibonacci(i));    }        return 0;}
     

 

1加到100

#include 
     
      int sum(int n){    if(n>1)    {        return n + sum(n-1);    }else{        return 1;    }}int main(){    printf("%d \n", sum(100));        return 0;}
     

 

递归实现strlen

#include 
     
      int strlen(const char* s){    if( s == NULL )    {        return -1;    }    else if( *s == '\0' )    {        return 0;    }    else    {        return strlen(s+1) + 1;    }}int main(){    printf("strlen(\"12345\") = %d\n", strlen("12345"));    printf("strlen(NULL) = %d\n", strlen(NULL));    printf("strlen(\"\") = %d\n", strlen(""));        return 0;}
     

 

递归实现全排列

#include 
     
      void permutation(char s[], int b, int e){    if( (0 <= b) && (b <= e) )    {        if( b == e )        {            printf("%s\n", s);        }        else        {            int i = 0;                        for(i=b; i<=e; i++)            {                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;            }        }    }}int main(){    char s[] = "abcd";        permutation(s, 0, 3);        return 0;}
     

 

汉诺塔 

a,b,c三个柱子，a上有从小到大的盘子，在借助b的情况下，全部移到c上，移动时每一时刻必须保持小盘子在上面

hanoi.c

#include 
     
      void hanoi(int n, char a, char b, char c){    if( n > 0 )    {        if( n == 1 )        {            printf("%c -> %c\n", a, c);        }        else        {            hanoi(n-1, a, c, b);                        printf("%c -> %c\n", a, c);                        hanoi(n-1, b, a, c);        }    }}int main(){    hanoi(8, 'a', 'b', 'c');        return 0;}
     

 

---

回溯 :

回溯算法是递归应用的重要场合。

利用函数调用的活动对象可以保存回溯算法中重要的变量信息。

 思想：

　　从问题的某一状态出发，搜索可以到达的状态。

　　当某个状态达到后，可向前回退(回溯)，并继续搜索其他可达状态。

　　当所有状态都到达后，回溯算法结束。

 

八皇后问题

queue.php

#include 
     
      #define N 8typedef 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 init(){    int i = 0;    int j = 0;        for(i=0; i
      
        N )    {        //输出本次解决方案        count++;                printf("Solution: %d\n", count);                display();                getchar(); //abort the process !    }    else    {        for(j=1; j<=N; j++)        {            if( check(i, j) )            {                board[i][j] = '*';                                find(i+1);                                board[i][j] = ' '; //回溯时需要清空，否则下次进入时数据会不对            }        }    }}int main(){    init();    find(1);        return 0; }
      
     

 

迷宫问题

#include 
     
      #include 
      
       void visit ( int, int );//2表示墙壁, 0:通过 ，1;障碍int maze[7][7] = {
   {
   2, 2, 2, 2, 2, 2, 2},    {
    2, 0, 0, 0, 0, 0, 2},    {
    2, 0, 2, 0, 2, 0, 2},    {
    2, 0, 0, 2, 0, 0, 2},    {
    2, 2, 0, 0, 0, 2, 2},    {
    2, 0, 0, 0, 0, 0, 2},    {
    2, 2, 2, 2, 2, 2, 2}};int starti = 1, startj = 1;  // 入口int endI = 5, endJ = 5;      // 出口int main ( void ){    visit(starti, startj);    return 0;}//打印迷宫和线路void display(){    int i,j;        for ( i = 0; i < 7; i++ )    {        for ( j = 0; j < 7; j++ )        {            if ( maze[i][j] == 2 )                    printf ( "█" );            else if ( maze[i][j] == 1 )                    printf ( "◇" );            else                    printf ( "  " );        }        printf ( "\n" );    }}//线路查找void visit ( int i, int j ){    maze[i][j] = 1;    if ( i == endI && j == endJ )    {            display();            printf("\n");            getchar();        }                //四个方向搜索    if (maze[i][j+1] == 0 ) visit ( i, j+1 );    if (maze[i+1][j] == 0 ) visit ( i+1, j );    if (maze[i][j-1] == 0 ) visit ( i, j-1 );    if (maze[i-1][j] == 0 ) visit ( i-1, j );    maze[i][j] = 0;}