1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA：为了了解
递归，你必须

3
00:00:10,190 --> 00:00:13,820
先了解递归。

4
00:00:13,820 --> 00:00:17,280
在程序设计方法有递归
你有自我指涉

5
00:00:17,280 --> 00:00:18,570
的定义。

6
00:00:18,570 --> 00:00:21,520
递归数据结构，例如，
是数据结构

7
00:00:21,520 --> 00:00:23,990
包括自己
它们的定义。

8
00:00:23,990 --> 00:00:27,160
但是今天，我们要集中
在递归函数。

9
00:00:27,160 --> 00:00:31,160
>> 回想一下，函数需要的投入，
参数，并返回一个值作为其

10
00:00:31,160 --> 00:00:34,480
表示为输出
此图在这里。

11
00:00:34,480 --> 00:00:38,060
我们想想盒子作为身体
的功能，包含该组

12
00:00:38,060 --> 00:00:42,340
该解释的说明
输入和提供输出。

13
00:00:42,340 --> 00:00:45,660
以身体内部一探究竟
该功能可以显示来电

14
00:00:45,660 --> 00:00:47,430
其它功能。

15
00:00:47,430 --> 00:00:51,300
就拿这个简单的函数foo，即
采用单个字符串作为输入，并

16
00:00:51,300 --> 00:00:54,630
打印多少个字母
该字符串了。

17
00:00:54,630 --> 00:00:58,490
该函数strlen函数，字符串长度，
被调用时，它的输出是

18
00:00:58,490 --> 00:01:01,890
所需调用的printf。

19
00:01:01,890 --> 00:01:05,770
>> 现在，是什么让一个递归函数
特别的是，它调用自身。

20
00:01:05,770 --> 00:01:09,610
我们可以代表这个递归
这个橙色箭头打电话

21
00:01:09,610 --> 00:01:11,360
循环返回到自身。

22
00:01:11,360 --> 00:01:15,630
但是，只有再次执行本身会
再拍递归调用，并

23
00:01:15,630 --> 00:01:17,150
其它一个又一个。

24
00:01:17,150 --> 00:01:19,100
但是递归函数
不可能是无限的。

25
00:01:19,100 --> 00:01:23,490
他们必须以某种方式结束，或者你
程序将一直运行下去。

26
00:01:23,490 --> 00:01:27,680
>> 因此，我们需要找到一种方法来打破
出了递归调用的。

27
00:01:27,680 --> 00:01:29,900
我们称之为基本情况。

28
00:01:29,900 --> 00:01:33,570
当满足基本情况的条件，
该函数返回而不进行

29
00:01:33,570 --> 00:01:34,950
另一个递归调用。

30
00:01:34,950 --> 00:01:39,610
借此功能，喜，一个void函数
接受一个int n作为输入。

31
00:01:39,610 --> 00:01:41,260
基本情况是第一位的。

32
00:01:41,260 --> 00:01:46,220
如果n小于零，打印和再见
返回对于所有其他情况下，

33
00:01:46,220 --> 00:01:49,400
功能将打印喜和执行
递归调用。

34
00:01:49,400 --> 00:01:53,600
另一个函数调用喜
一个递减的输入值。

35
00:01:53,600 --> 00:01:56,790
>> 现在，即使我们打印嗨，
函数将不会终止，直到我们

36
00:01:56,790 --> 00:02:00,370
返回它的返回类型，
在这种情况下无​​效。

37
00:02:00,370 --> 00:02:04,830
因此，对每一个n比基本情况外，
这个函数喜将返回喜

38
00:02:04,830 --> 00:02:06,890
的n减1。

39
00:02:06,890 --> 00:02:10,050
由于该功能是无效的，虽然，我们
这里将没有明确的返回类型。

40
00:02:10,050 --> 00:02:12,000
我们只需要执行该函数。

41
00:02:12,000 --> 00:02:16,960
因此调用喜（3）将打印和喜
执行喜（2）执行喜（1）1

42
00:02:16,960 --> 00:02:20,560
它执行喜（0），其中所述
基本情况的条件得到满足。

43
00:02:20,560 --> 00:02:24,100
因此喜（0）打印再见和回报。

44
00:02:24,100 --> 00:02:24,990
>> 确定。

45
00:02:24,990 --> 00:02:28,690
所以，现在我们了解的基本知识
递归函数，它们需要

46
00:02:28,690 --> 00:02:32,730
至少一种碱的情况下，以及一个
递归调用，让我们进入到一个

47
00:02:32,730 --> 00:02:34,120
更有意义的例子。

48
00:02:34,120 --> 00:02:37,830
一个不只是返回
无效不管。

49
00:02:37,830 --> 00:02:41,340
>> 让我们来看看阶乘
最常用于操作

50
00:02:41,340 --> 00:02:43,660
概率计算。

51
00:02:43,660 --> 00:02:48,120
n个阶乘是每一个的产品
比正整数

52
00:02:48,120 --> 00:02:49,400
和等于n。

53
00:02:49,400 --> 00:02:56,731
所以阶乘五是5倍，4倍
3次2次1，得到120。

54
00:02:56,731 --> 00:03:01,400
四阶乘是4倍3倍
2次1给24。

55
00:03:01,400 --> 00:03:04,910
而同样的规则也适用
到任何正整数。

56
00:03:04,910 --> 00:03:08,670
>> 那么我们如何可以写一个递归
函数，计算阶乘

57
00:03:08,670 --> 00:03:09,960
一个数字？

58
00:03:09,960 --> 00:03:14,700
好了，我们就需要确定双方的
基本情况和递归调用。

59
00:03:14,700 --> 00:03:18,250
递归调用是相同的
对于除基地所有情况

60
00:03:18,250 --> 00:03:21,420
情况下，这意味着我们将不得不
找到一个模式，这将赋予我们

61
00:03:21,420 --> 00:03:23,350
期望的结果。

62
00:03:23,350 --> 00:03:30,270
>> 对于这个例子，看看如何5的阶乘
涉及乘以4×3×2×1

63
00:03:30,270 --> 00:03:33,010
而这非常相同的乘法
这里被发现，该

64
00:03:33,010 --> 00:03:35,430
定义4的阶乘。

65
00:03:35,430 --> 00:03:39,810
所以我们看到，5的阶乘是
仅5倍4的阶乘。

66
00:03:39,810 --> 00:03:43,360
现在没有这种模式适用
到4的阶乘呢？

67
00:03:43,360 --> 00:03:44,280
是。

68
00:03:44,280 --> 00:03:49,120
我们看到，4的阶乘包含
乘法3次2次1，则

69
00:03:49,120 --> 00:03:51,590
同样的定义为3的阶乘。

70
00:03:51,590 --> 00:03:56,950
所以4因子等于4倍3
阶乘，等等等等我们

71
00:03:56,950 --> 00:04:02,170
图案坚持，直到1阶乘，这
通过定义等于1。

72
00:04:02,170 --> 00:04:04,950
>> 有没有其他积极
整数离开了。

73
00:04:04,950 --> 00:04:07,870
所以，我们有图案
我们的递归调用。

74
00:04:07,870 --> 00:04:13,260
的n的阶乘等于n倍
n的阶乘减去1。

75
00:04:13,260 --> 00:04:14,370
而我们的基本情况？

76
00:04:14,370 --> 00:04:17,370
这将只是我们的定义
1阶乘。

77
00:04:17,370 --> 00:04:19,995
>> 所以，现在我们可以继续写作
为函数的代码。

78
00:04:19,995 --> 00:04:24,110
对于基本情况，我们将有
条件n等于等于1，其中

79
00:04:24,110 --> 00:04:25,780
我们将返回1。

80
00:04:25,780 --> 00:04:29,280
然后移动到递归调用，
我们将返回n倍

81
00:04:29,280 --> 00:04:32,180
n个阶乘减1。

82
00:04:32,180 --> 00:04:33,590
>> 现在让我们来测试这个我们。

83
00:04:33,590 --> 00:04:35,900
让我们尝试阶乘4。

84
00:04:35,900 --> 00:04:39,420
根据我们的功能是相等的
到4倍阶乘（3）。

85
00:04:39,420 --> 00:04:43,040
阶乘（3）等于
3次阶乘（2）。

86
00:04:43,040 --> 00:04:48,700
阶乘（2）等于2倍
阶乘（1），它返回1。

87
00:04:48,700 --> 00:04:52,490
阶乘（2）现在返回2次1，2。

88
00:04:52,490 --> 00:04:55,960
阶乘（3）现在可以返回
3次2，6。

89
00:04:55,960 --> 00:05:02,490
最后，阶乘（4）
返回4次6，24。

90
00:05:02,490 --> 00:05:06,780
>> 如果你遇到任何困难
用递归调用，假装

91
00:05:06,780 --> 00:05:09,660
该功能的工作原理了。

92
00:05:09,660 --> 00:05:13,450
我的意思是，你应该
相信你的递归调用返回

93
00:05:13,450 --> 00:05:15,100
正确的价值观。

94
00:05:15,100 --> 00:05:18,960
举例来说，如果我知道，
阶乘（5）等于5倍

95
00:05:18,960 --> 00:05:24,870
阶乘（4），我要相信
阶乘（4）会给我24。

96
00:05:24,870 --> 00:05:28,510
把它看成是一个变量，如果你
会，因为如果你已经定义

97
00:05:28,510 --> 00:05:30,070
阶乘（4）。

98
00:05:30,070 --> 00:05:33,850
因此，对于任何阶乘（n）时，它的
n的产物和

99
00:05:33,850 --> 00:05:35,360
以前的阶乘。

100
00:05:35,360 --> 00:05:38,130
而这之前的阶乘
通过调用获得

101
00:05:38,130 --> 00:05:41,330
n个阶乘减1。

102
00:05:41,330 --> 00:05:45,130
>> 现在，看看你是否可以实现
递归函数自己。

103
00:05:45,130 --> 00:05:50,490
加载你的终端，或run.cs50.net，
写一个函数sum

104
00:05:50,490 --> 00:05:54,770
接受一个整数n，并返回
所有连续的正和

105
00:05:54,770 --> 00:05:57,490
整数n到1。

106
00:05:57,490 --> 00:06:01,000
我已经写了一些款项
值，以帮助您我们。

107
00:06:01,000 --> 00:06:04,030
首先，弄清楚
基本情况的条件。

108
00:06:04,030 --> 00:06:06,170
然后，看总和（5）。

109
00:06:06,170 --> 00:06:09,270
你可以在条件表达出来
另一个总和？

110
00:06:09,270 --> 00:06:11,290
现在，大约总和（4）？

111
00:06:11,290 --> 00:06:15,630
你怎么能表达总和（4）
在另一个总和条款？

112
00:06:15,630 --> 00:06:19,655
>> 一旦你有了总和（5）和金额（4）
以其他款项的条款，请参阅

113
00:06:19,655 --> 00:06:22,970
如果你能找出一个
图案总和（N）。

114
00:06:22,970 --> 00:06:26,190
如果没有，请尝试其他一些数字
并表达他们的款项

115
00:06:26,190 --> 00:06:28,410
条款的另一个号码。

116
00:06:28,410 --> 00:06:31,930
通过识别模式的离散
数字，你对你的方式来

117
00:06:31,930 --> 00:06:34,320
识别模式对任意n。

118
00:06:34,320 --> 00:06:38,040
>> 递归是一个非常强大的工具，
所以当然它不是局限于

119
00:06:38,040 --> 00:06:39,820
数学函数。

120
00:06:39,820 --> 00:06:44,040
递归可以非常有效地使用
当树木，例如处理。

121
00:06:44,040 --> 00:06:47,210
检查出的树木短的
更彻底的审查，但现在

122
00:06:47,210 --> 00:06:51,140
记得，二叉搜索树，在
特别地，由节点时，每个

123
00:06:51,140 --> 00:06:53,820
一个值，两个节点的指针。

124
00:06:53,820 --> 00:06:57,270
通常，这是由表示
有一条线指向父节点

125
00:06:57,270 --> 00:07:01,870
给左子节点和一个
右边的子节点。

126
00:07:01,870 --> 00:07:04,510
二进制搜索的结构
树很适合

127
00:07:04,510 --> 00:07:05,940
以递归搜索。

128
00:07:05,940 --> 00:07:09,730
递归调用或者通过在
左或右节点，但更

129
00:07:09,730 --> 00:07:10,950
那树短。

130
00:07:10,950 --> 00:07:15,690
>> 说你要执行一个操作
二叉树的每一个节点。

131
00:07:15,690 --> 00:07:17,410
你将如何着手呢？

132
00:07:17,410 --> 00:07:20,600
好吧，你可以写一个递归
函数来执行该操作

133
00:07:20,600 --> 00:07:24,450
父节点上，使递归
调用相同的功能，

134
00:07:24,450 --> 00:07:27,630
通过在左侧和
右子节点。

135
00:07:27,630 --> 00:07:31,650
例如，这个函数foo，即
改变一个给定的节点的值和

136
00:07:31,650 --> 00:07:33,830
所有的孩子1。

137
00:07:33,830 --> 00:07:37,400
的空节点的原因基本情况
函数返回，表明

138
00:07:37,400 --> 00:07:41,290
有没有任何节点
留在该子树。

139
00:07:41,290 --> 00:07:42,620
>> 让我们通过它。

140
00:07:42,620 --> 00:07:44,340
首先家长是13。

141
00:07:44,340 --> 00:07:47,930
我们将该值更改为1，然后调用
我们在左边的功能以及

142
00:07:47,930 --> 00:07:49,600
如权利。

143
00:07:49,600 --> 00:07:53,910
该函数foo，被称为左
子树的第一个，因此左节点

144
00:07:53,910 --> 00:07:57,730
将被重新分配给1和foo会
被称为该节点的子节点，

145
00:07:57,730 --> 00:08:01,900
第一左，然后右侧
等等，等等。

146
00:08:01,900 --> 00:08:05,630
并告诉他们，分支机构不具有
任何更多的孩子因此同样的过程

147
00:08:05,630 --> 00:08:09,700
将继续为儿童权利
直到整棵树的节点

148
00:08:09,700 --> 00:08:11,430
重新分配到1。

149
00:08:11,430 --> 00:08:15,390
>> 正如你所看到的，你不局限于
到只有一个递归调用。

150
00:08:15,390 --> 00:08:17,930
正如许多如将完成这项工作。

151
00:08:17,930 --> 00:08:21,200
如果你有一棵树，每个
节点有三个孩子，

152
00:08:21,200 --> 00:08:23,100
左，中，右？

153
00:08:23,100 --> 00:08:24,886
你会如何​​编辑富？

154
00:08:24,886 --> 00:08:25,860
好了，简单。

155
00:08:25,860 --> 00:08:30,250
只需添加另一个递归调用和
通过在中间节点指针。

156
00:08:30,250 --> 00:08:34,549
>> 递归是非常强大的，而不是
提到优雅，但它可以是一个

157
00:08:34,549 --> 00:08:38,010
难以理解的概念在第一，所以要
耐心，慢慢来。

158
00:08:38,010 --> 00:08:39,370
从基础案例。

159
00:08:39,370 --> 00:08:42,650
它通常是最容易识别，
然后就可以正常工作

160
00:08:42,650 --> 00:08:43,830
向后从那里。

161
00:08:43,830 --> 00:08:46,190
你知道你需要达到你的
基本情况，这样有可能

162
00:08:46,190 --> 00:08:47,760
给你一些提示。

163
00:08:47,760 --> 00:08:53,120
尝试在表达一种特定的情况下，
其他情况下，还是在子集。

164
00:08:53,120 --> 00:08:54,700
>> 感谢收看这短暂的。

165
00:08:54,700 --> 00:08:58,920
最起码，现在你可以
这样理解的笑话。

166
00:08:58,920 --> 00:09:01,250
我的名字是Zamyla，这是CS50。

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> 借此功能，喜，一
空函数，它接受

169
00:09:07,170 --> 00:09:09,212
一个int n作为输入。

170
00:09:09,212 --> 00:09:11,020
基本情况是第一位的。

171
00:09:11,020 --> 00:09:14,240
如果n小于0时，打印
“再见”和回报。

172
00:09:14,240 --> 00:09:15,490