1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Jika anda lihat
video di rekursi,

3
00:00:07,670 --> 00:00:10,170
keseluruhan proses mungkin mempunyai
seolah-olah sedikit ajaib.

4
00:00:10,170 --> 00:00:10,930
Bagaimanakah ia berfungsi?

5
00:00:10,930 --> 00:00:15,010
Bagaimana fungsi tahu bahawa mereka
perlu menunggu dan menunggu nilai lain

6
00:00:15,010 --> 00:00:19,150
untuk kembali dari fungsi yang berbeza
memanggil untuk mendapatkan hasil yang kita mahu?

7
00:00:19,150 --> 00:00:22,550
>> Nah, sebab kerja-kerja ini adalah kerana
sesuatu yang dikenali sebagai timbunan panggilan.

8
00:00:22,550 --> 00:00:26,360
Apabila anda memanggil fungsi, yang
sistem mengetepikan ruang dalam ingatan

9
00:00:26,360 --> 00:00:28,120
untuk fungsi bahawa untuk melakukan tugasnya.

10
00:00:28,120 --> 00:00:31,720
Dan kita panggil ketulan memori yang
sedang diketepikan untuk setiap fungsi

11
00:00:31,720 --> 00:00:35,670
memanggil bingkai tindanan atau bingkai fungsi.

12
00:00:35,670 --> 00:00:38,290
Dan seperti yang anda jangkakan,
bingkai tindanan

13
00:00:38,290 --> 00:00:41,000
tinggal di pihak timbunan memori.

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

15
00:00:43,960 --> 00:00:47,540
>> Lebih daripada satu fungsi bingkai tindanan
boleh wujud dalam memori pada masa yang diberikan.

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

17
00:00:51,240 --> 00:00:54,460
ketiga-tiga fungsi mempunyai bingkai terbuka.

18
00:00:54,460 --> 00:00:57,350
Tetapi mereka tidak semua mempunyai bingkai aktif.

19
00:00:57,350 --> 00:00:59,410
Ini bingkai disusun dalam timbunan.

20
00:00:59,410 --> 00:01:01,820
Dan kerangka dari
Yang baru dipanggil

21
00:01:01,820 --> 00:01:04,390
fungsi adalah sentiasa di atas timbunan.

22
00:01:04,390 --> 00:01:07,150
Dan yang sentiasa bingkai aktif.

23
00:01:07,150 --> 00:01:10,420
Terdapat hanya benar-benar pernah satu
fungsi itulah yang aktif pada satu masa.

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

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

26
00:01:17,620 --> 00:01:20,590
Ia semacam sedang ditunda, menunggu.

27
00:01:20,590 --> 00:01:24,050
Dan bingkai tindanan lain ditolak
ke dalam tindanan di atasnya.

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

29
00:01:26,150 --> 00:01:28,600
Dan rangka dengan segera
di bawahnya perlu menunggu

30
00:01:28,600 --> 00:01:33,560
sehingga ia sekali lagi bingkai aktif
sebelum ia boleh meneruskan tugasnya.

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

32
00:01:35,870 --> 00:01:37,720
bingkai yang muncul dari timbunan.

33
00:01:37,720 --> 00:01:38,950
Itulah istilah.

34
00:01:38,950 --> 00:01:41,110
Dan rangka dengan segera
di bawahnya, kerana saya hanya berkata,

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

36
00:01:42,880 --> 00:01:45,960
>> Dan jika ia memerlukan fungsi yang lain,
ia akan berhenti seketika lagi.

37
00:01:45,960 --> 00:01:49,290
Bingkai tindanan bahawa fungsi baru akan
dapat ditolak ke bahagian atas timbunan.

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

39
00:01:50,650 --> 00:01:52,100
Ia mungkin pop berundur.

40
00:01:52,100 --> 00:01:55,630
Dan fungsi yang lain
di bawahnya boleh meneruskan lagi.

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

42
00:02:00,080 --> 00:02:03,070
bahawa kita yang ditakrifkan dalam
video rekursi untuk melihat

43
00:02:03,070 --> 00:02:07,770
tepat bagaimana keajaiban di sebalik ini
proses rekursi sedang berlaku.

44
00:02:07,770 --> 00:02:09,870
Jadi ini adalah keseluruhan fail kita, bukan?

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

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

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

48
00:02:18,470 --> 00:02:21,660
>> Oleh itu, kita membuat bingkai tindanan baru untuk utama.

49
00:02:21,660 --> 00:02:23,320
Dan ia 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 5.

52
00:02:29,390 --> 00:02:31,440
Nah, ia tidak tahu
apa faktorial 5 adalah,

53
00:02:31,440 --> 00:02:35,620
dan sebagainya panggilan ini sudah
bergantung kepada panggilan fungsi yang lain.

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

55
00:02:37,270 --> 00:02:39,103
Saya akan meninggalkan mereka
arrow di sana, warna

56
00:02:39,103 --> 00:02:41,360
ia warna yang sama dengan
stack bingkai di sebelah kanan,

57
00:02:41,360 --> 00:02:47,720
untuk menunjukkan bahawa utama akan membekukan
di sini manakala faktorial 5 dipanggil.

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

59
00:02:49,300 --> 00:02:53,160
Dan ia akan mula sekurang-
bermula fungsi faktorial.

60
00:02:53,160 --> 00:02:55,440
Ia meminta soalan aku sama dengan 1?

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

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

63
00:02:57,410 --> 00:03:01,110
Jadi ia akan turun ke
itu pun sebahagian, pulangan n kali

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

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

66
00:03:03,490 --> 00:03:07,070
>> Oleh sebab itu, faktorial 5 adalah
bergantung kepada panggilan lain

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

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

69
00:03:14,210 --> 00:03:17,160
akan membekukan di sana
di garisan yang saya telah dinyatakan

70
00:03:17,160 --> 00:03:21,914
dan tunggu faktorial 4 hingga selesai
apa yang diperlukan untuk berbuat demikian yang maka ia

71
00:03:21,914 --> 00:03:23,330
boleh menjadi bingkai aktif lagi.

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

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

74
00:03:28,556 --> 00:03:30,180
Tidak, jadi ia akan melakukan perkara yang sama.

75
00:03:30,180 --> 00:03:31,590
Ia akan pergi ke cawangan lain.

76
00:03:31,590 --> 00:03:33,240
Ia akan sampai ke baris kod.

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

78
00:03:35,710 --> 00:03:41,270
Oh, faktorial 3-- supaya faktorial
4 bergantung kepada faktorial 3 penamat.

79
00:03:41,270 --> 00:03:43,055
>> Dan jadi ia perlu untuk memanggil faktorial 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
Ia bermula melalui, mendapat di sini.

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

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

84
00:03:53,750 --> 00:03:56,310
Ia bergantung kepada faktorial 1.

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

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

87
00:03:57,650 --> 00:03:59,775
Oleh sebab itu, kami mendapat
di suatu tempat yang menarik, bukan?

88
00:03:59,775 --> 00:04:02,190
Oleh sebab itu, 1 adalah sama dengan 1.

89
00:04:02,190 --> 00:04:05,130
Dan supaya kita kembali 1.

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

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

92
00:04:07,880 --> 00:04:11,140
Ia adalah tingkah laku is-- ada
apa-apa lagi untuk itu yang perlu dilakukan,

93
00:04:11,140 --> 00:04:17,006
dan sebagainya bingkai tindanan untuk
faktorial 1 timbul di luar.

94
00:04:17,006 --> 00:04:17,589
Ia selesai.

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

96
00:04:19,480 --> 00:04:23,370
Dan kini, faktorial 2, yang
adalah bingkai segera di bawahnya

97
00:04:23,370 --> 00:04:26,160
dalam tindanan, menjadi bingkai aktif.

98
00:04:26,160 --> 00:04:29,030
>> Dan ia boleh mengambil
tepat di mana ia berhenti.

99
00:04:29,030 --> 00:04:32,240
Ia telah menunggu Faktorial
daripada 1 untuk menyelesaikan tugasnya.

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

101
00:04:33,610 --> 00:04:35,510
Dan sebagainya 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 tin
katakan kembali 2 kali 1.

104
00:04:42,430 --> 00:04:43,680
Tugasnya kini dilakukan.

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

106
00:04:49,110 --> 00:04:53,370
Faktorial 3 kini bingkai atas,
bingkai aktif dalam timbunan.

107
00:04:53,370 --> 00:04:58,617
Dan maka ia berkata, OK, baik, saya akan
untuk kembali 3 kali 2, iaitu 6.

108
00:04:58,617 --> 00:05:00,700
Dan saya 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
Aku selesai.

111
00:05:04,500 --> 00:05:09,410
Faktorial 3 muncul dari timbunan, dan
faktorial 4 kini bingkai aktif.

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

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

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

115
00:05:19,010 --> 00:05:20,990
Dan saya akan lulus
kembali bahawa untuk faktorial

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

117
00:05:23,160 --> 00:05:25,270
Faktorial 5 kini bingkai aktif.

118
00:05:25,270 --> 00:05:30,700
Ia 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 mempunyai

120
00:05:32,722 --> 00:05:35,680
telah menunggu sangat sabar untuk
masa yang lama di bahagian bawah timbunan.

121
00:05:35,680 --> 00:05:36,640
>> Ia adalah di mana ia bermula.

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

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

124
00:05:39,400 --> 00:05:41,890
Ia kini kembali di atas timbunan.

125
00:05:41,890 --> 00:05:43,450
Ia bingkai 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
Ia telah menunggu untuk
mencetak nilai itu.

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

129
00:05:51,657 --> 00:05:53,240
Tidak ada yang lebih baris kod dalam utama.

130
00:05:53,240 --> 00:05:56,800
Jadi kerangka utama yang timbul daripada
timbunan, dan kami sudah selesai.

131
00:05:56,800 --> 00:05:58,992
>> Dan itulah bagaimana rekursi berfungsi.

132
00:05:58,992 --> 00:06:00,200
Itulah bagaimana bingkai tindanan bekerja.

133
00:06:00,200 --> 00:06:03,120
Mereka panggilan fungsi
yang berlaku sebelum ini

134
00:06:03,120 --> 00:06:06,620
hanyalah pada jeda, menunggu
untuk panggilan seterusnya

135
00:06:06,620 --> 00:06:12,050
untuk menyelesaikan supaya mereka boleh menjadi aktif
merangka dan menyelesaikan apa yang mereka perlu lakukan.

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

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

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