C语言递归练习

1、炮弹一样的球状物体，能够堆积成一个金字塔，在顶端有一个炮弹，它坐落在一个4个炮弹组成的层面上，而这4个炮弹又坐落在一个9个炮弹组成的层面上，以此类推。写一个递归函数CannonBall，这个函数把金字塔的高度作为参数，并且返回它所包括的炮弹数量。函数必须按照递归方式实现，不可以使用迭代结构，例如while或for。

 1 int CannonBall(int h)
 2 {
 3     if(h == 1) return 1;
 4     else
 5         return CannonBall(h-1) + pow(h,2);
 6 }
 7 
 8 int main(void)
 9 {
10     printf("%d\n",CannonBall(4));
11     return 0;
12 }

C代码

2、使用C编写一个指数函数，实现n^k

 1 int RaiseToPower(int n, int k)
 2 {
 3     if(k == 0)
 4         return 1;
 5     else
 6         return n * RaiseToPower(n,k -1);
 7 }
 8 
 9 int main()
10 {
11     printf("%d\n",RaiseToPower(3,4));
12     return 0;
13 }

C代码

3、使用欧几里得公式写一个递归函数gcd（m,n)，用来计算m与n的最大公约数.

 1 int gcd(int m, int n)
 2 {
 3     if(m % n ==0)
 4         return n;
 5     else
 6         return gcd(n,m % n);
 7 }
 8 
 9 int main()
10 {
11     printf("%d\n",gcd(18,4));
12     return 0;
13 }

C代码

4、写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和，例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19

 1 int DigitSum(int n)
 2 {
 3     if(n < 10) 
 4         return n;
 5     else
 6         return ((n % 10) + DigitSum(n / 10));
 7 }
 8 
 9 int main()
10 {
11     printf("%d\n",DigitSum(1729));
12     return 0;
13 }

C代码

5、整数n的数字根是如下定义的：它是一个整数的所有数字的和，反复相加，直到只剩下一位数字为止。例如：1729的digital root按照如下的步骤计算：

step 1: 1+7+2+9 -----> 19

step 2: 1+9 -----> 10

step 3: 1+0 ------> 1

因为第三步的结果是1，所以1就是数字根的值。

写一个函数DigitalRoot（n），返回参数的根，注意：写一个纯粹的、不使用任何循环结构的递归函数。

 1 int DigitSum(int n)
 2 {
 3     if(n < 10) 
 4         return n;
 5     else
 6         return ((n % 10) + DigitSum(n / 10));
 7 }
 8 
 9 int DigitalRoot(int n)
10 {
11     if(n < 10)
12         return n;
13     else
14         return DigitalRoot(DigitSum(n));
15 }
16 
17 int main()
18 {
19     printf("%d\n",DigitalRoot(1729));
20     return 0;
21 }

C代码

6、计算组合数C（n，k）

 1 int Comb(int n, int k)
 2 {
 3     if(k == 0 || n == k) 
 4         return 1; 
 5     else
 6         return (Comb(n - 1,k - 1) + Comb(n - 1,k));
 7 }
 8 
 9 int main()
10 {
11     int i;
12     for(i = 0; i <= 6; i++)
13     {
14         printf("%d ",Comb(6,i));
15     }
16     printf("\n");
17     return 0;
18 }

C代码

7、将一个整数作为字符串打印

 1 #include<stdio.h>
 2 
 3 void printd(int n)
 4 {
 5     if(n < 0) {
 6         putchar('-');
 7         n = -n;
 8     }
 9     if(n / 10)
10         printd(n / 10);
11     putchar(n % 10 + '0');
12 }
13 
14 int main()
15 {
16     int a = 12238;
17     printd(a);
18     printf("\n");
19     return 0;
20 
21 }

C代码

8、运用上面printd函数的设计思想编写一个递归版本的itoa函数，即通过递归函数把整数变为字符串

 1 #include<stdio.h>
 2 
 3 void itoa(int n, char *s)
 4 {
 5     static int i;
 6     if(n / 10)
 7         itoa(n / 10, s);
 8     else {
 9         i = 0;
10         if(n < 0)
11             s[i++] = '-';
12     }
13     s[i++] = abs(n) % 10 + '0';
14     s[i] = '\0';
15 }
16 
17 int main()
18 {
19     char s[100];
20     int n = 1232;
21     itoa(n, s);
22     printf("%s\n",s);
23     return 0;
24 
25 }

C代码

9、编写一个递归版本的reverse（s）函数，以将字符串s转置

 1 #include<stdio.h>
 2 
 3 void reverser(char *s, int i, int len)
 4 {
 5     int c, j;
 6     j = len - (i + 1);
 7     if(i < j) {
 8         c = s[i];
 9         s[i] = s[j];
10         s[j] = c;
11         reverser(s, ++i, len);
12     }
13 }
14 
15 void reverse(char *s)
16 {
17     int len;
18     len = strlen(s);
19     reverser(s, 0, len);
20 }
21 
22 int main()
23 {
24     char s[100];
25     gets(s);
26     reverse(s);
27     printf("%s\n",s);
28     return 0;
29 }

C代码