c语言递归练习

dic递归基础练习题： 1. 求1+2+3+……+n的值 int sum(int a,int b) { if(b==a) return a; return a+sum(a+1,b); }

2. 求1*2*3*……*n的值 cheng(int begin,int end) { if(begin==end) return begin; return begin * cheng(begin+1,end); }

3. 数的全排列问题。将n个数字1，2，…n的所有排列按字典顺序枚举出猴 2 3 1 2 1 3 3 1 2 3 2 1

4. 数的组合问题。从1,2,…,n中取出m个数，将所有组合按照字典顺序列出。 如n=3,m=2时，输出： 1 2 1 3 2 3

5. 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？ fruit(int begin,int times) { if(times==10) return begin; return fruit((begin+1)*2,times+1); }

6. 有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？

7. 一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？

duck(int begin,int times) { if(times==7) return begin; return duck((begin+1)*2,times+1); }

8. 著名的菲波拉契(Fibonacci)数列，其第一项为0，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。 int fbi(int i) { if(i<2) { if(i == 0) return 0; else return 1; } return fbi(i-1) +fbi(i-2); }

9. 求两个数的最大公约数。

fgongyue(int m,int n)//m要大于n，前面可以交换让它实现 { if(n == 0) return m; fgongyue(n,m%n); }

10. 求两个数的最小公倍数。

最小公倍数等于２个数之积乘最好公约数 m*n/fgongyue(m,n)

11. 输入一个数，求这个数的各位数字之和。 add_every_num(int num) {

if(num<10) return num;

return num+add_every_num(num/10); }

12. 角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。 如：输入22，

输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 STEP=16

#include \#include \

int i = 1;

int fc(int n) {

if(n == 1) { printf(\ return i;

}

else if(n%2 == 0) { printf(\ fc(n/2); i++; } else { printf(\ fc(n*3+1); i++; } }

int main(int argc, char* argv[]) {

int n,step;

printf(\ scanf(\ step = fc(n);

printf(\ return 0; }

13. 将十进制转换为二进制。

#include \#include \

int fc(int num) {

if(num == 1) { printf(\ return 0; }

fc(num/2);

printf(\ }

int main(int argc, char* argv[]) {

int num;

printf(\ scanf(\ fc(num); printf(\ return 0; }

14. 计算M＝max(a,b,c)/[max(a+b,b,c)*max(a,b,b+c)],其中a，b，c由键盘输入。skip

15. 梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。

return 1+(fc(n-1)+fc(n-2)

16. 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况?

17. 给出一棵二叉树的中序与后序排列。求出它的先序排列。

18. 求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。 19. 已知一个一维数组A[1..N]。{N<50} 又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。

20. 要求找出具有下列性质的数的个数(包含输入的自然数n)：

先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理: ①. 不作任何处理;

②. 在它的左边加上一个自然数,但该自然数不能超过原数首位数字的一半; ③. 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 样例: 输入: 6

满足条件的数为 6 16 26 126 36 136 输出: 6

21. 自然数的拆分问题。给定自然数n,将其拆分成若干自然数的和。输出所有解，每组解中数字按从小到大排列。相同数字的不同排列算一组解。如： 3=1+1+1 3=1+2 3=3

22. 用递归的方法求N个数中最大的数及其位置。 23. 写出折半查找的递归算法。 24. 快速排序法。

思考题 :

1、数学宝塔，从最顶上走到最底层，每次只能走到下一层的左边或右边的数字，求出使所走到的所有数字之和为60的途径。 7

4 6 6 9 3 6 3 7 1 2 5 3 2 8 5 9 4 7 3 2 6 4 1 8 5 6 3 3 9 7 6 8 4 1 5 2 5 7 3 5 7 8 4 2

2、 汉诺塔问题：设有三个塔座，依次命名为x,y,z。有z个直径不同的圆盘，由小到大依次编号为1、2、……，n。开始时，它们全部按递减的次序插在塔座上。现要求按下列规则把n个圆盘按次序插放在z塔座上。 （1）、每次只能移动一个圆盘； （2）、圆盘可以从任一个塔座上移到另一个塔座上； （3）、任何时刻都不能把一个较大的圆盘压在较小的圆盘上。

典型例题:

1.设有n个数已经按从大到小的顺序排列，现在从键盘上输入n，判断它是否在这n 个数中，如果存在则输出“yes”否则输出“no”。 Program lx4; Const n=30;

Var a:array[1..n]of integer; F,r,x,k:integer;

Program search(x,top,bot:integer); Var mid:integer; Begin

if top<=bot then Begin

Mid=(top + bot) div 2;

If x =a[mid] then writeln(x:5,mid:5,?yes?) else If x

else Writeln(x:5,?no?); End; Begin

Writeln(?input n ge shu?); For k:=1 to n do read(a[k]); Read(x); F:=1;r:=n; Search(x,f,r); End.

2.hanoi塔问题。

递归：procedure Hanoi(n:integer;x,y,z:char); Begin

本文来源：https://www.bwwdw.com/article/tzwt.html