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
무효 함수에게, 안녕,이 기능을
그 입력으로 INT 해당됩니다.

31
00:01:39,610 --> 00:01:41,260
기본 케이스가 먼저 온다.

32
00:01:41,260 --> 00:01:46,220
N이 0보다 작은 경우, 인쇄 안녕과 경우
다른 모든 경우 반환

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) 하나의 안녕을 실행하는 실행

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
>> OK.

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 계승 참조
1 2 3 4를 곱 포함

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,
및 함수 합 쓰기

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
NULL 노드 원인의 기본 케이스
기능을 나타내는 돌아갑니다

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
어떻게 foo는 편집까요?

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