打印解决汉诺塔问题的所有步骤

1 void Move(int n, int start, int goal, int temp) 2 { 3     if (n >= 1) 4     { 5         Move(n - 1, start, temp, goal);        //将最上面的n-1个盘子移到temp柱子上 6         printf("Move disk %d from %d to %d.\n", n, start, goal);    //将第n个柱子移到goal柱子上 7         Move(n - 1, temp, goal, start);        //将temp柱子上的n - 1个柱子移到goal柱子上 8     } 9         10     11 }

 用递归方法求集合中的中位数

1 void Swap(ElementType *X, ElementType *Y) 2 { 3     ElementType temp; 4     temp = *X; 5     *X = *Y; 6     *Y = temp; 7 } 8  9 ElementType FindKthLargest(ElementType s[], int K, int Left, int Right)10 {    //在s[Left]……s[Right]中找第K大的元素11     ElementType e = s[Left];        //简单取首元素为基准12     int L = Left, R = Right;13     14     while (1)15     {16         while ((Left <= Right) && (e <= s[Left])) Left++;    17         while ((Left < Right) && (e > s[Right])) Right--;18         if (Left < Right)19             Swap(&s[Left], &s[Right]);20         else21             break;    //最终brak退出时，Left一定指向第二个集合的第一个元素22     }23     Swap(&s[Left - 1], &s[L]);24     if ((Left - L - 1) >= K)25         return FindKthLargest(s, K, L, Left - 2);    //Left - 1是基准，所以下一次递归的右边界应该是Left - 226     else27     if ((Left - L - 1) < K - 1)28         return FindKthLargest(s, K - (Left - L - 1) - 1, Left, R);    //K 先减去第一个集合的Left - L - 1个元素，在减去基准元素，所以下一次递归应该是在第二个集合中求第K - (Left - L - 1) - 1个元素29     else30         return e;        //找到，返回31 }32 33 //封装前面这个查找函数34 ElementType Median(ElementType s[], int N)35 {36     return FindKthLargest(s, (N + 1) / 2, 0, N - 1);37 }

这个方法实际上利用了和快速排序相同的思路

简单选取S中的第一个元素e，根据e将集合S分为{e}和大于等于e的元素集合S1、小于e的元素集合S2; 然后通过判别集合S1的大小，将从S集合中找第K大数问题转换为在S1 和S2中的查找问题，由于S1或S2中的集合规模都比S小，这样就将复杂的问题转化为规模相对较小的问题，这也是递归函数的设计基础