经典算法_递归

经典算法_递归

循环可以实现的，递归一定可以实现

递归可以实现的，循环不一定可以实现。

1 费波拉契数列，天梯，兔子繁殖

2 阶乘

3 递增1+2+3+...+n

4 判断整数有多少位

5 判断一个数是否为3的幂，1代表是3的幂，0代表不是

6 十进制转二进制

7 十进制转八进制

8 十进制转十六进制

9 判断一个数组是否升序，降序，等序

10 打印出一个整数的逆序

11 汉诺塔

12 计算1+(1*2)+(1*2*3)+...+(1*2*3*...*n)

13 编写计算m的n次方的递归函数。

14 编一个程序，读入具有5个元素的整型数组，然后调用一个函数，递归计算这些元素的积。

15 编一个程序，读入具有5个元素的实型数组，然后调用一个函数，递归地找出其中的最大元素，并指出它位置。

16 不使用+-*/，计算两个整数之和

17 模拟计算器，输入字符串，计算结果

1 费波拉契数列，天梯，兔子繁殖

有一个天梯，每次只能走1步或者2步，阶梯从0开始计数，现在输入天梯的阶数，求一共有多少种走法。

由于每次只能走1步或者2步，因此在走到第3阶之前，不是从第1阶走2步，就是从第2阶走1步。故第3阶的走法是第1阶的走法加上第2阶的走法的和。如此类推。

兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生成一对小兔子。一年以后可以繁殖多少对兔子呢？

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<windows.h>
 5 
 6 double tencent(int n);//如果数值过大，需要用到double类型
 7 
 8 void main()
 9 {
10     int n;
11 
12     scanf("%d", &n);
13 
14     printf("%f", tencent(n));
15 
16     system("pause");
17 }
18 
19 double tencent(int n)//递归，有返回值，因此有多个return
20 {
21     if (n == 1)//第1阶，1种走法
22     {
23         return 1;
24     }
25     else if (n == 2)//第2阶，2种走法
26     {
27         return 2;
28     }
29     else
30     {
31         return tencent(n - 1) + tencent(n - 2);
32     }
33 }

2 阶乘

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 
 6 int fun(int n)
 7 {
 8     if (n == 1)
 9     {
10         return 1;
11     }
12     else
13     {
14         return fun(n - 1)*n;
15     }
16 }
17 
18 void main()
19 {
20     int n;
21 
22     scanf("%d", &n);
23 
24     printf("%d", fun(n));
25 
26     system("pause");
27 }

3 递增1+2+3+...+n

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 
 6 int fun(int n)
 7 {
 8     if (n == 1)
 9     {
10         return 1;
11     }
12     else
13     {
14         return fun(n - 1) + n;
15     }
16 }
17 
18 void main()
19 {
20     int n;
21 
22     scanf("%d", &n);
23 
24     printf("%d", fun(n));
25 
26     system("pause");
27 }

4 判断整数有多少位

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 
 6 int getwei(int num)
 7 {
 8     if (num < 10)
 9     {
10         return 1;
11     }
12     else
13     {
14         return getwei(num / 10) + 1;
15     }
16 }
17 
18 void main()
19 {
20     int num;
21 
22     scanf("%d", &num);
23 
24     printf("%d", getwei(num));
25 
26     system("pause");
27 }

5 判断一个数是否为3的幂，1代表是3的幂，0代表不是

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<windows.h>
 5 
 6 int mi(int num)//递归，1代表是3的幂，0代表不是
 7 {
 8     if (num < 1)//如果小于1，不是3的幂
 9     {
10         return 0;
11     }
12     else if (num == 1)//3的最小幂是1
13     {
14         return 1;
15     }
16     else
17     {
18         if (num % 3 == 0)//如果是3的倍数，继续除以3，继续递归
19         {
20             return mi(num / 3);
21         }
22         else
23         {
24             return 0;
25         }
26     }
27 }
28 
29 void main()
30 {
31     int num;
32     int i;
33     
34     scanf("%d", &num);
35 
36     printf("%d", mi(num));
37 
38     system("pause");
39 }

6 十进制转二进制

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 
 6 void ten2two(int num)
 7 {
 8     if (num < 2)
 9     {
10         printf("%d", num);
11     }
12     else
13     {
14         ten2two(num / 2);
15         printf("%d", num % 2);
16     }
17 }
18 
19 void main()
20 {
21     int num = 2;
22 
23     ten2two(num);
24 
25     system("pause");
26 }

7 十进制转八进制

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 
 6 void ten2eight(int num)
 7 {
 8     if (num < 8)
 9     {
10         printf("%d", num);
11     }
12     else
13     {
14         ten2eight(num / 8);
15         printf("%d", num % 8);
16     }
17 }
18 
19 void main()
20 {
21     int num = 8;
22 
23     ten2eight(num);
24 
25     system("pause");
26 }

8 十进制转十六进制

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 
 6 void ten2sixteen(int num)
 7 {
 8     if (num < 10)
 9     {
10         printf("%d", num);
11     }
12     else if (num == 10)
13     {
14         printf("A");
15     }
16     else if (num == 11)
17     {
18         printf("B");
19     }
20     else if (num == 12)
21     {
22         printf("C");
23     }
24     else if (num == 13)
25     {
26         printf("D");
27     }
28     else if (num == 14)
29     {
30         printf("E");
31     }
32     else if (num == 15)
33     {
34         printf("F");
35     }
36     else
37     {
38         ten2sixteen(num / 16);
39         switch (num % 16)
40         {
41         case 0:
42         case 1:
43         case 2:
44         case 3:
45         case 4:
46         case 5:
47         case 6:
48         case 7:
49         case 8:
50         case 9:
51             printf("%d", num % 16);
52             break;
53         case 10:
54             printf("A");
55             break;
56         case 11:
57             printf("B");
58             break;
59         case 12:
60             printf("C");
61             break;
62         case 13:
63             printf("D");
64             break;
65         case 14:
66             printf("E");
67             break;
68         case 15:
69             printf("F");
70             break;
71         }
72     }
73 }
74 
75 void main()
76 {
77     int num = 1234;
78 
79     ten2sixteen(num);
80 }

9 判断一个数组是否升序，降序，等序

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 #define N 10//数组元素个数
 5 int a[N] = { 1,2,3,4,5,6,7,8,9,10 };
 6 
 7 int isadd(int n)//升序返回1，否则返回0
 8 {
 9     if (n == 1)//循环到下标1
10     {
11         return a[n - 1] < a[n];//改成>判断降序，改成==判断等序
12     }
13     else
14     {
15         return a[n - 1] < a[n] && isadd(n - 1);//改成>判断降序，改成==判断等序
16     }
17 }
18 
19 void main()
20 {
21     printf("%d", isadd(N - 1));//数组的最后一个下标，开始往前循环
22 
23     system("pause");
24 }

10 打印出一个整数的逆序

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 void nixu(int n)
 5 {
 6     if (n < 10)
 7     {
 8         printf("%d", n);
 9     }
10     else
11     {
12         printf("%d", n % 10);
13         nixu(n / 10);
14     }
15 }
16 
17 void main()
18 {
19     int num = 123456;
20 
21     nixu(num);
22 
23     system("pause");
24 }

11 汉诺塔

如果只有1个盘子，直接将A柱子上的盘子从A移到C

否则，先将A柱子上的n-1个盘子借助C移到B

直接将A柱子上的盘子从A移到C

最后将B柱子上的n-1个盘子借助A移到C

C实现

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 
 6 int hanoi(int n)
 7 {
 8     if (n == 1)
 9     {
10         return 1;
11     }
12     else
13     {
14         return 2 * hanoi(n - 1) + 1;
15     }
16 }
17 
18 //左边a->右边c，中间参数b是辅助盘
19 void hanoi1(int n, char a, char b, char c)
20 {
21     if (n == 1)
22     {
23         printf("%c->%c
", a, c);
24     }
25     else
26     {
27         hanoi1(n - 1, a, c, b);//中间参数c辅助
28         printf("%c->%c
", a, c);
29         hanoi1(n - 1, b, a, c);//中间参数a辅助
30     }
31 }
32 
33 void main()
34 {
35     int n;
36 
37     scanf("%d", &n);//代表汉诺塔有几个盘子
38 
39     printf("移动%d次
", hanoi(n));
40 
41     hanoi1(n, 'a', 'b', 'c');
42 
43     system("pause");
44 }

C++实现

 1 #include <iostream>
 2 
 3 void hanoi(int n, char a, char b, char c)//参数说明，把左边a放到右边c，中间b不处理
 4 {
 5     static int count = 0;
 6     count++;
 7     std::cout << "第" << count << "次：";
 8 
 9     if (n < 1)
10     {
11         return;
12     }
13     else
14     {
15         hanoi(n - 1, a, c, b);
16         std::cout << a << "->" << c << std::endl;
17         hanoi(n - 1, b, a, c);
18     }
19 }
20 
21 void main()
22 {
23     int n;
24     std::cin >> n;
25 
26     hanoi(n, 'A', 'B', 'C');
27 
28     system("pause");
29 }

12 计算1+(1*2)+(1*2*3)+...+(1*2*3*...*n)

需要用到双层递归，分别是阶乘和阶乘的相加

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 
 6 int fun(int num)//实现阶乘 1*2*3*...*n
 7 {
 8     if (num == 1)
 9     {
10         return 1;
11     }
12     else
13     {
14         return num*fun(num - 1);
15     }
16 }
17 
18 //双层递归
19 
20 int add(int n)//实现相加
21 {
22     if (n == 1)
23     {
24         return 1;
25     }
26     else
27     {
28         return add(n - 1) + fun(n);
29     }
30 }
31 
32 void main()
33 {
34     printf("%d
", add(1));
35 
36     printf("%d
", add(2));
37 
38     printf("%d
", add(3));
39 
40     system("pause");
41 }

13 编写计算m的n次方的递归函数。

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 
 6 int getm_n(int m, int n)
 7 {
 8     if (m == 0)//0的n次方是0
 9     {
10         return 0;
11     }
12     else if (n == 0)//非0的0次方是1
13     {
14         return 1;
15     }
16     else
17     {
18         return getm_n(m, n - 1)*m;
19     }
20 }
21 
22 void main()
23 {
24     int m = 2;
25     int n = 10;
26 
27     printf("%d
", getm_n(m, n));
28 
29     system("pause");
30 }

14 编一个程序，读入具有5个元素的整型数组，然后调用一个函数，递归计算这些元素的积。

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 
 6 #define N 5
 7 
 8 int cheng(int *arr, int n)
 9 {
10     if (n == 0)
11     {
12         return arr[0];
13     }
14     else
15     {
16         return cheng(arr, n - 1)*arr[n];
17     }
18 }
19 
20 void main()
21 {
22     int arr[N] = { 1,2,3,4,5 };
23     int i;
24 
25     for (i = 0; i < N; i++)
26     {
27         printf("%5d", arr[i]);
28     }
29 
30     printf("
%d
", cheng(arr, N - 1));//最后的下标是N-1
31 
32     system("pause");
33 }

15 编一个程序，读入具有5个元素的实型数组，然后调用一个函数，递归地找出其中的最大元素，并指出它位置。

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 
 6 int search_max(double *arr, int num)//递归查找数组最大值的下标，第1个参数是数组，第2个参数是数组元素个数
 7 {
 8     if (num == 1)//如果数组只有一个元素，最大值的下标就是0
 9     {
10         return 0;
11     }
12     else
13     {
14         if (arr[num - 1] > arr[search_max(arr, num - 1)])//如果后面的元素比前面的元素大，返回后面元素的下标
15         {
16             return num - 1;
17         }
18         else
19         {
20             return search_max(arr, num - 1);
21         }
22     }
23 }
24 
25 void main()
26 {
27     double arr[5] = { 1,2,3,4,5 };
28     int num = search_max(arr, 5);//递归查找数组最大值的下标，第1个参数是数组，第2个参数是数组元素个数
29 
30     printf("最大元素位置是%d，最大元素是%lf
", num, arr[num]);
31 
32     system("pause");
33 }

16 不使用+-*/，计算两个整数之和

 1 #include <iostream>
 2 
 3 //将来从事手机端、嵌入式开发，位操作
 4 class jia
 5 {
 6 private:
 7     int x;
 8     int y;
 9 public:
10     jia(int a, int b) :x(a), y(b)//构造函数
11     {
12 
13     }
14     int jiafa()//返回相加的结果
15     {
16         return x + y;
17     }
18     int getx()//返回x的值
19     {
20         return x;
21     }
22     int gety()//返回y的值
23     {
24         return y;
25     }
26     int newjiafa(int a, int b)//递归
27     {
28         if (a == 0)
29         {
30             return b;
31         }
32         else if (b == 0)
33         {
34             return a;//让相与&慢慢趋势为0
35         }
36         else
37         {
38             int res = a^b;//异或，先求结果
39             int wei = (a&b) << 1;//进位，左移，乘以2
40             std::cout << "res=" << res << " wei=" << wei << std::endl;//打印中间值
41             return newjiafa(res, wei);
42         }
43     }
44 };
45 
46 void main()
47 {
48     jia jia1(10, 9);//创建对象
49 
50     std::cout << jia1.newjiafa(jia1.getx(), jia1.gety()) << std::endl;//打印结果
51     
52     system("pause");
53 }

17 模拟计算器，输入字符串，计算结果

  1 #include <iostream>
  2 
  3 const int MAX = 1024;
  4 
  5 void qukongge(char *str);//去除字符串的空格
  6 double getnum(char *str, int & index);//分离数字，把字符串转换为数字
  7 double fenxi(char *str);
  8 double term(char *str, int & index);
  9 char *extract(char *str, int &index);
 10 
 11 void main()
 12 {
 13     char str[MAX] = { 0 };
 14     int i(0);
 15     std::cout << "请输入表达式" << std::endl;
 16     std::cin.getline(str, MAX);
 17 
 18     qukongge(str);//去除字符串的空格
 19 
 20     //std::cout << str << std::endl;
 21 
 22     //std::cout << getnum(str, i) << std::endl;
 23 
 24     std::cout << fenxi(str) << std::endl;
 25 
 26 }
 27 
 28 void qukongge(char *str)//去除字符串的空格
 29 {
 30     int i(0);
 31     int j(0);
 32 
 33     while ((*(str + i) = *(str + j++)) != '')
 34     {
 35         if (*(str + i) != ' ')//如果不是空格
 36         {
 37             i++;
 38         }
 39     }
 40 }
 41 
 42 double getnum(char *str, int & index)//分离数字，把字符串转换为数字
 43 {
 44     double value(0.0);
 45 
 46     if (*(str + index) == '(')
 47     {
 48         char *substr(nullptr);
 49         substr = extract(str, ++index);
 50 
 51         value = fenxi(substr);
 52         delete[]substr;
 53 
 54         return value;
 55     }
 56 
 57     if (!isdigit(*(str + index)))//如果不是数字
 58     {
 59         char error[30] = "get error";
 60         throw error;
 61     }
 62 
 63     while (isdigit(*(str + index)))
 64     {
 65         value = 10 * value + (*(str + index) - '0');
 66         index++;
 67     }
 68 
 69     if (*(str + index) != '.')//如果没有小数点
 70     {
 71 
 72     }
 73     else
 74     {
 75         double xiaoshu(1.0);
 76         while (isdigit(*(str + (++index))))
 77         {
 78             xiaoshu /= 10;
 79             value = value + (*(str + index) - '0')*xiaoshu;
 80         }
 81     }
 82     
 83     return value;
 84 }
 85 
 86 double fenxi(char *str)
 87 {
 88     double value(0.0);
 89     int index(0);
 90     value += term(str, index);//第一个数字
 91 
 92     for (;;)//后面的数字
 93     {
 94         switch (*(str + (index++)))
 95         {
 96         case '':
 97             return value;
 98         case '+':
 99             value += term(str, index);
100             break;
101         case '-':
102             value -= term(str, index);
103             break;
104         default:
105             break;
106         }
107     }
108 }
109 
110 double term(char *str, int & index)
111 {
112     double value(0.0);
113     value = getnum(str, index);//获取数据
114     while (1)
115     {
116         if (*(str + index) == '*')//如果是*
117         {
118             value *= getnum(str, ++index);//先向后移动，跳过*，再调用函数
119         }
120         else if (*(str + index) == '/')//如果是/
121         {
122             value /= getnum(str, ++index);//先向后移动，跳过/，再调用函数
123         }
124         else
125         {
126             break;
127         }
128     }
129     return value;
130 }
131 
132 char *extract(char *str, int &index)
133 {
134     char *pstr(nullptr);
135     int num(0);//记录有多少对()
136     int bufindex(index);//记录下标，备份
137     do
138     {
139         switch (*(str + index))
140         {
141         case ')':
142             if (!num)
143             {
144                 ++index;
145                 pstr = new char[index - bufindex];
146                 if (!pstr)
147                 {
148                     throw "malloc fail";
149                 }
150                 strncpy_s(pstr, index - bufindex, str + bufindex, index - bufindex - 1);//拷贝字符串
151                 return pstr;
152             }
153             else
154             {
155                 num--;
156             }
157             break;
158         case '(':
159             num++;
160             break;
161         }
162     } while (*(str + index++) != '');
163 
164     throw "error fail";
165 }

【推广】免费学中医，健康全家人

原文地址：https://www.cnblogs.com/denggelin/p/5487204.html