---

递归程序设计是一个重要的程序设计思想。可以应用递归设计来解决字符串，链表，树中一些常见的问题。尤其是树中，很多问题都可以使用递归的方法来解决。在利用递归解决问题的时候，有2个关键的地方：

 

首先就是要找到问题的最简子问题，也就是问题中最简单的情况，比如对于一个链表，最简单情况就是链表为空或者只有一个结点；对于一个字符串，最简单情况就是字符串为NULL或者只有一个’\0’字符；自然数最简单的情况就是0或者1；树最简单的情况就是为NULL或者只有一个结点等，而更多的问题已经明确提出了最简子问题，比如阶乘中的0！和1！，在定义中已经给了出来。所以，最简子问题往往是很容易分析出来的。这个最简子问题，就是递归的出口。

 

然后是要通过分析和转换，将原问题转化为子问题。子问题和原问题是同类问题，但子问题的规模应该比原问题要小。比如求n!那么它的子问题就是(n-1)!，只需要把(n-1)!乘以n就是n的阶乘了。又比如要求斐波那契数列的第n个值，只需要求出(n-1)的值和(n-2)的值，那么就可以求出n的值了。在先序遍历树t的时候，当把根节点遍历完后，因为t->left和t->right是它的子树，也就是子问题，所以然后用递归遍历t->left和t->right就可以了。

 

1．  字符串问题。

问题：不允许使用任何全局或局部变量编写 int strlen(char *strDest)。

 

int strlen( const char* s )

{

     return *s?1+strlen(s+1):0;

}

 

问题：请反向的输出一个字符串：比如”hello, world!”，打印出来是：”!dlrow, olleh”。

 

void inverse(char *p)

{

    if( *p = = '\0' )

         return;

    inverse( p+1 );

    printf( "%c", *p );

}

 

2．  递归实现链表转置。

 

list ResverseList(list l)

{

   if(!l || !l->next)

    return l;

   list n = reverse(l->next);

   l->next->next = l;

   l->next=null;

   return n;

 }

 

3．编写一个计算一棵二叉树t的高度的函数。

首先归纳出计算高度的递归函数height(t) ：

1）0                                                             t == NULL

2）max(height(t->left), height(t->right)) + 1             t != NULL

 

int height(btree *t)

{

     int h, h1, h2;

     if (s == NULL)

    {

         return (0);

     }

    else

    {

         h1 = height(t->left);

         h2 = height(t->right);

         if (h1 > h2)

    {

              h = h1 + 1;

         }

    else

    {

              h = h2 + 1;

         }

         return (h);

     }

}

 

4．编写一个递归算法，求出二叉树中所有叶结点的最大枝长。二叉树用标准表示法。

 

首先归纳出计算高度的递归函数maxlength(t)：

1）0                                                           t->left == NULL && t->right == NULL

2）maxlength(t->left) + 1                                   t->right == NULL

3）maxlength(t->right) + 1                                 t->left == NULL

4）max(maxlength(t->left), maxlength(t->right))+1 t->left != NULL && t->right != NULL

 

int maxlength(btree *t)

{

     int max, max1, max2;

 

     iif (t->left == NULL && t->right == NULL)

    {

         return (0);

     }

    else if (t->left == NULL)

    {

         return (maxlength(t->right) + 1);

     }

    else if (t->right == NULL)

    {

         return (maxlength(t->left) + 1);

     }

    else

    {

         max1 = maxlength(t->left);

         max2 = maxlength(t->right);

         if (max1 > max2)

        {

              max = max1 + 1;

         }

    else

        {

              max = max2 + 1;

         }

         return (max);

     }

}

 

5．试设计判断两棵二叉树是否相似的算法，所谓二叉树t1和t2相似，指的是t1和t2都是空的二叉树；或者t1和t2的根结点相似的并且t1和t2的左右子树都是相似的。

 

int like(btree *b1, btree *b2)

{

     int  like1, like2;

     iif (b1 == NULL && b2 == NULL)

    {

         return (1);

     }

    else if (b1 == NULL || b2 == NULL)

    {

         return (0);

     }

    else

    {

         like1 = like(t1->left, t2->left);

         like2 = like(t1->right, t2->right);

         return (like1 && like2);

     }

}

 

6．假设二叉树采用链接方法存储，编写一个函数复制一棵给定的二叉树。

 

btree *copy(btree *b)

{

     btree *p;

     iif (b != NULL)

    {

         p = (btree *)malloc(sizeof (btree));

         p->data = b->data;

         p->left = copy(b->left);

         p->right = copy(b->right);

         return (p);

     }

    else

    {

         return (NULL);

     }

}

 

7．假设二叉树采用链接方法存储，编写一个算法，求出二叉树中所有叶结点的最大和最小枝长。

 

void maxminleaf(btree *b, int *m, int *n)

{

     int  m1, m2, n1, n2;

 

     iif (b == NULL)

    {

         *m = 0;

         *n = 0;

     }

    else

    {

         maxminleaf(b->left, &m1, &n1);

         maxminleaf(b->right, &m2, &n2);

         m = max(*m1, *m2) + 1;

         n = min(*n1, *n2) + 1;

     }

}

 

8．设树b是一棵采用链接存储结构的二叉树，编写一个把树b的左右子树进行交换的函数。

 

btree *swap(btree *b)

{

     btree    *t, *t1, *t2;

 

     iif (b == NULL)

    {

         t == NULL;

     }

    else

    {

         t = (btree *)malloc(sizeof (btree));

         t->data = b->data;

         t1 = swap(b->left);

         t2 = swap(b->right);

         t->left = t2;

         t->right = t1;

     }

     return (t);

}

 

9．试设计一个算法计算一棵给定二叉树的叶子结点数。

 

int leafs(btree *b)

{

     int  num1, num2;

 

     iif (b == NULL)

    {

         return (0);

     }

    else if (b->left == NULL && b->right == NULL)

    {

         return (1);

     }

    else

    {

         num1 = leafs(b->left);

         num2 = leafs(b->right);

         return (num1 + num2);

     }

}

 

10．请实现快速排序的非递归算法，实现过程不能使用第三方库函数。

 

#define Maxsize 100

typedef struct

{     

     int low;

     int high;

}node;

 

void quicksort(int a[], int n)

{    

     int i, j, low, high, tmp, top = -1;

     node stack[Maxsize];

     //初始化栈

     top++;

     stack[top].low = 0;

     stack[top].high = n-1;

 

     while(top > -1)

     {  

         //出栈

         low = stack [top].low;

         high = stack [top].high;

         top--;

        

         i = low;

         j = high;

 

         if(low < high)

         {

              tmp = a[low];

              while(i != j)

              {   

                   while(i<j && a[j]>tmp)

                       j--;

                   if(i < j)

                   {

                       a[i] = a[j];

                       i++;

                   }

                   while(i<j && a[i]<tmp)

                       i++;

                   if(i < j)

                   {

                       a[j] = a[i];j--;

                   }

              }

              a[i] = tmp;

              //将中间结果保存在栈中

              top++;

              stack [top].low = low;

              stack [top].high = i-1;

              //将中间结果保存在栈中

              top++;

              stack [top].low = i+1;

              stack [top].high = high;

         }

     }

}

思考题：一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。求总共有多少总跳法，并分析算法的时间复杂度。

 

sum(N)=1 (N=1); 

sum(N)=2 (N=2);

sum(N)=sum(N-1)+sum(N-2) (N>2);

 

int jump_sum(int n)  //递归版本

{

   if (n == 1 || n == 2)

        return n;

    return ......;

}