DOUG LLOYD: ถ้าคุณเคยเห็น วิดีโอเกี่ยวกับการเรียกซ้ำ
กระบวนการทั้งหมดอาจจะมี ดูเหมือนนิด ๆ หน่อย ๆ ที่มีมนต์ขลัง
มันทำงานยังไง?
วิธีการทำงานจะรู้ว่าพวกเขา จำเป็นต้องรอและรอค่าอื่น
จะกลับมาจากที่แตกต่างกันฟังก์ชั่น โทรในการสั่งซื้อเพื่อให้ได้ผลที่เราต้องการหรือไม่
>> ดีเหตุผลที่งานนี้เป็นเพราะ บางสิ่งบางอย่างที่รู้จักกันเป็นกองสาย
เมื่อคุณเรียกฟังก์ชั่นที่ ระบบชุดกันพื้นที่ในหน่วยความจำ
สำหรับฟังก์ชั่นการทำงานที่
และที่เราเรียกว่าชิ้นนี้ของหน่วยความจำที่ มีการตั้งสำรองสำหรับแต่ละฟังก์ชัน
เรียกกองกรอบหรือกรอบการทำงาน
และในขณะที่คุณอาจคาดหวัง เหล่านี้เฟรมสแต็ค
อาศัยอยู่ในส่วนของสแต็คของหน่วยความจำ
>> มากกว่าหนึ่งกองกรอบการทำงาน สามารถอยู่ในความทรงจำในเวลาที่กำหนด
ถ้าสายหลักย้ายฟังก์ชั่น และเรียกร้องให้ย้ายทิศทาง
ทั้งสามฟังก์ชั่นที่มีกรอบการเปิด
แต่พวกเขาไม่ได้ทุกคนมีกรอบการใช้งาน
ภาพเหล่านี้จะถูกจัดให้อยู่ในกอง
และกรอบจากที่ มากที่สุดเมื่อเร็ว ๆ นี้ที่เรียกว่า
ฟังก์ชั่นอยู่เสมอด้านบนของสแต็ค
และที่อยู่เสมอกรอบการใช้งาน
มีเพียงหนึ่งจริงๆเคย ฟังก์ชั่นที่ใช้งานได้ตลอดเวลา
มันเป็นหนึ่งในด้านบนของสแต็ค
>> เมื่อมีการเรียกฟังก์ชั่นอื่น ฟังก์ชั่นการจัดเรียงของมันกดหยุดชั่วคราว
มันคือการจัดเรียงของที่ถือรอ
และกองกรอบอื่นจะถูกผลัก บนสแต็คที่ด้านบนของมัน
และนั่นกลายเป็นกรอบที่ใช้งานอยู่
และกรอบทันที ด้านล่างจะต้องรอ
จนกว่าจะมีกรอบอีกครั้งที่ใช้งาน ก่อนที่จะสามารถดำเนินการต่อการทำงานของมัน
เมื่อฟังก์ชั่นเป็น ที่สมบูรณ์และมันทำ
กรอบของมันจะโผล่ออกกอง
นั่นเป็นคำศัพท์
และกรอบทันที ด้านล่างเป็นฉันเพียงแค่กล่าวว่า
กลายเป็นกรอบใหม่ที่ใช้งาน
>> และถ้ามันเรียกฟังก์ชั่นอื่น ก็จะหยุดการทำงานชั่วคราวอีกครั้ง
กรอบสแต็คที่ฟังก์ชั่นใหม่จะ จะผลักดันไปยังด้านบนของสแต็ค
มันจะทำงานของมัน
มันอาจปรากฏกลับออก
และฟังก์ชั่นอื่น ๆ ด้านล่างจะสามารถกลับมาทำงานอีกครั้ง
>> ถ้าอย่างนั้นเราไปถึงนี้อีกครั้งมอง ที่ความคิดของฟังก์ชั่นแฟกทอ
ที่เรากำหนดไว้ใน วิดีโอเรียกซ้ำเพื่อดู
ว่าวิธีการที่อยู่เบื้องหลังความมหัศจรรย์นี้ ขั้นตอนการเรียกซ้ำที่เกิดขึ้น
ดังนั้นนี่คือไฟล์ทั้งหมดของเราใช่มั้ย?
เรากำหนดสอง functions-- หลักและความเป็นจริง
และในขณะที่เราอาจคาดหวัง โปรแกรม C ใด ๆ ที่เกิดขึ้น
จะเริ่มต้นที่บรรทัดแรกของหลัก
>> ดังนั้นเราจึงสร้างกองกรอบใหม่สำหรับหลัก
และมันก็จะเริ่มทำงาน
สายหลัก printf
และ printf เป็นไป พิมพ์ออกมาจาก 5 ปัจจัย
ดีก็ไม่ทราบ สิ่งที่ปัจจัย 5 คือ
และเพื่อให้การเรียกร้องนี้มีอยู่แล้ว ขึ้นอยู่กับการเรียกใช้ฟังก์ชันอื่น
หลักดังนั้นจะไปหยุดอยู่ที่นั่น
ผมจะปล่อยให้มัน ลูกศรขวามีสี
มันมีสีเดียวกันเป็น สแต็คกรอบด้านขวา
เพื่อแสดงให้เห็นว่าหลักเป็นไปแช่แข็ง ที่นี่ในขณะปัจจัย 5 ที่เรียกว่า
>> ดังนั้นปัจจัย 5 ที่เรียกว่า
และมันจะเริ่มต้นที่มาก เริ่มต้นการทำงานของปัจจัย
มันถามคำถามที่ฉันกำลังเท่ากับ 1
คือ 5 เท่ากับ 1?
ดีไม่มี
ดังนั้นมันจะลงไป ส่วนอื่นกลับ n ครั้ง
ปัจจัยของ n ลบ 1
ดีตกลง
>> ดังนั้นตอนนี้ปัจจัย 5 คือ ขึ้นอยู่กับสายอื่น
ปัจจัยที่จะผ่าน 4 เป็นพารามิเตอร์
ดังนั้นปัจจัยของ 5 กรอบที่กรอบสีแดง
จะไปหยุดอยู่ที่นั่น ที่บรรทัดที่ฉันได้แสดงให้เห็น
และรอปัจจัย 4 ที่จะเสร็จสิ้น สิ่งที่ต้องทำเพื่อที่แล้วมัน
จะกลายเป็นกรอบที่ใช้งานอีกครั้ง
>> ดังนั้นปัจจัย 4 เริ่มต้นที่ จุดเริ่มต้นของปัจจัย
4 เท่ากับ 1?
ไม่เช่นนั้นก็จะทำสิ่งเดียวกัน
มันจะลงไปสาขาอื่น
ก็จะได้รับไปยังบรรทัดของรหัสที่
ตกลงฉันจะกลับมาสี่ครั้ง
โอ้ปัจจัยของ 3-- ดังนั้นปัจจัยของ 4 ขึ้นอยู่กับปัจจัย 3 ตกแต่ง
>> และดังนั้นจึงต้องมีการเรียก factorial 3
และที่จะไปผ่าน กระบวนการเดียวกันอีกครั้ง
มันเริ่มต้นผ่านได้ที่นี่
ปัจจัย 3 ขึ้น ในปัจจัยที่ 1
ดังนั้นปัจจัย 2 เริ่มต้นที่นี่ได้รับ
มันขึ้นอยู่กับปัจจัยที่ 1
ปัจจัยที่ 1 เริ่มต้น
>> ตกลง.
ดังนั้นตอนนี้เราได้รับ ที่ไหนสักแห่งที่น่าสนใจใช่มั้ย?
ดังนั้นตอนนี้ 1 มีค่าเท่ากับ 1
และเพื่อให้เรากลับ 1
ณ จุดนี้เราจะกลับมา
ของทำฟังก์ชั่น
มันเป็นพฤติกรรม is-- มี ไม่มีอะไรมันจะทำ
และเพื่อให้กองกรอบสำหรับ ปัจจัยที่ 1 ปรากฏออก
มันเสร็จ
มันกลับมา 1
และตอนนี้ปัจจัยของ 2 ซึ่ง เป็นกรอบด้านล่างทันที
ในกองกลายเป็นกรอบที่ใช้งานอยู่
>> และมันสามารถรับ ตรงที่มันทิ้งไป
มันได้รับการรอปัจจัย 1 ที่จะเสร็จสิ้นการทำงานของมัน
จะได้ดำเนินการเสร็จสิ้นในขณะนี้
และอื่น ๆ ที่นี่เรามี
>> ปัจจัยที่ 1 กลับค่าเป็น 1
ดังนั้นปัจจัย 2 กระป๋อง กล่าวว่าการกลับมาครั้งที่ 2 1
การทำงานของมันจะทำในขณะนี้
มันกลับ 2 ปัจจัย 3 ซึ่งได้รับการรอให้มัน
ปัจจัย 3 อยู่ในขณะนี้กรอบด้านบน กรอบการใช้งานในกอง
และดังนั้นจึงกล่าวว่าตกลงกันฉันจะ ที่จะกลับมา 3 ครั้งที่ 2 ซึ่งเป็น 6
และฉันจะให้ที่ ค่ากลับไปที่ปัจจัย
4 ซึ่งได้รับการรอคอยสำหรับฉัน
ฉันทำ
ปัจจัย 3 ปรากฏออกมาจาก stack และ ปัจจัย 4 คือตอนนี้กรอบที่ใช้งานอยู่
>> 4 กล่าวว่าตกลงฉันจะกลับมา 4 ครั้ง ปัจจัยใน 3 ซึ่งเป็นหก
นั่นคือของค่าที่ ปัจจัย 3 กลับ
และอื่น ๆ 4 ครั้งที่ 6 คือ 24
และฉันจะผ่าน กลับไปที่ปัจจัย
5 ซึ่งได้รับการรอคอยสำหรับฉัน
ปัจจัย 5 อยู่ในขณะนี้กรอบที่ใช้งานอยู่
มันจะกลับมา 5 ครั้ง ปัจจัยของ 4-- 5 ครั้งที่ 24 หรือ 120--
และให้ค่าที่ กลับไปที่หลักซึ่งมี
รอคอยอย่างอดทนมากสำหรับ เวลานานที่ด้านล่างของสแต็ค
>> มันเป็นเรื่องที่มันเริ่มต้น
มันทำให้สายนี้
หลายเฟรมเข้ามาที่ด้านบน
คือตอนนี้กลับมาอยู่ด้านบนของสแต็ค
มันเป็นกรอบที่ใช้งานอยู่
ดังนั้นหลักมีค่า 120 กลับมาจากปัจจัย 5
จะได้รับการรอคอยที่จะ พิมพ์ค่าที่
และจากนั้นก็ทำ
ไม่มีบรรทัดที่มากขึ้นของรหัสในหลักเป็น
ดังนั้นกรอบหลักของปรากฏออก สแต็คและเรากำลังทำ
>> และนั่นคือวิธีการเรียกซ้ำงาน
นั่นเป็นวิธีที่เฟรมสแต็คทำงาน
ผู้ที่ฟังก์ชั่นการโทร ก่อนหน้านี้ที่เกิดขึ้น
เป็นเพียงเกี่ยวกับการหยุดรอ สำหรับการโทรตามมา
จะเสร็จสิ้นเพื่อให้พวกเขาสามารถกลายเป็นที่ใช้งานอยู่ กรอบและเสร็จสิ้นสิ่งที่พวกเขาต้องทำ
>> ฉันลอยด์ดั๊ก
นี่คือ CS50