การทำความเข้าใจการเรียกซ้ำและสูตรการเรียกซ้ำ

การทำซ้ำ

การทำซ้ำคือการทำซ้ำของกระบวนการ นักเรียนที่ไปโรงเรียนซ้ำขั้นตอนการไปโรงเรียนทุกวันจนกว่าจะสำเร็จการศึกษา เราไปร้านขายของชำอย่างน้อยเดือนละครั้งหรือสองครั้งเพื่อซื้อสินค้า เราทำขั้นตอนนี้ซ้ำทุกเดือน ในทางคณิตศาสตร์ลำดับฟีโบนักชีเป็นไปตามคุณสมบัติของการทำซ้ำงานเช่นกัน ลองพิจารณาลำดับฟีโบนักชีโดยที่ตัวเลขสองตัวแรกคือ 0 และ 1 ตัวเลขอื่น ๆ ทั้งหมดเป็นผลรวมของสองจำนวนก่อนหน้า

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

ขั้นตอนการทำซ้ำ

สูตรฟีโบนักชีสามารถเขียนเป็น

F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
ฟีโบนักชี (2) = ฟีโบนักชี (1) + ฟีโบนักชี (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8

อัลกอริทึมที่ให้ไว้ด้านล่างจะแสดงผลหมายเลขฟีโบนักชีที่ n

การเรียกซ้ำ

ทุกครั้งที่เราได้รับหมายเลข Fibonacci ใหม่ (หมายเลขที่ n) ซึ่งจริงๆแล้วจำนวนที่ n คือ (n - 1) th เมื่อเราพบ (n + 1) th Fibonacci เป็น Fibonacci ตัวถัดไปของเรา ดังที่เราเห็นขั้นตอนการทำซ้ำที่กล่าวถึงข้างต้น: ถ้า n = 2 แล้ว
ฟีโบนักชี (2) = ฟีโบนักชี (2 - 1) + ฟีโบนักชี (2 - 2) = ฟีโบนักชี (1) + ฟีโบนักชี (0) = 1 + 0 = 1

ตอนนี้เราต้องการสร้าง fibonacci (3) นั่นคือ n = 3

ฟีโบนักชี (3) = ฟีโบนักชี (3 - 1) + ฟีโบนักชี (3 - 2) = ฟีโบนักชี (2) + ฟีโบนักชี (1) = 1 + 1 = 2
นั่นหมายความว่าทุกครั้งที่ n จะเพิ่มค่าของ current (n - 1) th และ (n - 2) th fibonacci ก็เพิ่มขึ้นเช่นกัน แต่มันเหนื่อยที่จะต้องติดตาม (n - 1) th และ (n - 2) th fibonacci สำหรับแต่ละ n แล้วการเขียนวิธีการที่เรียกตัวเองให้ทำซ้ำงานซ้ำด้วยตัวเองล่ะ?

เมธอดที่เรียกตัวเองถูกตั้งชื่อเป็นวิธีการเรียกซ้ำ วิธีการเรียกซ้ำต้องมีกรณีพื้นฐานที่โปรแกรมหยุดการเรียกตัวเอง กรณีพื้นฐานสำหรับอนุกรมฟีโบนักชีคือ fibonacci (0) = 0 และ fibonacci (1) = 1 มิฉะนั้นวิธี Fibonacci จะเรียกตัวเองสองครั้ง - fibonacci (n - 1) และ fibonacci (n - 2) จากนั้นจะเพิ่มพวกเขาเพื่อรับ fibonacci (n) วิธีการวนซ้ำสำหรับการค้นหาฟีโบนักชีที่ n สามารถเขียนเป็น -

ถ้าเราดูอย่างถี่ถ้วนการเรียกซ้ำจะเป็นไปตามคุณสมบัติของ stack มันแก้ปัญหาย่อยที่เล็กกว่าเพื่อหาทางแก้ปัญหา สำหรับ n> 1 จะดำเนินการบรรทัดสุดท้าย ดังนั้นถ้า n = 6 ฟังก์ชันจะเรียกและเพิ่ม fibonacci (6 - 1) และ fibonacci (6 - 2) fibonacci (6 - 1) หรือ fibonacci (5) เรียกและเพิ่ม fibonacci (5 - 1) และ fibonacci (5 - 2) การวนซ้ำนี้จะดำเนินต่อไปจนกว่า 6 จะถึงค่าเคสพื้นฐานซึ่งก็คือ fibonacci (0) = 0 หรือ fibonacci (1) = 1 เมื่อมันกระทบเคสพื้นฐานมันจะเพิ่มค่าฐานสองค่าและเพิ่มขึ้นจนกว่าจะได้ค่าของ fibonacci ( 6). ด้านล่างนี้เป็นการแสดงต้นไม้ของการเรียกซ้ำ

ต้นไม้เรียกซ้ำ

อย่างที่เราเห็นว่าการเรียกซ้ำจะทรงพลังเพียงใด โค้ดเพียงบรรทัดเดียวเท่านั้นที่สร้างโครงสร้างด้านบน (บรรทัดสุดท้ายของโค้ดด้านบนรวมถึงกรณีฐาน) การเรียกซ้ำจะรักษาสแต็กและลึกลงไปเรื่อย ๆ จนกว่าจะถึงเคสพื้นฐาน การเขียนโปรแกรมแบบไดนามิก (DP): การเรียกซ้ำเข้าใจง่ายและใช้รหัส แต่อาจมีราคาแพงในแง่ของเวลาและหน่วยความจำ ดูต้นไม้เรียกซ้ำด้านล่าง แผนผังย่อยด้านซ้ายที่ขึ้นต้นด้วย fib (4) และแผนผังย่อยด้านขวาที่ขึ้นต้นด้วย fib (4) จะเหมือนกันทุกประการ พวกเขาสร้างผลลัพธ์เดียวกันซึ่งเป็น 3 แต่กำลังทำงานเดียวกันสองครั้ง ถ้า n เป็นจำนวนมาก (ตัวอย่าง: 500000) การเรียกซ้ำอาจทำให้โปรแกรมช้ามากเพราะจะเรียกงานย่อยเดียวกันหลาย ๆ ครั้ง

การเรียกซ้ำต้นไม้เป็นวงกลม

เพื่อหลีกเลี่ยงปัญหานี้สามารถใช้โปรแกรมไดนามิก ในการเขียนโปรแกรมแบบไดนามิกเราสามารถใช้งานย่อยที่แก้ไขก่อนหน้านี้เพื่อแก้ปัญหางานประเภทเดียวกันในอนาคต นี่เป็นวิธีลดงานในการแก้ปัญหาเดิม มามีอาร์เรย์ fib [] ที่เราเก็บโซลูชันงานย่อยที่แก้ไขแล้วก่อนหน้านี้ เรารู้แล้วว่า fib [0] = 0 และ fib [1] = 1 มาเก็บสองค่านี้กัน ตอนนี้ค่าของ fib [2] คืออะไร? ในฐานะที่เป็น fib [0] = 0 และ fib [1] = 1 ได้ถูกจัดเก็บไว้แล้วเราก็แค่บอกว่า fib [2] = fib [1] + fib [0] เท่านี้ก็หมดแล้ว เราสามารถสร้าง fib [3], fib [4], fib [5], ……, fib [n] ในลักษณะเดียวกัน งานย่อยที่แก้ไขก่อนหน้านี้จะถูกเรียกให้รับงานย่อยถัดไปจนกว่างานเดิมจะไม่ได้รับการแก้ไขจึงช่วยลดการคำนวณที่ซ้ำซ้อน