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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
| #include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*
1,直接递归，
2，简介递归
使用情况：
1，数据结构本身是递归的，比如链表的类型定义。
2，数学问题：比如汉诺塔问题
3,问题本身是递归问题：比如兔子数列
*/
/*递归模型
1，终止条件：递归出口/确定了什么时候递归结束
2，递归关系：递归体/确定了递归进行的方式
递归的目的：以大化小，直到最简单的问题。
程序化：可以发现，在递归问题中，先出现的数据，到最后才能
得到结果，这正符合了栈的思想：先进后出！
递归工作栈：
*/
/*汉诺塔问题：
1，n ==1，时，直接将盘子移动到B//临界条件
2, n>1,时，将A上的n-1个盘子移动到B，此时C作为过渡
3,用A作为过渡，将B上的n-1个盘子移动到C
4，如此进行，循环往复。
*/
//汉诺塔问题的代码实现
void HanNuoTa(int n, char A, char B, char C)
{
//A是最初的柱子，C是目标柱子
if (n == 1)
printf("MOVE%s ", A, "to %s", C) else
{
HanNuoTa(n - 1, A, C, B);
printf("MOVE %s", A, "to %s", C);
HanNuoTa(n - 1, B, A, C);
}
}
//通过递归计算数组中的最小值
float f(float A[], int i)
{
float m;
if (i == 0) //递归出口
return A[0];
else
{ //递归体：
m = f(A, i - 1); //初值
if (m > A(i)) //判断A[i-1]和A[i]的大小
return A[i];
else //返回两个数中的最小的那个
return m;
}
}
//递归计算结点的个数，链表不带头结点
int count(LNode *L)
{
if (L == NULL) //出口
return 0;
else
return count(L->next) + 1; //递归体
}
//递归输出结点的值
void Travers(LNode *L)
{
if (L == NULL) //出口
return;
printf("%d/t/n", L->data); //递归体
Travers(L->next);
}
//倒序输出单链表结点的值
void TraverseR(LNode *L)
{
if (L == NULL) //出口
return;
//递归体
TraverseR(L->next);
printf("%d/t/n", L->data);
}
//删除以L为首结点的单链表中值为x的第一个结点
void del(LNode *&L, ElemType x)
{
LNode *t;
if (L == NULL)
return;
if (L->data == x) //出口
{ //简单的删除结点的操作
t = L;
L = L->next;
free(t);
return;
}
else //递归体
del(L->next, x);
}
//利用递归删除结点值为x的所有的结点
void delall(LNode *L, ElemType x)
{
LNode *t;
if (L == NULL)
return;
if (L->data == x) //出口
{
t = L;
L = L->next;
delall(L, x);
}
else
delall(L->next, x); //递归体
}
//输出最大值结点
ElemType maxv(LNode *L)
{
ElemType m;
if (L->next == NULL) //出口
return L->data;
m = maxv(L->data);
if (m > L->data) //递归体
return m;
else
return L->data;
}
//输出最小结点值
ElemType minv(LNode *L)
{
ElemType m;
if (L->next == NULL)
return L->data;
m = minv(L->next);
if (m > L->data)
return L->data;
else
return m;
}
|