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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
Doug LLOYD: Jika Anda pernah melihat
video di rekursi,

3
00:00:07,670 --> 00:00:10,170
seluruh proses mungkin memiliki
tampak sedikit ajaib.

4
00:00:10,170 --> 00:00:10,930
Bagaimana cara kerjanya?

5
00:00:10,930 --> 00:00:15,010
Bagaimana fungsi tahu bahwa mereka
harus menunggu dan menunggu untuk nilai lain

6
00:00:15,010 --> 00:00:19,150
untuk kembali dari fungsi yang berbeda
panggilan untuk mendapatkan hasil yang kita inginkan?

7
00:00:19,150 --> 00:00:22,550
>> Nah, alasan ini bekerja karena
dari sesuatu yang dikenal sebagai panggilan stack.

8
00:00:22,550 --> 00:00:26,360
Ketika Anda memanggil fungsi, yang
Sistem menyisihkan ruang di memori

9
00:00:26,360 --> 00:00:28,120
untuk fungsi yang melakukan pekerjaannya.

10
00:00:28,120 --> 00:00:31,720
Dan kita sebut potongan ini memori yang
sedang disisihkan untuk setiap fungsi

11
00:00:31,720 --> 00:00:35,670
sebut stack frame atau bingkai fungsi.

12
00:00:35,670 --> 00:00:38,290
Dan seperti yang Anda harapkan,
tumpukan frame ini

13
00:00:38,290 --> 00:00:41,000
hidup di tumpukan bagian dari memori.

14
00:00:41,000 --> 00:00:43,960

15
00:00:43,960 --> 00:00:47,540
>> Lebih dari satu fungsi stack frame
bisa ada di memori pada waktu tertentu.

16
00:00:47,540 --> 00:00:51,240
Jika utama panggilan langkah fungsi,
dan bergerak panggilan arah,

17
00:00:51,240 --> 00:00:54,460
semua tiga fungsi memiliki frame terbuka.

18
00:00:54,460 --> 00:00:57,350
Tapi mereka tidak semua memiliki frame yang aktif.

19
00:00:57,350 --> 00:00:59,410
Frame ini disusun dalam tumpukan.

20
00:00:59,410 --> 00:01:01,820
Dan frame dari
yang terakhir disebut

21
00:01:01,820 --> 00:01:04,390
Fungsi selalu di atas tumpukan.

22
00:01:04,390 --> 00:01:07,150
Dan yang selalu frame aktif.

23
00:01:07,150 --> 00:01:10,420
Hanya ada benar-benar pernah satu
Fungsi yang aktif pada suatu waktu.

24
00:01:10,420 --> 00:01:12,420
Ini adalah salah satu di atas tumpukan.

25
00:01:12,420 --> 00:01:17,620
>> Ketika fungsi panggilan lain
fungsi, itu semacam menekan jeda.

26
00:01:17,620 --> 00:01:20,590
Hal semacam ini ditahan, menunggu.

27
00:01:20,590 --> 00:01:24,050
Dan stack frame lain didorong
ke tumpukan di atasnya.

28
00:01:24,050 --> 00:01:26,150
Dan yang menjadi frame yang aktif.

29
00:01:26,150 --> 00:01:28,600
Dan frame segera
bawah perlu menunggu

30
00:01:28,600 --> 00:01:33,560
sampai lagi frame aktif
sebelum dapat melanjutkan pekerjaannya.

31
00:01:33,560 --> 00:01:35,870
Ketika fungsi adalah
lengkap dan itu dilakukan,

32
00:01:35,870 --> 00:01:37,720
frame yang muncul dari tumpukan.

33
00:01:37,720 --> 00:01:38,950
Itu terminologi.

34
00:01:38,950 --> 00:01:41,110
Dan frame segera
bawahnya, karena saya hanya berkata,

35
00:01:41,110 --> 00:01:42,880
menjadi frame yang aktif baru.

36
00:01:42,880 --> 00:01:45,960
>> Dan jika panggilan fungsi lain,
itu akan berhenti lagi.

37
00:01:45,960 --> 00:01:49,290
Bahwa fungsi baru stack frame akan
didorong ke atas tumpukan.

38
00:01:49,290 --> 00:01:50,650
Ini akan melakukan tugasnya.

39
00:01:50,650 --> 00:01:52,100
Mungkin pop kembali off.

40
00:01:52,100 --> 00:01:55,630
Dan fungsi lainnya
bawah itu dapat melanjutkan lagi.

41
00:01:55,630 --> 00:02:00,080
>> Jadi mari kita pergi melalui ini lagi, mencari
pada gagasan fungsi faktorial

42
00:02:00,080 --> 00:02:03,070
bahwa kita ditetapkan dalam
rekursi Video untuk melihat

43
00:02:03,070 --> 00:02:07,770
persis bagaimana keajaiban di balik ini
Proses rekursif berlangsung.

44
00:02:07,770 --> 00:02:09,870
Jadi ini adalah seluruh file kita, kan?

45
00:02:09,870 --> 00:02:14,000
Kami mendefinisikan dua
functions-- utama dan fakta.

46
00:02:14,000 --> 00:02:15,980
Dan seperti yang kita harapkan,
program C akan

47
00:02:15,980 --> 00:02:18,470
untuk memulai pada baris pertama utama.

48
00:02:18,470 --> 00:02:21,660
>> Jadi kita membuat stack frame baru untuk utama.

49
00:02:21,660 --> 00:02:23,320
Dan itu akan mulai berjalan.

50
00:02:23,320 --> 00:02:25,270
Panggilan utama printf.

51
00:02:25,270 --> 00:02:29,390
Dan printf akan
mencetak faktorial dari 5.

52
00:02:29,390 --> 00:02:31,440
Yah, itu tidak tahu
apa faktorial dari 5 adalah,

53
00:02:31,440 --> 00:02:35,620
dan panggilan ini sudah
tergantung pada panggilan fungsi lain.

54
00:02:35,620 --> 00:02:37,270
Jadi utama akan berhenti di sana.

55
00:02:37,270 --> 00:02:39,103
Aku akan meninggalkan nya
panah di sana, warna

56
00:02:39,103 --> 00:02:41,360
itu warna yang sama sebagai
tumpukan bingkai di sebelah kanan,

57
00:02:41,360 --> 00:02:47,720
untuk menunjukkan bahwa utama akan membekukan
di sini sementara faktorial dari 5 disebut.

58
00:02:47,720 --> 00:02:49,300
>> Jadi faktorial dari 5 disebut.

59
00:02:49,300 --> 00:02:53,160
Dan itu akan mulai sangat
mulai dari fungsi faktorial.

60
00:02:53,160 --> 00:02:55,440
Ini meminta pertanyaan saya sama dengan 1?

61
00:02:55,440 --> 00:02:56,810
Apakah 5 sama dengan 1?

62
00:02:56,810 --> 00:02:57,410
Nah, tidak ada.

63
00:02:57,410 --> 00:03:01,110
Jadi itu akan pergi ke
yang lain bagian, kembali n kali

64
00:03:01,110 --> 00:03:02,990
faktorial dari n minus 1.

65
00:03:02,990 --> 00:03:03,490
Baiklah.

66
00:03:03,490 --> 00:03:07,070
>> Jadi sekarang, faktorial 5 adalah
tergantung pada panggilan lain

67
00:03:07,070 --> 00:03:09,740
untuk faktorial, melewati
di 4 sebagai parameter.

68
00:03:09,740 --> 00:03:14,210
Dan faktorial dari
5 bingkai, frame merah,

69
00:03:14,210 --> 00:03:17,160
akan membekukan di sana
pada baris yang saya ditunjukkan

70
00:03:17,160 --> 00:03:21,914
dan menunggu faktorial 4 untuk menyelesaikan
apa yang perlu dilakukan agar kemudian

71
00:03:21,914 --> 00:03:23,330
dapat menjadi frame aktif kembali.

72
00:03:23,330 --> 00:03:26,890
>> Jadi faktorial dari 4 dimulai pada
awal faktorial.

73
00:03:26,890 --> 00:03:28,556
Adalah 4 sama dengan 1?

74
00:03:28,556 --> 00:03:30,180
Tidak ada, jadi itu akan melakukan hal yang sama.

75
00:03:30,180 --> 00:03:31,590
Ini akan turun cabang lain.

76
00:03:31,590 --> 00:03:33,240
Ini akan mendapatkan bahwa baris kode.

77
00:03:33,240 --> 00:03:35,710
OK, aku akan kembali empat kali.

78
00:03:35,710 --> 00:03:41,270
Oh, faktorial 3-- sehingga faktorial dari
4 tergantung pada faktorial dari 3 finishing.

79
00:03:41,270 --> 00:03:43,055
>> Dan sehingga perlu untuk memanggil faktorial dari 3.

80
00:03:43,055 --> 00:03:45,180
Dan itu akan pergi melalui
proses yang sama lagi.

81
00:03:45,180 --> 00:03:48,200
Dimulai melalui, tiba di sini.

82
00:03:48,200 --> 00:03:50,980
Faktorial 3 tergantung
pada faktorial 1.

83
00:03:50,980 --> 00:03:53,750
Jadi faktorial 2 dimulai, tiba di sini.

84
00:03:53,750 --> 00:03:56,310
Hal ini tergantung pada faktorial dari 1.

85
00:03:56,310 --> 00:03:57,430
Faktorial 1 dimulai.

86
00:03:57,430 --> 00:03:57,650
>> OKE.

87
00:03:57,650 --> 00:03:59,775
Jadi sekarang, kita sudah
suatu tempat yang menarik, bukan?

88
00:03:59,775 --> 00:04:02,190
Jadi sekarang, 1 sama dengan 1.

89
00:04:02,190 --> 00:04:05,130
Dan jadi kami kembali 1.

90
00:04:05,130 --> 00:04:06,770
Pada titik ini, kami akan kembali.

91
00:04:06,770 --> 00:04:07,880
Fungsi dilakukan.

92
00:04:07,880 --> 00:04:11,140
Ini perilaku is-- ada
tidak ada yang lain untuk itu harus dilakukan,

93
00:04:11,140 --> 00:04:17,006
dan stack frame untuk
faktorial 1 muncul dari.

94
00:04:17,006 --> 00:04:17,589
Selesai.

95
00:04:17,589 --> 00:04:19,480
Itu kembali 1.

96
00:04:19,480 --> 00:04:23,370
Dan sekarang, faktorial 2, yang
adalah frame segera bawahnya

97
00:04:23,370 --> 00:04:26,160
dalam tumpukan, menjadi frame yang aktif.

98
00:04:26,160 --> 00:04:29,030
>> Dan dapat mengambil
persis di mana ia tinggalkan.

99
00:04:29,030 --> 00:04:32,240
Sudah menunggu faktorial
dari 1 untuk menyelesaikan pekerjaannya.

100
00:04:32,240 --> 00:04:33,610
Kini telah selesai.

101
00:04:33,610 --> 00:04:35,510
Dan jadi di sini kita.

102
00:04:35,510 --> 00:04:38,080
>> Faktorial 1 kembali nilai 1.

103
00:04:38,080 --> 00:04:42,430
Jadi faktorial 2 kaleng
katakanlah kembali 2 kali 1.

104
00:04:42,430 --> 00:04:43,680
Pekerjaannya sekarang dilakukan.

105
00:04:43,680 --> 00:04:49,110
Ini kembali ke faktorial 2
dari 3, yang sedang menunggu untuk itu.

106
00:04:49,110 --> 00:04:53,370
Faktorial 3 sekarang frame atas,
frame aktif dalam stack.

107
00:04:53,370 --> 00:04:58,617
Dan ia mengatakan, OK, baik, aku akan
untuk kembali 3 kali 2, yang adalah 6.

108
00:04:58,617 --> 00:05:00,700
Dan aku akan memberikan yang
menghargai kembali ke faktorial

109
00:05:00,700 --> 00:05:03,430
4, yang telah menunggu saya.

110
00:05:03,430 --> 00:05:04,500
Saya selesai.

111
00:05:04,500 --> 00:05:09,410
Faktorial 3 muncul dari tumpukan, dan
faktorial 4 sekarang frame aktif.

112
00:05:09,410 --> 00:05:13,510
>> 4 mengatakan, OK, aku akan kembali 4 kali
faktorial dari 3, yang enam.

113
00:05:13,510 --> 00:05:15,980
Itu nilai yang
faktorial 3 kembali.

114
00:05:15,980 --> 00:05:19,010
Dan 4 kali 6 adalah 24.

115
00:05:19,010 --> 00:05:20,990
Dan aku akan lulus
yang kembali ke faktorial

116
00:05:20,990 --> 00:05:23,160
dari 5, yang telah menunggu saya.

117
00:05:23,160 --> 00:05:25,270
Faktorial dari 5 sekarang frame aktif.

118
00:05:25,270 --> 00:05:30,700
Ini akan kembali 5 kali
faktorial 4-- 5 kali 24, atau 120--

119
00:05:30,700 --> 00:05:32,722
dan memberikan nilai yang
kembali ke utama, yang memiliki

120
00:05:32,722 --> 00:05:35,680
telah menunggu sangat sabar untuk
lama di bagian bawah tumpukan.

121
00:05:35,680 --> 00:05:36,640
>> Ini di mana ia mulai.

122
00:05:36,640 --> 00:05:37,670
Hal itu membuat panggilan ini.

123
00:05:37,670 --> 00:05:39,400
Beberapa frame mengambil alih di bagian atas.

124
00:05:39,400 --> 00:05:41,890
Sekarang kembali di atas tumpukan.

125
00:05:41,890 --> 00:05:43,450
Ini frame yang aktif.

126
00:05:43,450 --> 00:05:47,810
Jadi utama mendapat nilai 120
kembali dari faktorial 5.

127
00:05:47,810 --> 00:05:50,750
Sudah menunggu untuk
mencetak nilai tersebut.

128
00:05:50,750 --> 00:05:51,657
Dan kemudian hal itu dilakukan.

129
00:05:51,657 --> 00:05:53,240
Tidak ada garis yang lebih kode di utama.

130
00:05:53,240 --> 00:05:56,800
Jadi bingkai utama muncul dari
stack, dan kami sudah selesai.

131
00:05:56,800 --> 00:05:58,992
>> Dan itulah cara rekursi bekerja.

132
00:05:58,992 --> 00:06:00,200
Begitulah cara tumpukan frame bekerja.

133
00:06:00,200 --> 00:06:03,120
Mereka fungsi panggilan
yang terjadi sebelumnya

134
00:06:03,120 --> 00:06:06,620
hanya pada jeda, menunggu
untuk panggilan berikutnya

135
00:06:06,620 --> 00:06:12,050
untuk menyelesaikan sehingga mereka dapat menjadi aktif
bingkai dan menyelesaikan apa yang harus mereka lakukan.

136
00:06:12,050 --> 00:06:13,060
>> Aku Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Ini adalah CS50.

138
00:06:14,880 --> 00:06:16,580