>> ZAMYLA: เพื่อให้เข้าใจ เรียกซ้ำคุณต้อง
แรกเข้าใจเรียกซ้ำ
มีการเรียกซ้ำในโปรแกรมการออกแบบ ว่าคุณมีตัวอ้างอิง
คำจำกัดความ
ข้อมูลซ้ำโครงสร้างเช่น เป็นโครงสร้างข้อมูลที่
รวมถึงตัวเองใน คำจำกัดความของพวกเขา
แต่วันนี้เรากำลังจะมุ่งเน้น ในการทำงานซ้ำ
>> จำได้ว่าฟังก์ชั่นใช้ปัจจัย ข้อโต้แย้งและคืนค่าเป็นของพวกเขา
เอาท์พุทที่แสดงโดย แผนภาพนี้ที่นี่
เราจะคิดจากกล่องในขณะที่ร่างกายของ ฟังก์ชั่นที่มีชุดของ
คำสั่งที่ตีความ นำเข้าและส่งออกให้
การมองใกล้ภายในร่างกายของ ฟังก์ชั่นสามารถเปิดเผยโทรไป
ฟังก์ชั่นอื่น ๆ ได้เป็นอย่างดี
ใช้ฟังก์ชั่นแบบนี้ foo ที่ ใช้สายเดียวที่นำเข้าและ
พิมพ์ตัวอักษรหลายวิธี สตริงที่มี
strlen ฟังก์ชั่นสำหรับความยาวสตริง เรียกว่าเอาท์พุทเป็น
ที่จำเป็นสำหรับการเรียก printf
>> ตอนนี้สิ่งที่ทำให้การทำงานซ้ำ พิเศษคือว่ามันเรียกตัวเอง
เราสามารถเป็นตัวแทนของซ้ำนี้ เรียกที่มีลูกศรสีส้มนี้
วนลูปกลับไปที่ตัวเอง
แต่การดำเนินงานตัวเองอีกครั้งจะมีเพียง ให้โทรซ้ำอีกและ
อื่นและอื่น
แต่ฟังก์ชั่นซ้ำ ไม่สามารถที่จะไม่มีที่สิ้นสุด
พวกเขาต้องจบอย่างใดหรือของคุณ โปรแกรมจะทำงานตลอด
>> ดังนั้นเราจึงจำเป็นที่จะหาทางที่จะทำลาย ออกจากการโทรซ้ำ
เราเรียกสิ่งนี้ว่ากรณีฐาน
เมื่อเงื่อนไขกรณีฐานจะพบ ฟังก์ชั่นส่งกลับโดยไม่ต้องทำ
โทรซ้ำอีก
ใช้ฟังก์ชันนี้ hi ฟังก์ชั่นเป็นโมฆะ ที่ใช้เวลา int n เป็นอินพุท
กรณีฐานมาก่อน
ถ้า n มีค่าน้อยกว่าศูนย์การพิมพ์และลาก่อน กลับสำหรับกรณีอื่น ๆ ทั้งหมด
ฟังก์ชั่นจะพิมพ์ hi และดำเนินการ โทรซ้ำ
สายอื่นที่จะทำงาน hi ด้วย ค่าเข้า decremented
>> ตอนนี้แม้ว่าเราจะพิมพ์สวัสดี ฟังก์ชั่นจะไม่ยุติจนกว่าเราจะ
กลับพิมพ์กลับของ ในกรณีนี้เป็นโมฆะ
ดังนั้นสำหรับทุก n อื่น ๆ กว่ากรณีฐาน ฟังก์ชั่นนี้จะกลับ hi hi
ของ n ลบ 1
ตั้งแต่ฟังก์ชั่นนี้จะถือเป็นโมฆะ แต่เรา จะไม่กลับมาอย่างชัดเจนชนิดที่นี่
เราก็จะดำเนินการฟังก์ชั่น
ดังนั้นการเรียก hi (3) จะพิมพ์ hi และ hi ดำเนินการ (2) ที่รัน hi (1) อย่างใดอย่างหนึ่ง
ที่รัน hi (0), ที่ เงื่อนไขกรณีฐานจะพบ
ดังนั้น hi (0) ลาก่อนพิมพ์และผลตอบแทนที่
>> ตกลง
ดังนั้นขณะนี้ที่เราเข้าใจพื้นฐานของ ฟังก์ชั่นซ้ำที่พวกเขาต้องการ
กรณีฐานอย่างน้อยหนึ่งเช่นเดียวกับที่ โทรซ้ำให้ย้ายไป
ตัวอย่างเช่นความหมายมากขึ้น
หนึ่งที่ไม่ได้เพียงแค่กลับมา เป็นโมฆะไม่ว่าสิ่งที่
>> ลองมาดูที่ปัจจัย การดำเนินงานที่ใช้กันมากที่สุดใน
การคำนวณความน่าจะเป็น
ปัจจัยของ n เป็นผลิตภัณฑ์ของทุก จำนวนเต็มบวกน้อยกว่า
และเท่ากับ n
ดังนั้นปัจจัยที่ห้าคือ 5 ครั้ง 4 ครั้ง 3 ครั้ง 2 ครั้งที่ 1 เพื่อให้ 120
สี่ปัจจัยคือ 4 ครั้ง 3 ครั้ง 2 ครั้งที่ 1 เพื่อให้ 24
และกฎเดียวกันกับ เป็นจำนวนเต็มบวกใด ๆ
>> ดังนั้นวิธีที่เราอาจจะเขียนซ้ำ ฟังก์ชั่นที่คำนวณปัจจัย
จำนวน?
ดีเราจะต้องระบุทั้ง กรณีฐานและโทรซ้ำ
โทรซ้ำจะเหมือนกัน ทุกกรณียกเว้นสำหรับฐาน
กรณีซึ่งหมายความว่าเราจะต้อง หารูปแบบที่จะทำให้เรามีของเรา
ผลลัพธ์ที่ต้องการ
>> ตัวอย่างเช่นนี้ดูว่า 5 ปัจจัย ที่เกี่ยวข้องกับการคูณ 4 3 2 1
และที่คูณเดียวกันมาก ถูกพบที่นี่
4 นิยามของปัจจัย
ดังนั้นเราจะเห็นว่า 5 ปัจจัยคือ เพียงแค่ 5 ครั้งที่ 4 ปัจจัย
ตอนนี้ไม่ใช้รูปแบบนี้ 4 ปัจจัยด้วยหรือไม่
ใช่
เราจะเห็นว่ามี 4 ปัจจัย คูณ 3 คูณ 2 คูณ 1
คำนิยามเดียวกันมากเป็น 3 ปัจจัย
ดังนั้นปัจจัย 4 เท่ากับ 4 ครั้งที่ 3 ปัจจัยและอื่น ๆ และอื่น ๆ ของเรา
รูปแบบเกาะติดจนถึง 1 ปัจจัยที่ โดยมีความหมายเท่ากับ 1
>> ไม่มีการบวกอื่น ๆ จำนวนเต็มซ้าย
ดังนั้นเราจึงมีรูปแบบสำหรับ โทรซ้ำของเรา
n ปัจจัยเท่ากับ n ครั้ง ปัจจัยของ n ลบ 1
และกรณีฐานของเราหรือไม่
ที่เพิ่งจะนิยามของเรา 1 ปัจจัย
>> ดังนั้นตอนนี้เราสามารถไปยังการเขียน สำหรับฟังก์ชั่น
สำหรับกรณีฐานเราจะมี สภาพ n เท่ากับ 1 เท่ากับที่
เราจะกลับมาที่ 1
แล้วย้ายไปยังโทรซ้ำ, เราจะกลับมาครั้ง n
ปัจจัยของ n ลบ 1
>> ตอนนี้ขอทดสอบนี้ของเรา
ลองปัจจัย 4
ต่อการทำงานของเราก็เท่ากัน ถึง 4 ครั้งปัจจัย (3)
ปัจจัย (3) มีค่าเท่ากับ 3 ครั้งปัจจัย (2)
ปัจจัย (2) มีค่าเท่ากับ 2 ครั้ง ปัจจัย (1) ซึ่งผลตอบแทนที่ 1
ปัจจัย (2) ตอนนี้กลับมาครั้งที่ 2 1, 2
ปัจจัย (3) ตอนนี้สามารถกลับ 3 ครั้งที่ 2, 6
และสุดท้ายปัจจัย (4) ผลตอบแทนที่ 4 ครั้งที่ 6, 24
>> หากคุณพบปัญหาใด ๆ ด้วยการโทรซ้ำ, แกล้งทำเป็นว่า
ฟังก์ชั่นการทำงานอยู่แล้ว
สิ่งที่ผมหมายถึงนี้คือการที่คุณควร ไว้วางใจเรียก recursive ของคุณเพื่อกลับ
ค่าที่ถูกต้อง
ตัวอย่างเช่นถ้าฉันรู้ว่า ปัจจัย (5) เท่ากับ 5 ครั้ง
ปัจจัย (4) ฉันจะให้ความไว้วางใจว่า ปัจจัย (4) จะให้ฉัน 24
คิดว่ามันเป็นตัวแปรถ้าคุณ จะเป็นถ้าคุณกำหนดไว้แล้ว
ปัจจัย (4)
ดังนั้นสำหรับปัจจัยใด ๆ (n) ก็ ผลิตภัณฑ์ของ n และ
ปัจจัยที่แล้ว
และปัจจัยที่แล้วนี้ ได้มาจากการเรียกร้อง
ปัจจัยของ n ลบ 1
>> ตอนนี้ดูว่าคุณสามารถใช้ ตัวเองฟังก์ชั่นซ้ำ
โหลดขึ้นเครื่องของคุณหรือ run.cs50.net, และเขียนผลรวมฟังก์ชั่น
ที่ใช้เวลาจำนวนเต็มและส่งกลับ ผลรวมของติดต่อกันทั้งหมดบวก
จำนวนเต็มจาก n 1
ฉันได้เขียนออกมาจำนวนเงินของบางคน ค่าที่จะช่วยคุณของเรา
ครั้งแรกที่คิดออก เงื่อนไขกรณีฐาน
จากนั้นให้ดูที่ผลรวม (5)
คุณสามารถแสดงมันในแง่ ผลรวมของอื่นได้หรือไม่
ตอนนี้สิ่งที่เกี่ยวกับผลรวม (4)?
วิธีที่คุณสามารถแสดงผลรวม (4) ในแง่ของผลรวมอื่นได้หรือไม่
>> เมื่อคุณมีผลรวม (5) และผลรวม (4) แสดงในแง่ของจำนวนเงินอื่นดู
ถ้าคุณสามารถระบุ รูปแบบการรวม (n)
ถ้าไม่ลองไม่กี่หมายเลขอื่น ๆ และแสดงผลรวมของพวกเขาใน
แง่ของตัวเลขอื่น
โดยการระบุรูปแบบการต่อเนื่อง ตัวเลขคุณจะดีในแบบของคุณกับ
ระบุรูปแบบการ n ใด ๆ
>> เรียกซ้ำเป็นเครื่องมือที่มีประสิทธิภาพจริงๆ ดังนั้นแน่นอนมันไม่ได้ จำกัด อยู่ที่
ฟังก์ชั่นทางคณิตศาสตร์
เรียกซ้ำตัวเองสามารถนำมาใช้อย่างมีประสิทธิภาพ เมื่อจัดการกับต้นไม้เช่น
ตรวจสอบสั้นบนต้นไม้สำหรับ ตรวจสอบอย่างละเอียดมากขึ้น แต่สำหรับตอนนี้
เรียกว่าต้นไม้ค้นหาแบบไบนารีใน โดยเฉพาะอย่างยิ่งได้รับการสร้างขึ้นจากโหนดแต่ละ
ที่มีค่าและสองตัวชี้โหนด
ปกตินี้จะถูกแทนด้วย โหนดแม่มีสายหนึ่งชี้
โหนดลูกด้านซ้ายและเป็นหนึ่งใน ไปยังโหนดลูกที่ถูกต้อง
โครงสร้างของการค้นหาแบบไบนารี ต้นไม้ยืมตัวเองดี
การค้นหาซ้ำ
โทรซ้ำอย่างใดอย่างหนึ่งผ่านไปใน ซ้ายหรือโหนดขวา แต่มากขึ้น
ที่อยู่ในต้นไม้สั้น
>> สมมติว่าคุณต้องการที่จะดำเนินการใน ทุกโหนดเดียวในต้นไม้ไบนารี
วิธีที่คุณอาจจะไปเกี่ยวกับที่
ดีคุณสามารถเขียนซ้ำ ฟังก์ชั่นที่มีประสิทธิภาพการดำเนินงาน
บนโหนดแม่และทำให้ซ้ำ เรียกร้องให้ฟังก์ชั่นเดียวกัน
ผ่านในด้านซ้ายและ ต่อมน้ำเด็กที่เหมาะสม
ตัวอย่างเช่นฟังก์ชั่นนี้ foo ที่ การเปลี่ยนแปลงค่าของโหนดที่กำหนดและ
ทั้งหมดของเด็กถึง 1
กรณีฐานของสาเหตุโหนดโมฆะ ฟังก์ชั่นที่จะกลับมาแสดงให้เห็น
ว่าไม่มีโหนดใด ทิ้งไว้ในที่ sub ต้นไม้
>> ลองเดินผ่านมัน
ผู้ปกครองแรกคือ 13
เราเปลี่ยนค่าเป็น 1 แล้วโทร ฟังก์ชั่นของเราทางด้านซ้ายเช่นกัน
เป็นสิทธิ
ฟังก์ชั่น foo จะเรียกว่าด้านซ้าย sub ต้นไม้แรกดังนั้นโหนดซ้าย
จะได้รับการกำหนดให้ 1 และ foo จะ จะเรียกว่าเด็กของโหนดที่
แรกด้านซ้ายแล้วขวา และอื่น ๆ และอื่น ๆ
และบอกพวกเขาว่าสาขาจะได้ไม่ต้อง เด็ก ๆ มากขึ้นดังนั้นกระบวนการเดียวกัน
จะยังคงเป็นเด็กที่ถูกต้อง จนโหนดต้นไม้ทั้งเป็น
กำหนดให้ 1
>> ในขณะที่คุณสามารถดูคุณจะไม่ จำกัด เพียงหนึ่งโทรซ้ำ
เพียงมากที่สุดเท่าที่จะได้รับงานทำ
สิ่งที่ถ้าคุณมีต้นไม้ที่แต่ละ โหนดมีลูกสามคน
ซ้ายกลางและขวา
วิธีที่คุณจะแก้ไข foo?
ดีง่าย
เพียงแค่เพิ่มอีกโทรซ้ำและ ผ่านในตัวชี้โหนดกลาง
>> เรียกซ้ำจะมีประสิทธิภาพมากและไม่ให้ พูดถึงหรูหรา แต่ก็สามารถเป็น
แนวคิดที่ยากในตอนแรกเพื่อให้ ผู้ป่วยและใช้เวลาของคุณ
เริ่มต้นด้วยกรณีฐาน
ก็มักจะง่ายที่สุดในการระบุ และจากนั้นคุณสามารถทำงานได้
หลังจากที่นั่น
คุณรู้ว่าคุณต้องไปถึงของคุณ กรณีฐานดังนั้นอาจที่
ให้คำแนะนำไม่กี่
พยายามที่จะแสดงกรณีที่เฉพาะเจาะจงอย่างใดอย่างหนึ่งใน แง่ของกรณีอื่น ๆ หรือในชุดย่อย
>> ขอบคุณสำหรับการดูสั้น ๆ นี้
อย่างน้อยตอนนี้คุณสามารถ เข้าใจเรื่องตลกเช่นนี้
ชื่อของฉันคือ Zamyla และนี่คือ CS50
>> ใช้ฟังก์ชันนี้สวัสดี ฟังก์ชั่นเป็นโมฆะว่าจะใช้เวลา
int, n, เป็นอินพุท
กรณีฐานมาก่อน
ถ้า n มีค่าน้อยกว่า 0, พิมพ์ "ลาก่อน" และการกลับมา