题目：81枚硬币中，有一枚假币且这枚假币比其它的轻。称四次把这枚硬币找出来。
算法描述：
81=3^4
把所有的硬币分成数目相同的三份，把两份(x和y)放在天平上，如果重量不等，则假币在轻的一份里；如果重量相等，则假币在没称的那份里(z)。此时硬币总量变为1/3。依此循环，称三次后，剩三枚硬币，再称一次则可找出假币。
这个题适合于用递归来解决。递归的特点是：函数里面嵌套本函数。递归函数的执行分为两个环节：递推和回归：遇到本函数则递推；函数有了最终值时开始回归。
主函数中定义了重量为10的81枚硬币(其中第10枚为假币，重量为6)。递归函数weight(m,n)的参数m,n分别是当前所有硬币的序号的开始数和结束数(例如，称了第1次发现硬币可能在第1-27枚中，则m=1,n=27。)当m=n时，假币找到，函数开始回归。
以下代码在turboc2.0中执行通过。如果你也在turobc中运行，请删除其中的中文注释。
1 #define count 81
2 #define badcoin 10
3 #include <stdio.h>
4 int a[count];
5 int main()
6 {int i;
7 int t = 0;
8 clrscr();
9 for (i = 0;i<count;i++)
10 a[i]= 10;
11 a[badcoin]=6;
12 t= weight(1,count);
13 printf("the %dth coin is bad!",t);
14 system("PAUSE");
15 return 0;
16 }
17
18 int weight(int m,int n){
19 int j=0;
20 int i=0;
21 int x=0;
22 int y=0;
23 int z=0;
24 if(m>=n)
25 return m;
26 for (i=0;i<(n-m+1)/3;i++,j++){
27 x += (a[m+j]);
28 y += (a[m+(n-m+1)/3+j]);
29 z += (a[m+2*(n-m+1)/3+j]);
30 }
31 if (x==y){
32 m = m+2*(n-m+1)/3;
33 weight(m,n);
34 }
35 else if(x>y){
36 m = m+(n-m+1)/3;
37 n = m+(n-m+1)/2-1;
38 weight(m,n);
39 }
40 else{
41 n=m+(n-m+1)/3-1;
42 weight(m,n);
43 }
44 }
45
2 #define badcoin 10
3 #include <stdio.h>
4 int a[count];
5 int main()
6 {int i;
7 int t = 0;
8 clrscr();
9 for (i = 0;i<count;i++)
10 a[i]= 10;
11 a[badcoin]=6;
12 t= weight(1,count);
13 printf("the %dth coin is bad!",t);
14 system("PAUSE");
15 return 0;
16 }
17
18 int weight(int m,int n){
19 int j=0;
20 int i=0;
21 int x=0;
22 int y=0;
23 int z=0;
24 if(m>=n)
25 return m;
26 for (i=0;i<(n-m+1)/3;i++,j++){
27 x += (a[m+j]);
28 y += (a[m+(n-m+1)/3+j]);
29 z += (a[m+2*(n-m+1)/3+j]);
30 }
31 if (x==y){
32 m = m+2*(n-m+1)/3;
33 weight(m,n);
34 }
35 else if(x>y){
36 m = m+(n-m+1)/3;
37 n = m+(n-m+1)/2-1;
38 weight(m,n);
39 }
40 else{
41 n=m+(n-m+1)/3-1;
42 weight(m,n);
43 }
44 }
45
深入理解递归：
递归相当于我们数学中的括号嵌套：最里面的运算最先执行。算出结果后再与次里面的括号中的式子计算，直到算到最外面的式子，得出结果。
递推：
递推以不再递推为终点。不再递推的条件是：参数的变化使得递推终于有界，得到了实际值。在上例中，递推的边界就是m=n。此时weight(10,10)有了最终的实际值，于是开始回归。
回归：
对上面的weight(m,n)执行单步跟踪可发现，当m=n=10时，函数执行了第26行的return后，跳到了第39行，而不是第44行。然后在39->44行循环四次。这是因为，函数执行了weight(10,10)后，返回上一层函数weight(9,11)的调用处。此时，函数weight(9,11)执行到第四十行。这就是回归的过程。