递归
什么是递归
递归简而言之就是函数自己调用自己 如图所示
但是递归并不是简简单单的自己调用自己的过程 它分为 传递 和 回归，传递就是橙色箭头 回归则是黑色箭头 这就是递归
以 计算阶乘为例，假设我们输入6 计算6的阶乘为例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#define _crt_secure_no_warnings
#include<stdio.h>
int factorial(int x) //递归体函数
{
if (x == 1)
{
return 1;
}
return x * (factorial(x - 1));
}
int main()
{
int i = 0;
scanf("%d", & i);
int k = factorial(i);
printf("%d", k);
return 0;
}
|
具体实现过程如下 我们可以很清楚看到 先传递 在归一 就是递归
递归的特点 结构 缺点
递归的本质
在传递的过程将问题化简 归一的过程将化简的问题解决
递归的应用
(1). 问题的定义是按递归定义的（fibonacci函数，阶乘，…）；
(2). 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；
(3). 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）
递归实战
阶乘
阶乘递归解法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#define _crt_secure_no_warnings
#include<stdio.h>
int factorial(int x) // 递归体
{
if (x == 1)// 函数出口
{
return 1;
}
return x * (factorial(x - 1));//就x！转换成x*((x-1)!) 达到传递化简的目的
}
int main()
{
int i = 0;
scanf("%d", & i);
int k = factorial(i);
printf("%d", k);
return 0;
}
|
阶乘普通解法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#define _crt_secure_no_warnings
#include<stdio.h>
int main()
{
int k = 0;
scanf("%d", &k);
int i = 0;
int sum = 1;
for (i = 1; i < k + 1; i++)
{
sum = sum * i; //利用循环累乘 最后打印
}
printf("%d", sum);
return 0;
}
|
斐波拉契数列
斐波拉契数列 即0、1、1、2、3、5、8、13、21、34、………这样一串数字
斐波拉契数列递归解法
递归解法通过数学函数定义可轻松得到 他的递归体
是当n>1时 fib(n-2)+fib(n-1)
递归出口就是n=0 返回0，n=1，返回1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#define _crt_secure_no_warnings
#include<stdio.h>
int fib(int x) //第0个元素为0 第一个元素为1
{
if (x == 0)
{
return 0;
}
else if (x == 1) //出口
{
return 1;
}
else
return fib(x - 2) + fib(x - 1); //循环体
}
int main()
{
int k = 0;
scanf("%d", &k);
int sum = fib(k);
printf("%d", sum);
return 0;
}
|
斐波拉契数列普通解法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#define _crt_secure_no_warnings
#include<stdio.h>
int fib(int x)
{
int i = 0;
int j = 1;
int k = 0;
int m = 0;
for (m = 0; m < x-1; m++)
{
k = i + j;
i = j;
j = k;
}
return k;
}
int main()
{
int k = 0;
scanf("%d", &k);
int sum = fib(k);
printf("%d", sum);
return 0;
}
|
汉诺塔
输出一个数字的每一位
如 输入 1234 输出 1 2 3 4
普通解法
这里用取对数的方法得到有多少位 依次除以位数的10次方 即可
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#define _crt_secure_no_warnings
#include<stdio.h>
#include<math.h>
void elect(int x)
{
printf("逆序输出");
float k = 0.1;
int m = 0;
do
{
m = x % 10;
k = k * 10;
printf("%d是%f位",m,k);
x = x / 10;
if (x < 9)
{
k = k * 10;
printf("%d是%f位", m, k);
break;
}
} while (1);
printf("\n \n");
}
void elect2(int x)
{
printf("顺序输出");
int digit = log10(x) ;
int i = 0;
int m = 0;
for (i = pow(10, digit); i >0; i = i / 10)
{
m = x / i;
printf("%d ", m);
x = x % i;
}
}
int main()
{
int k = 0;
scanf("%d", &k);
//elect(k);
elect2(k);
return 0;
}
|
递归解法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#define _crt_secure_no_warnings
#include<stdio.h>
void elect(int x)
{
if (x > 9)
{
elect(x / 10); //递归体 通过除以10 来使得问题更接近正确答案
}
printf("%d ", x % 10);//出口
}
int main()
{
int k = 0;
scanf("%d", &k);
elect(k);
return 0;
}
|
倒序保存字符串
将参数字符串中的字符反向排列，不是逆序打印
递归解法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#define _crt_secure_no_warnings
#include<stdio.h>
#include<math.h>
#include<stdio.h>
#include<string.h>
void reverse_string(char arr[])
{
int sz = strlen(arr);
int tmp = *arr;
*arr = *(arr + sz - 1); //将最后一个和第一个互换
*(arr + sz - 1) = '\0';// 将最后一个赋值为0
if (strlen(arr) > 1)//如果不是最后一个则 指针后移
{
reverse_string(arr + 1);
}
*(arr + sz - 1) = tmp;
}
int main()
{
char arr[] = "abcdef";
reverse_string(arr);
printf("%s\n", arr);
}
|
总结
到此这篇关于c语言递归系列的文章就介绍到这了,更多相关c语言递归内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/qq_45849625/article/details/113060354