การเรียกซ้ำและสแต็ก

กลับไปที่ฟังก์ชั่นและศึกษาพวกมันในเชิงลึกมากขึ้น

หัวข้อแรกของเราจะเป็นการ เรียกซ้ำ

หากคุณไม่ใช่มือใหม่ในการเขียนโปรแกรม ก็อาจเป็นเรื่องที่คุ้นเคยและข้ามบทนี้ได้

การเรียกซ้ำเป็นรูปแบบการเขียนโปรแกรมที่มีประโยชน์ในสถานการณ์ที่งานสามารถแบ่งออกเป็นหลาย ๆ งานที่เป็นประเภทเดียวกันได้ แต่ง่ายกว่า หรือเมื่อสามารถทำให้งานง่ายขึ้นเป็นการกระทำที่ง่ายบวกกับงานเดียวกันที่ง่ายกว่า หรืออย่างที่เราจะได้เห็นในเร็วๆ นี้ เพื่อจัดการกับโครงสร้างข้อมูลบางอย่าง

เมื่อฟังก์ชันแก้ไขงาน ในกระบวนการนั้นจะสามารถเรียกใช้ฟังก์ชันอื่นๆ ได้มากมาย กรณีบางส่วนคือเมื่อฟังก์ชันเรียก ตัวเอง นั่นเรียกว่า การเรียกซ้ำ

คิดได้สองแบบ

สำหรับการเริ่มต้นง่ายๆ ลองเขียนฟังก์ชัน pow(x, n) ที่ทำให้ x เป็นกำลังธรรมชาติของ n กล่าวอีกนัยหนึ่ง คูณ x ด้วยตัวมันเอง n ครั้ง

 ธาร(2, 2) = 4
ธาร(2, 3) = 8
ธาร(2, 4) = 16

มีสองวิธีในการดำเนินการ

1. การคิดซ้ำ: for loop:

    ฟังก์ชั่นธาร(x, n) {
     ให้ผลลัพธ์ = 1;
   
     // คูณผลลัพธ์ด้วย xn เท่าในลูป
     สำหรับ (ให้ i = 0; i < n; i++) {
       ผลลัพธ์ *= x;
     -
   
     ส่งคืนผลลัพธ์;
   -
   
   การแจ้งเตือน( ธาร(2, 3) ); // 8

2. การคิดแบบวนซ้ำ: ทำให้งานง่ายขึ้นและเรียกตัวเองว่า:

    ฟังก์ชั่นธาร(x, n) {
     ถ้า (n == 1) {
       กลับ x;
     } อื่น {
       กลับ x * ธาร(x, n - 1);
     -
   -
   
   การแจ้งเตือน ( ธาร(2, 3) ); // 8

โปรดทราบว่าตัวแปรแบบเรียกซ้ำมีความแตกต่างโดยพื้นฐานอย่างไร

เมื่อ pow(x, n) ถูกเรียก การดำเนินการจะแบ่งออกเป็นสองสาขา:

              ถ้า n==1 = x
             -
ธาร(x, n) =
             -
              อื่น = x * ธาร(x, n - 1)

1. ถ้า n == 1 ทุกอย่างก็ไม่สำคัญ มันถูกเรียกว่า ฐาน ของการเรียกซ้ำ เพราะมันให้ผลลัพธ์ที่ชัดเจนทันที: pow(x, 1) เท่ากับ x

2. มิฉะนั้น เราสามารถแสดง pow(x, n) เป็น x * pow(x, n - 1) ได้ ในทางคณิตศาสตร์ เราจะเขียนว่า x n = x * x n-1 สิ่งนี้เรียกว่า ขั้นตอนแบบเรียกซ้ำ : เราแปลงงานให้เป็นการกระทำที่ง่ายกว่า (คูณด้วย x ) และการเรียกงานเดียวกันที่ง่ายกว่า ( pow ด้วย n ที่ต่ำกว่า) ขั้นตอนถัดไปทำให้ง่ายขึ้นเรื่อยๆ จนกระทั่งถึง n 1

นอกจากนี้เรายังสามารถพูดได้ว่า pow เรียกตัวเองซ้ำ ๆ จนถึง n == 1

ตัวอย่างเช่น ในการคำนวณ pow(2, 4) ตัวแปรแบบเรียกซ้ำจะทำตามขั้นตอนเหล่านี้:

1. pow(2, 4) = 2 * pow(2, 3)

2. pow(2, 3) = 2 * pow(2, 2)

3. pow(2, 2) = 2 * pow(2, 1)

4. pow(2, 1) = 2

ดังนั้นการเรียกซ้ำจะลดการเรียกใช้ฟังก์ชันให้เหลือฟังก์ชันที่ง่ายกว่า และจากนั้น – ให้ง่ายกว่านี้อีก และต่อไปเรื่อยๆ จนกว่าผลลัพธ์จะชัดเจน

การเรียกซ้ำมักจะสั้นกว่า

วิธีแก้ปัญหาแบบเรียกซ้ำมักจะสั้นกว่าวิธีแก้ปัญหาแบบวนซ้ำ

ที่นี่เราสามารถเขียนสิ่งเดียวกันใหม่ได้โดยใช้ตัวดำเนินการแบบมีเงื่อนไข ? if ทำให้ pow(x, n) สั้นลงและยังสามารถอ่านได้ดีมาก:

 ฟังก์ชั่นธาร(x, n) {
  กลับ (n == 1) ? x : (x * ธาร(x, n - 1));
-

จำนวนสูงสุดของการโทรที่ซ้อนกัน (รวมถึงการโทรแรก) เรียกว่าความ ลึกของการเรียกซ้ำ ในกรณีของเรา มันจะเป็น n อย่างแน่นอน

ความลึกของการเรียกซ้ำสูงสุดถูกจำกัดโดยกลไก JavaScript เราสามารถวางใจได้ว่ามันคือ 10,000 เครื่องยนต์บางเครื่องอนุญาตมากกว่านั้น แต่ 100,000 เครื่องอาจเกินขีดจำกัดสำหรับส่วนใหญ่ มีการเพิ่มประสิทธิภาพอัตโนมัติที่ช่วยบรรเทาสิ่งนี้ (“การเพิ่มประสิทธิภาพการโทรแบบหาง”) แต่ยังไม่รองรับในทุกที่และใช้ได้เฉพาะในกรณีธรรมดาเท่านั้น

นั่นเป็นการจำกัดการใช้การเรียกซ้ำ แต่ก็ยังกว้างมาก มีงานหลายอย่างที่วิธีคิดแบบเรียกซ้ำให้โค้ดที่ง่ายกว่า และดูแลรักษาง่ายกว่า

บริบทการดำเนินการและสแต็ก

ตอนนี้เรามาตรวจสอบว่าการโทรแบบเรียกซ้ำทำงานอย่างไร เพื่อที่เราจะดูภายใต้ประทุนของฟังก์ชั่น

ข้อมูลเกี่ยวกับกระบวนการดำเนินการของฟังก์ชันที่ทำงานอยู่จะถูกเก็บไว้ใน บริบทการดำเนินการ

บริบทการดำเนินการคือโครงสร้างข้อมูลภายในที่มีรายละเอียดเกี่ยวกับการทำงานของฟังก์ชัน: ตำแหน่งที่โฟลว์การควบคุมอยู่ในขณะนี้ ตัวแปรปัจจุบัน ค่าของ this (เราไม่ได้ใช้ที่นี่) และรายละเอียดภายในอื่นๆ เล็กน้อย

การเรียกใช้ฟังก์ชันหนึ่งครั้งมีบริบทการดำเนินการเดียวที่เกี่ยวข้องกัน

เมื่อฟังก์ชันทำการเรียกแบบซ้อน สิ่งต่อไปนี้จะเกิดขึ้น:

• ฟังก์ชั่นปัจจุบันถูกหยุดชั่วคราว

• บริบทการดำเนินการที่เกี่ยวข้องจะถูกจดจำในโครงสร้างข้อมูลพิเศษที่เรียกว่า สแต็กบริบทการดำเนินการ

• การเรียกใช้แบบซ้อนจะดำเนินการ

• หลังจากที่สิ้นสุด บริบทการดำเนินการเก่าจะถูกดึงมาจากสแต็ก และฟังก์ชันภายนอกจะกลับมาทำงานต่อจากตำแหน่งที่หยุด

มาดูกันว่าเกิดอะไรขึ้นระหว่างการโทร pow(2, 3)

ธาร(2, 3)

ในจุดเริ่มต้นของการเรียก pow(2, 3) บริบทการดำเนินการจะเก็บตัวแปร: x = 2, n = 3 โฟลว์การดำเนินการอยู่ที่บรรทัดที่ 1 ของฟังก์ชัน

เราสามารถร่างมันเป็น:

• บริบท: { x: 2, n: 3 ที่บรรทัด 1 } pow(2, 3)

นั่นคือตอนที่ฟังก์ชันเริ่มทำงาน เงื่อนไข n == 1 เป็นเท็จ ดังนั้นโฟลว์จะดำเนินต่อไปยังสาขาที่สองของ if :

 ฟังก์ชั่นธาร(x, n) {
  ถ้า (n == 1) {
    กลับ x;
  } อื่น {
    กลับ x * ธาร(x, n - 1);
  -
-

การแจ้งเตือน ( ธาร(2, 3) );

ตัวแปรเหมือนกัน แต่บรรทัดเปลี่ยนไป ดังนั้นบริบทจึงเป็นดังนี้:

• บริบท: { x: 2, n: 3, ที่บรรทัด 5 } pow(2, 3)

ในการคำนวณ x * pow(x, n - 1) เราจำเป็นต้องทำการเรียกย่อยของ pow ด้วยอาร์กิวเมนต์ใหม่ pow(2, 2)

ธาร(2, 2)

หากต้องการทำการเรียกแบบซ้อน JavaScript จะจำบริบทการดำเนินการปัจจุบันใน สแต็กบริบทการดำเนินการ

ที่นี่เราเรียกฟังก์ชันเดียวกัน pow แต่มันไม่สำคัญเลย กระบวนการจะเหมือนกันสำหรับทุกฟังก์ชัน:

1. บริบทปัจจุบันคือ "จดจำ" ไว้ที่ด้านบนของสแต็ก

2. บริบทใหม่ถูกสร้างขึ้นสำหรับการโทรย่อย

3. เมื่อการโทรย่อยเสร็จสิ้น - บริบทก่อนหน้าจะถูกดึงออกจากสแต็ก และการดำเนินการจะดำเนินต่อไป

นี่คือบริบทสแต็กเมื่อเราป้อน subcall pow(2, 2) :

• บริบท: { x: 2, n: 2, ที่บรรทัด 1 } pow(2, 2)

• บริบท: { x: 2, n: 3 ที่บรรทัด 5 } pow(2, 3)

บริบทการดำเนินการปัจจุบันใหม่จะอยู่ด้านบน (และตัวหนา) และบริบทที่จดจำก่อนหน้านี้จะอยู่ด้านล่าง

เมื่อเราเสร็จสิ้นการโทรย่อย มันเป็นเรื่องง่ายที่จะกลับมาใช้บริบทก่อนหน้าต่อ เพราะมันเก็บทั้งตัวแปรและตำแหน่งที่แน่นอนของโค้ดที่มันหยุด

โปรดทราบ:

ในภาพนี้ เราใช้คำว่า “line” ดังตัวอย่างของเราที่มีการเรียกย่อยเพียงรายการเดียวในบรรทัด แต่โดยทั่วไปแล้ว โค้ดบรรทัดเดียวอาจมีการเรียกย่อยหลายรายการ เช่น pow(…) + pow(…) + somethingElse(…) .

ดังนั้นจึงจะแม่นยำกว่าหากกล่าวว่าการดำเนินการดำเนินการต่อ "ทันทีหลังจากการโทรย่อย"

ธาร(2, 1)

กระบวนการทำซ้ำ: มีการโทรย่อยใหม่ที่บรรทัด 5 ขณะนี้มีอาร์กิวเมนต์ x=2 , n=1

มีการสร้างบริบทการดำเนินการใหม่ โดยบริบทก่อนหน้าถูกผลักไว้ด้านบนของสแต็ก:

• บริบท: { x: 2, n: 1, ที่บรรทัด 1 } pow(2, 1)

• บริบท: { x: 2, n: 2, ที่บรรทัด 5 } pow(2, 2)

• บริบท: { x: 2, n: 3, ที่บรรทัด 5 } pow(2, 3)

ขณะนี้มี 2 บริบทเก่าและ 1 รายการกำลังทำงานอยู่ pow(2, 1)

ทางออก

ในระหว่างการดำเนินการ pow(2, 1) ไม่เหมือนเมื่อก่อน เงื่อนไข n == 1 เป็นความจริง ดังนั้นสาขาแรกของ if ใช้งานได้:

 ฟังก์ชั่นธาร(x, n) {
  ถ้า (n == 1) {
    กลับ x;
  } อื่น {
    กลับ x * ธาร(x, n - 1);
  -
-

ไม่มีการเรียกซ้อนอีกต่อไป ดังนั้นฟังก์ชันจึงเสร็จสิ้นโดยส่งคืน 2

เมื่อฟังก์ชันเสร็จสิ้น บริบทการดำเนินการก็ไม่จำเป็นอีกต่อไป ดังนั้นจึงถูกลบออกจากหน่วยความจำ อันก่อนหน้านี้ถูกเรียกคืนจากด้านบนของสแต็ก:

• บริบท: { x: 2, n: 2, ที่บรรทัด 5 } pow(2, 2)

• บริบท: { x: 2, n: 3, ที่บรรทัด 5 } pow(2, 3)

การดำเนินการของ pow(2, 2) จะกลับมาทำงานต่อ มันมีผลลัพธ์ของการโทรย่อย pow(2, 1) ดังนั้นจึงยังสามารถเสร็จสิ้นการประเมินของ x * pow(x, n - 1) ส่งคืน 4

จากนั้นบริบทก่อนหน้าจะถูกกู้คืน:

• บริบท: { x: 2, n: 3, ที่บรรทัด 5 } pow(2, 3)

เมื่อเสร็จแล้วเราจะได้ผลลัพธ์เป็น pow(2, 3) = 8

ความลึกของการเรียกซ้ำในกรณีนี้คือ: 3

ดังที่เราเห็นจากภาพประกอบด้านบน ความลึกของการเรียกซ้ำเท่ากับจำนวนบริบทสูงสุดในสแต็ก

สังเกตข้อกำหนดด้านหน่วยความจำ บริบทต้องใช้ความทรงจำ ในกรณีของเรา การยกกำลัง n ต้องใช้หน่วยความจำสำหรับบริบท n สำหรับค่าที่ต่ำกว่าทั้งหมดของ n

อัลกอริธึมแบบวนซ้ำช่วยประหยัดหน่วยความจำได้มากกว่า:

 ฟังก์ชั่นธาร(x, n) {
  ให้ผลลัพธ์ = 1;

  สำหรับ (ให้ i = 0; i < n; i++) {
    ผลลัพธ์ *= x;
  -

  ส่งคืนผลลัพธ์;
-

pow วนซ้ำใช้บริบทเดียวที่เปลี่ยนแปลง i และ result ให้เกิดกระบวนการ ข้อกำหนดหน่วยความจำมีขนาดเล็ก คงที่ และไม่ขึ้นอยู่กับ n

การเรียกซ้ำใดๆ สามารถเขียนใหม่เป็นการวนซ้ำได้ โดยทั่วไปตัวแปรลูปจะทำให้มีประสิทธิภาพมากขึ้น

…แต่บางครั้งการเขียนซ้ำก็ไม่ใช่เรื่องเล็กน้อย โดยเฉพาะอย่างยิ่งเมื่อฟังก์ชันใช้การเรียกย่อยแบบเรียกซ้ำที่แตกต่างกัน ขึ้นอยู่กับเงื่อนไขและรวมผลลัพธ์เข้าด้วยกัน หรือเมื่อการแยกย่อยมีความซับซ้อนมากขึ้น และการเพิ่มประสิทธิภาพอาจไม่จำเป็นและไม่คุ้มค่ากับความพยายามโดยสิ้นเชิง

การเรียกซ้ำสามารถให้โค้ดที่สั้นกว่า เข้าใจง่ายกว่าและสนับสนุน ไม่จำเป็นต้องมีการเพิ่มประสิทธิภาพในทุกที่ ส่วนใหญ่แล้วเราต้องการโค้ดที่ดี นั่นคือเหตุผลว่าทำไมจึงต้องใช้

การข้ามแบบเรียกซ้ำ

การประยุกต์ใช้การเรียกซ้ำที่ยอดเยี่ยมอีกประการหนึ่งคือการข้ามผ่านแบบเรียกซ้ำ

ลองนึกภาพเรามีบริษัท โครงสร้างพนักงานสามารถนำเสนอเป็นวัตถุได้:

 ให้บริษัท = {
  ฝ่ายขาย: [{
    ชื่อ: 'จอห์น'
    เงินเดือน: 1,000
  -
    ชื่อ'อลิซ'
    เงินเดือน: 1600
  -

  การพัฒนา: {
    ไซต์: [{
      ชื่อ' ปีเตอร์'
      เงินเดือน: 2000
    -
      ชื่อ'อเล็กซ์'
      เงินเดือน: 1800
    -

    ภายใน: [{
      ชื่อ'แจ๊ค'
      เงินเดือน: 1300
    -
  -
-

กล่าวอีกนัยหนึ่ง บริษัทมีแผนกต่างๆ

• แผนกหนึ่งอาจมีพนักงานหลายกลุ่ม ตัวอย่างเช่น แผนก sales มีพนักงาน 2 คน: จอห์นและอลิซ

• หรือแผนกอาจแยกออกเป็นแผนกย่อย เช่น development มีสองสาขา: sites และ internals แต่ละคนมีพนักงานของตัวเอง

• อาจเป็นไปได้ว่าเมื่อแผนกย่อยเติบโตขึ้น จะแบ่งออกเป็นแผนกย่อย (หรือทีม)

  ตัวอย่างเช่น แผนก sites ในอนาคตอาจถูกแบ่งออกเป็นทีมสำหรับ siteA และ siteB และอาจแบ่งแยกได้มากขึ้นอีก นั่นไม่ได้อยู่ในภาพ เป็นเพียงสิ่งที่ต้องคำนึงถึง

ทีนี้ สมมติว่าเราต้องการฟังก์ชันเพื่อหาผลรวมของเงินเดือนทั้งหมด เราจะทำเช่นนั้นได้อย่างไร?

วิธีการวนซ้ำไม่ใช่เรื่องง่าย เนื่องจากโครงสร้างไม่ง่าย แนวคิดแรกอาจเป็นการสร้าง for loop เหนือ company โดยมี subloop ซ้อนกันบนแผนกระดับที่ 1 แต่แล้วเราจำเป็นต้องมีลูปย่อยที่ซ้อนกันมากขึ้นเพื่อวนซ้ำกับพนักงานในแผนกระดับ 2 เช่น sites … และยังมีลูปย่อยอื่นในแผนกสำหรับแผนกระดับ 3 ที่อาจปรากฏในอนาคต หากเราใส่ลูปย่อยที่ซ้อนกัน 3-4 ลูปในโค้ดเพื่อสำรวจวัตถุเดี่ยว มันจะค่อนข้างน่าเกลียด

มาลองเรียกซ้ำกัน

ดังที่เราเห็น เมื่อฟังก์ชันของเราได้รับแผนกเพื่อสรุป มีสองกรณีที่เป็นไปได้:

1. ไม่ว่าจะเป็นแผนกที่ "เรียบง่าย" ที่มีคน จำนวนมาก เราก็สามารถสรุปเงินเดือนแบบวนเดียวได้

2. หรือเป็น อ็อบเจ็กต์ ที่มีแผนกย่อย N จากนั้นเราสามารถทำการเรียกซ้ำ N เพื่อรับผลรวมสำหรับแต่ละแผนกย่อยและรวมผลลัพธ์

กรณีที่ 1 เป็นฐานของการเรียกซ้ำ ซึ่งเป็นกรณีที่ไม่สำคัญ เมื่อเราได้รับอาร์เรย์

กรณีที่ 2 เมื่อเราได้รับวัตถุคือขั้นตอนการเรียกซ้ำ งานที่ซับซ้อนจะถูกแบ่งออกเป็นงานย่อยสำหรับแผนกย่อย พวกเขาอาจจะแยกกันอีกครั้ง แต่ไม่ช้าก็เร็วการแยกจะสิ้นสุดที่ (1)

อัลกอริทึมน่าจะอ่านง่ายกว่าจากโค้ด:

 ให้บริษัท = { // วัตถุเดียวกัน บีบอัดเพื่อความกระชับ
  ยอดขาย: [{ชื่อ: 'จอห์น' เงินเดือน: 1,000} {ชื่อ: 'อลิซ' เงินเดือน: 1600 }],
  การพัฒนา: {
    เว็บไซต์: [{ชื่อ: 'ปีเตอร์' เงินเดือน: 2000} {ชื่อ: 'อเล็กซ์' เงินเดือน: 1800 }],
    ภายใน: [{ชื่อ: 'แจ็ค' เงินเดือน: 1300}]
  -
-

// ฟังก์ชั่นในการทำงาน
ฟังก์ชั่น sumSalaries(แผนก) {
  ถ้า (Array.isArray (แผนก)) { // กรณี (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // รวมอาร์เรย์
  } อื่น ๆ { // กรณี (2)
    ให้ผลรวม = 0;
    สำหรับ (ให้ส่วนย่อยของ Object.values ​​(แผนก)) {
      ผลรวม += ผลรวมเงินเดือน (ส่วนย่อย); //เรียกแผนกย่อยซ้ำๆ และสรุปผลลัพธ์
    -
    จำนวนเงินที่ส่งคืน;
  -
-

alert(ผลรวมเงินเดือน(บริษัท)); // 7700

รหัสสั้นและเข้าใจง่าย (หวังว่า?) นั่นคือพลังของการเรียกซ้ำ นอกจากนี้ยังใช้ได้กับการซ้อนแผนกย่อยทุกระดับอีกด้วย

นี่คือแผนภาพการโทร:

เราสามารถมองเห็นหลักการได้อย่างง่ายดาย: สำหรับการโทรย่อยของอ็อบเจ็กต์ {...} ถูกสร้างขึ้น ในขณะที่อาร์เรย์ [...] เป็น "ใบไม้" ของแผนผังการเรียกซ้ำ พวกมันให้ผลลัพธ์ทันที

โปรดทราบว่าโค้ดใช้คุณสมบัติอัจฉริยะที่เราได้กล่าวถึงก่อนหน้านี้:

• วิธี arr.reduce อธิบายไว้ในบท Array วิธีการรับผลรวมของอาร์เรย์

• วนซ้ำ for(val of Object.values(obj)) เพื่อวนซ้ำค่าอ็อบเจ็กต์: Object.values ​​ส่งคืนอาร์เรย์ของค่าเหล่านั้น

โครงสร้างแบบเรียกซ้ำ

โครงสร้างข้อมูลแบบเรียกซ้ำ (กำหนดแบบเรียกซ้ำ) เป็นโครงสร้างที่จำลองตัวเองเป็นส่วนๆ

เราเพิ่งเห็นมันในตัวอย่างโครงสร้างบริษัทข้างต้น

แผนก ของบริษัทคือ:

• ไม่ว่าจะเป็นผู้คนมากมาย

• หรือวัตถุมงคลกับ หน่วยงานต่างๆ

สำหรับนักพัฒนาเว็บ มีตัวอย่างที่รู้จักกันดีกว่ามาก: เอกสาร HTML และ XML

ในเอกสาร HTML แท็ก HTML อาจมีรายการของ:

• ชิ้นส่วนข้อความ

• ความคิดเห็น HTML

• แท็ก HTML อื่นๆ (ซึ่งอาจมีส่วนข้อความ/ความคิดเห็น หรือแท็กอื่นๆ เป็นต้น)

นั่นเป็นคำจำกัดความแบบเรียกซ้ำอีกครั้ง

เพื่อความเข้าใจที่ดีขึ้น เราจะกล่าวถึงโครงสร้างแบบเรียกซ้ำอีกหนึ่งโครงสร้างที่ชื่อ "รายการที่เชื่อมโยง" ซึ่งอาจเป็นทางเลือกที่ดีกว่าสำหรับอาร์เรย์ในบางกรณี

รายการที่เชื่อมโยง

ลองนึกภาพเราต้องการจัดเก็บรายการวัตถุที่เรียงลำดับไว้

ตัวเลือกที่เป็นธรรมชาติจะเป็นอาร์เรย์:

 ให้ arr = [obj1, obj2, obj3];

…แต่มีปัญหากับอาร์เรย์ การดำเนินการ "ลบองค์ประกอบ" และ "แทรกองค์ประกอบ" มีราคาแพง ตัวอย่างเช่น การดำเนินการ arr.unshift(obj) จะต้องกำหนดหมายเลของค์ประกอบทั้งหมดใหม่เพื่อให้มีที่ว่างสำหรับ obj ใหม่ และหากอาร์เรย์มีขนาดใหญ่ก็ต้องใช้เวลา เช่นเดียวกับ arr.shift()

การปรับเปลี่ยนโครงสร้างเพียงอย่างเดียวที่ไม่ต้องการการจัดเรียงหมายเลขใหม่จำนวนมากคือการปรับเปลี่ยนที่ทำงานโดยที่ส่วนท้ายของอาร์เรย์: arr.push/pop ดังนั้นอาร์เรย์อาจค่อนข้างช้าสำหรับคิวขนาดใหญ่ เมื่อเราต้องทำงานกับจุดเริ่มต้น

หรือหากเราต้องการแทรก/ลบอย่างรวดเร็ว เราสามารถเลือกโครงสร้างข้อมูลอื่นที่เรียกว่ารายการที่เชื่อมโยงได้

องค์ประกอบรายการที่เชื่อมโยง ถูกกำหนดซ้ำเป็นวัตถุด้วย:

• value .

• คุณสมบัติ next ไปที่อ้างอิงถึง องค์ประกอบรายการที่ถูกเชื่อมโยง ถัดไปหรือ null หากนั่นคือจุดสิ้นสุด

ตัวอย่างเช่น:

 ให้รายการ = {
  ค่า: 1,
  ต่อไป: {
    ค่า: 2,
    ต่อไป: {
      ค่า: 3,
      ต่อไป: {
        ค่า: 4,
        ถัดไป: โมฆะ
      -
    -
  -
-

การแสดงกราฟิกของรายการ:

รหัสทางเลือกสำหรับการสร้าง:

 ให้รายการ = { ค่า: 1 };
list.next = { ค่า: 2 };
list.next.next = { ค่า: 3 };
list.next.next.next = { ค่า: 4 };
list.next.next.next.next = โมฆะ;

ตรงนี้เราจะเห็นได้ชัดเจนยิ่งขึ้นว่ามีวัตถุหลายชิ้น แต่ละชิ้นมี value และชี้ไปที่เพื่อนบ้าน next ตัวแปร list เป็นออบเจ็กต์แรกในห่วงโซ่ ดังนั้นหลังจากพอยน์เตอร์ next จากนั้นเราจึงสามารถเข้าถึงองค์ประกอบใดก็ได้

รายการสามารถแบ่งออกเป็นหลายส่วนได้อย่างง่ายดายและกลับมารวมกันในภายหลัง:

 ให้ SecondList = list.next.next;
list.next.next = โมฆะ; 

หากต้องการเข้าร่วม:

 list.next.next = รายการที่สอง;

และแน่นอนว่าเราสามารถใส่หรือถอดสิ่งของได้ทุกที่

ตัวอย่างเช่น หากต้องการเพิ่มค่าใหม่ เราจำเป็นต้องอัปเดตส่วนหัวของรายการ:

 ให้รายการ = { ค่า: 1 };
list.next = { ค่า: 2 };
list.next.next = { ค่า: 3 };
list.next.next.next = { ค่า: 4 };

// นำค่าใหม่มาไว้หน้ารายการ
รายการ = { ค่า: "รายการใหม่" ถัดไป: รายการ }; 

หากต้องการลบค่าออกจากตรงกลาง ให้เปลี่ยนค่า next จากค่าก่อนหน้า:

 list.next = รายการถัดไป.ถัดไป; 

เราทำ list.next กระโดดข้าม 1 ไปเป็นค่า 2 ตอนนี้ค่า 1 ถูกแยกออกจากเชนแล้ว หากไม่ได้เก็บไว้ที่อื่น ข้อมูลนั้นจะถูกลบออกจากหน่วยความจำโดยอัตโนมัติ

ต่างจากอาร์เรย์ตรงที่ไม่มีการจัดเรียงหมายเลขใหม่จำนวนมาก เราสามารถจัดเรียงองค์ประกอบใหม่ได้อย่างง่ายดาย

โดยปกติแล้ว รายการไม่ได้ดีไปกว่าอาร์เรย์เสมอไป มิฉะนั้นทุกคนจะใช้เฉพาะรายการเท่านั้น

ข้อเสียเปรียบหลักคือเราไม่สามารถเข้าถึงองค์ประกอบด้วยหมายเลขได้อย่างง่ายดาย ในอาร์เรย์ที่ง่าย: arr[n] เป็นการอ้างอิงโดยตรง แต่ในรายการ เราต้องเริ่มจากรายการแรกและไป N ครั้ง next เพื่อรับองค์ประกอบที่ N

…แต่เราไม่จำเป็นต้องมีการดำเนินการดังกล่าวเสมอไป ตัวอย่างเช่น เมื่อเราต้องการคิวหรือแม้แต่ deque โครงสร้างที่ได้รับคำสั่งจะต้องอนุญาตให้เพิ่ม/ลบองค์ประกอบจากปลายทั้งสองอย่างรวดเร็ว แต่ไม่จำเป็นต้องเข้าถึงตรงกลาง

รายการสามารถปรับปรุงได้:

• เราสามารถเพิ่มคุณสมบัติ prev นอกเหนือจาก next เพื่ออ้างอิงองค์ประกอบก่อนหน้าได้ เพื่อให้ย้อนกลับได้อย่างง่ายดาย

• นอกจากนี้เรายังสามารถเพิ่มตัวแปรชื่อ tail โดยอ้างอิงถึงองค์ประกอบสุดท้ายของรายการ (และอัปเดตเมื่อเพิ่ม/ลบองค์ประกอบออกจากส่วนท้าย)

• …โครงสร้างข้อมูลอาจแตกต่างกันไปตามความต้องการของเรา

สรุป

เงื่อนไข:

• การเรียกซ้ำ เป็นศัพท์การเขียนโปรแกรมที่หมายถึงการเรียกใช้ฟังก์ชันจากตัวมันเอง ฟังก์ชันแบบเรียกซ้ำสามารถใช้เพื่อแก้ปัญหางานได้อย่างหรูหรา

  เมื่อฟังก์ชันเรียกตัวเอง นั่นเรียกว่า ขั้นตอนการเรียกซ้ำ พื้นฐาน ของการเรียกซ้ำคืออาร์กิวเมนต์ของฟังก์ชันที่ทำให้งานง่ายจนฟังก์ชันไม่ทำการเรียกเพิ่มเติม

• โครงสร้างข้อมูลที่กำหนดแบบเรียกซ้ำคือโครงสร้างข้อมูลที่สามารถกำหนดได้โดยใช้ตัวมันเอง

  ตัวอย่างเช่น รายการที่เชื่อมโยงสามารถกำหนดเป็นโครงสร้างข้อมูลที่ประกอบด้วยวัตถุที่อ้างอิงถึงรายการ (หรือ null)

   รายการ = { ค่า ถัดไป -> รายการ }

  ต้นไม้เช่นแผนผังองค์ประกอบ HTML หรือแผนผังแผนกจากบทนี้ก็เป็นแบบเรียกซ้ำตามธรรมชาติเช่นกัน พวกมันมีกิ่งก้านและทุกกิ่งสามารถมีกิ่งอื่นได้

  สามารถใช้ฟังก์ชันแบบเรียกซ้ำเพื่อดำเนินการตามที่เราเห็นในตัวอย่าง sumSalary

ฟังก์ชันแบบเรียกซ้ำใดๆ สามารถเขียนใหม่เป็นการวนซ้ำได้ และบางครั้งจำเป็นต้องเพิ่มประสิทธิภาพสิ่งต่างๆ แต่สำหรับงานหลายๆ งาน โซลูชันแบบเรียกซ้ำจะเร็วเพียงพอและง่ายกว่าในการเขียนและการสนับสนุน

งาน

รวมตัวเลขทั้งหมดจนถึงตัวที่กำหนด

ความสำคัญ: 5

เขียนฟังก์ชัน sumTo(n) ที่คำนวณผลรวมของตัวเลข 1 + 2 + ... + n

ตัวอย่างเช่น:

 ผลรวมถึง(1) = 1
ผลรวมถึง(2) = 2 + 1 = 3
ผลรวมถึง(3) = 3 + 2 + 1 = 6
ผลรวมถึง(4) = 4 + 3 + 2 + 1 = 10
-
ผลรวมถึง(100) = 100 + 99 + ... + 2 + 1 = 5050

สร้างโซลูชัน 3 แบบ:

1. การใช้ for loop

2. การใช้การเรียกซ้ำ ทำให้ sumTo(n) = n + sumTo(n-1) สำหรับ n > 1

3. การใช้สูตรก้าวหน้าทางคณิตศาสตร์

ตัวอย่างของผลลัพธ์:

 ฟังก์ชั่น sumTo(n) { /*... รหัสของคุณ ... */ }

การแจ้งเตือน( sumTo(100) ); // 5050

ป.ล. โซลูชันรุ่นใดที่เร็วที่สุด ช้าที่สุด? ทำไม

PPS เราสามารถใช้การเรียกซ้ำเพื่อนับ sumTo(100000) ได้หรือไม่?

สารละลาย

วิธีแก้ปัญหาโดยใช้ลูป:

 ฟังก์ชั่น sumTo(n) {
  ให้ผลรวม = 0;
  สำหรับ (ให้ i = 1; i <= n; i++) {
    ผลรวม += ฉัน;
  -
  จำนวนเงินที่ส่งคืน;
-

การแจ้งเตือน( sumTo(100) );

วิธีแก้ปัญหาโดยใช้การเรียกซ้ำ:

 ฟังก์ชั่น sumTo(n) {
  ถ้า (n == 1) ส่งคืน 1;
  กลับ n + sumTo(n - 1);
-

การแจ้งเตือน( sumTo(100) );

วิธีแก้ปัญหาโดยใช้สูตร: sumTo(n) = n*(n+1)/2 :

 ฟังก์ชั่น sumTo(n) {
  กลับ n * (n + 1) / 2;
-

การแจ้งเตือน( sumTo(100) );

ป.ล. แน่นอนว่าสูตรคือคำตอบที่เร็วที่สุด โดยจะใช้การดำเนินการเพียง 3 ครั้งสำหรับตัวเลขใดๆ n คณิตช่วยได้!

ตัวแปรลูปเป็นตัวแปรที่สองในแง่ของความเร็ว ทั้งในตัวแปรแบบเรียกซ้ำและแบบวนซ้ำ เราจะรวมตัวเลขที่เท่ากัน แต่การเรียกซ้ำเกี่ยวข้องกับการเรียกแบบซ้อนและการจัดการสแต็กการดำเนินการ นั่นต้องใช้ทรัพยากรด้วยดังนั้นจึงช้าลง

PPS เอ็นจิ้นบางตัวรองรับการเพิ่มประสิทธิภาพ "การเรียกหาง": หากการเรียกซ้ำเป็นการโทรครั้งสุดท้ายในฟังก์ชัน โดยไม่มีการคำนวณอื่นใด ฟังก์ชันภายนอกจะไม่จำเป็นต้องดำเนินการต่อ ดังนั้นเอ็นจิ้นจึงไม่จำเป็นต้อง จำบริบทการดำเนินการของมัน ที่ช่วยขจัดภาระในหน่วยความจำ แต่หากเอ็นจิ้น JavaScript ไม่รองรับการเพิ่มประสิทธิภาพการเรียกส่วนท้าย (ส่วนใหญ่ไม่รองรับ) จะมีข้อผิดพลาด: เกินขนาดสแต็กสูงสุด เนื่องจากโดยปกติแล้วจะมีข้อจำกัดเกี่ยวกับขนาดสแต็กทั้งหมด

คำนวณแฟกทอเรียล

ความสำคัญ: 4

แฟกทอเรียลของจำนวนธรรมชาติคือจำนวนคูณด้วย "number minus one" จากนั้นด้วย "number minus two" และต่อๆ ไปจนถึง 1 แฟกทอเรียลของ n แสดงเป็น n!

เราสามารถเขียนคำจำกัดความของแฟกทอเรียลได้ดังนี้:

 มะ! = n * (n - 1) * (n - 2) * ...*1

ค่าแฟกทอเรียลสำหรับค่าต่างๆ n :

 1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

งานคือการเขียนฟังก์ชัน factorial(n) ที่คำนวณ n! โดยใช้การโทรซ้ำ

 การแจ้งเตือน ( แฟกทอเรียล (5) ); // 120

PS คำแนะนำ: n! สามารถเขียนเป็น n * (n-1)! ตัวอย่างเช่น: 3! = 3*2! = 3*2*1! = 6

สารละลาย

ตามคำนิยามแล้ว แฟกทอเรียล n! สามารถเขียนเป็น n * (n-1)! -

กล่าวอีกนัยหนึ่ง ผลลัพธ์ของ factorial(n) สามารถคำนวณได้โดย n คูณด้วยผลลัพธ์ของ factorial(n-1) และการเรียก n-1 สามารถลดระดับลงซ้ำๆ จนถึง 1 ได้

 ฟังก์ชันแฟกทอเรียล (n) {
  กลับ (n != 1) ? n * แฟกทอเรียล(n - 1) : 1;
-

การแจ้งเตือน ( แฟกทอเรียล (5) ); // 120

พื้นฐานของการเรียกซ้ำคือค่า 1 เรายังสามารถสร้าง 0 เป็นพื้นฐานได้ที่นี่ ไม่สำคัญมากนัก แต่ให้อีกหนึ่งขั้นตอนการเรียกซ้ำ:

 ฟังก์ชันแฟกทอเรียล (n) {
  กลับไม่มี ? n * แฟกทอเรียล(n - 1) : 1;
-

การแจ้งเตือน ( แฟกทอเรียล (5) ); // 120

ตัวเลขฟีโบนัชชี

ความสำคัญ: 5

ลำดับของตัวเลขฟีโบนัชชีมีสูตร F n = F n-1 + F n-2 กล่าวอีกนัยหนึ่ง ตัวเลขถัดไปคือผลรวมของสองตัวก่อนหน้า

ตัวเลขสองตัวแรกคือ 1 จากนั้น 2(1+1) จากนั้น 3(1+2) , 5(2+3) และอื่นๆ: 1, 1, 2, 3, 5, 8, 13, 21... .

ตัวเลขฟีโบนัชชีเกี่ยวข้องกับอัตราส่วนทองคำและปรากฏการณ์ทางธรรมชาติมากมายรอบตัวเรา

เขียนฟังก์ชัน fib(n) ที่ส่งคืนเลขฟีโบนัชชี n-th

ตัวอย่างงาน:

 ฟังก์ชั่น fib(n) { /* รหัสของคุณ */ }

การแจ้งเตือน (ปลิ้นปล้อน (3)); // 2
การแจ้งเตือน (ปลิ้นปล้อน (7)); // 13
การแจ้งเตือน (ปลิ้นปล้อน (77)); // 5527939700884757

ป.ล. ฟังก์ชั่นควรจะรวดเร็ว การเรียก fib(77) ควรใช้เวลาไม่เกินเสี้ยววินาที

สารละลาย

วิธีแก้ปัญหาแรกที่เราสามารถลองได้ที่นี่คือวิธีเรียกซ้ำ

หมายเลขฟีโบนัชชีเป็นแบบเรียกซ้ำตามคำจำกัดความ:

 ฟังก์ชั่นปลิ้นปล้อน (n) {
  กลับ n <= 1 ? n : ตอแหล(n - 1) + ตอแหล(n - 2);
-

การแจ้งเตือน( ตอแหล(3) ); // 2
การแจ้งเตือน( ตอแหล(7) ); // 13
// ปลิ้นปล้อน (77); // จะช้ามาก!

…แต่สำหรับค่า n จำนวนมาก มันช้ามาก ตัวอย่างเช่น fib(77) อาจวางสายเอ็นจิ้นเป็นระยะเวลาหนึ่งโดยกินทรัพยากร CPU ทั้งหมด

นั่นเป็นเพราะว่าฟังก์ชันทำการเรียกย่อยมากเกินไป ค่าเดียวกันจะได้รับการประเมินซ้ำแล้วซ้ำอีก

ตัวอย่างเช่น เรามาดูการคำนวณสำหรับ fib(5) :

 -
ตอแหล(5) = ตอแหล(4) + ตอแหล(3)
ตอแหล(4) = ตอแหล(3) + ตอแหล(2)
-

ที่นี่เราจะเห็นได้ว่าค่าของ fib(3) เป็นสิ่งจำเป็นสำหรับทั้ง fib(5) และ fib(4) ดังนั้น fib(3) จะถูกเรียกและประเมินสองครั้งโดยอิสระโดยสมบูรณ์

นี่คือแผนผังการเรียกซ้ำแบบเต็ม:

เราจะสังเกตได้ชัดเจนว่า fib(3) ได้รับการประเมินสองครั้ง และ fib(2) ได้รับการประเมินสามครั้ง จำนวนการคำนวณทั้งหมดเติบโตเร็วกว่า n มาก ทำให้มีจำนวนมหาศาลแม้กระทั่งสำหรับ n=77

เราสามารถปรับให้เหมาะสมได้ด้วยการจดจำค่าที่ประเมินแล้ว: หากคำนวณค่าของ fib(3) หนึ่งครั้ง เราก็สามารถนำค่านั้นกลับมาใช้ใหม่ในการคำนวณในอนาคตได้

อีกตัวแปรหนึ่งคือการละทิ้งการเรียกซ้ำและใช้อัลกอริธึมแบบวนซ้ำที่แตกต่างกันโดยสิ้นเชิง

แทนที่จะไปจาก n ลงไปที่ค่าที่ต่ำกว่า เราสามารถสร้างการวนซ้ำที่เริ่มต้นจาก 1 และ 2 จากนั้นรับ fib(3) เป็นผลรวม จากนั้น fib(4) เป็นผลรวมของสองค่าก่อนหน้า จากนั้น fib(5) และขึ้นๆ ลงๆ จนกระทั่งได้ค่าที่ต้องการ ในแต่ละขั้นตอนเราจำเป็นต้องจำค่าก่อนหน้าสองค่าเท่านั้น

ต่อไปนี้เป็นขั้นตอนของอัลกอริทึมใหม่โดยละเอียด

จุดเริ่มต้น:

 // a = fib(1), b = fib(2) ค่าเหล่านี้เป็นไปตามคำจำกัดความ 1
ให้ a = 1, b = 1;

// รับ c = fib(3) เป็นผลรวม
ให้ c = a + b;

/* ตอนนี้เรามี fib(1), fib(2), fib(3)
เอ บี ซี
1, 1, 2
-

ตอนนี้เราต้องการรับ fib(4) = fib(2) + fib(3)

มาเปลี่ยนตัวแปรกัน: a,b จะได้รับ fib(2),fib(3) และ c จะได้รับผลรวม:

 ก = ข; // ตอนนี้ a = fib(2)
ข = ค; // ตอนนี้ b = ปลิ้นปล้อน (3)
ค = ก + ข; // c = ปลิ้นปล้อน (4)

/* ตอนนี้เรามีลำดับ:
   เอ บี ซี
1, 1, 2, 3
-

ขั้นตอนต่อไปจะให้หมายเลขลำดับอื่น:

 ก = ข; // ตอนนี้ a = fib(3)
ข = ค; // ตอนนี้ b = ปลิ้นปล้อน (4)
ค = ก + ข; // c = ปลิ้นปล้อน (5)

/* ตอนนี้ลำดับคือ (อีกหนึ่งหมายเลข):
      เอ บี ซี
1, 1, 2, 3, 5
-

…และต่อๆ ไปจนกว่าเราจะได้ค่าที่ต้องการ ซึ่งเร็วกว่าการเรียกซ้ำมาก และไม่มีการคำนวณซ้ำกัน

รหัสเต็ม:

 ฟังก์ชั่นปลิ้นปล้อน (n) {
  ให้ = 1;
  ให้ข = 1;
  สำหรับ (ให้ i = 3; i <= n; i++) {
    ให้ c = a + b;
    ก = ข;
    ข = ค;
  -
  กลับข;
-

การแจ้งเตือน( ตอแหล(3) ); // 2
การแจ้งเตือน( ตอแหล(7) ); // 13
การแจ้งเตือน( ตอแหล(77) ); // 5527939700884757

การวนซ้ำเริ่มต้นด้วย i=3 เนื่องจากค่าลำดับแรกและลำดับที่สองถูกฮาร์ดโค้ดลงในตัวแปร a=1 , b=1

วิธีการนี้เรียกว่าการเขียนโปรแกรมแบบไดนามิกจากล่างขึ้นบน

เอาท์พุตรายการลิงค์เดียว

ความสำคัญ: 5

สมมติว่าเรามีรายการแบบลิงก์เดียว (ตามที่อธิบายไว้ในบท Recursion and stack):

 ให้รายการ = {
  ค่า: 1,
  ต่อไป: {
    ค่า: 2,
    ต่อไป: {
      ค่า: 3,
      ต่อไป: {
        ค่า: 4,
        ถัดไป: โมฆะ
      -
    -
  -
-

เขียนฟังก์ชัน printList(list) ที่ส่งออกรายการทีละรายการ

สร้างโซลูชันสองแบบ: การใช้การวนซ้ำและการใช้การเรียกซ้ำ

อะไรจะดีไปกว่า: ด้วยการเรียกซ้ำหรือไม่มีมัน?

สารละลาย

โซลูชันแบบวนซ้ำ

โซลูชันแบบวนซ้ำ

ตัวแปรแบบอิงลูปของโซลูชัน:

 ให้รายการ = {
  ค่า: 1,
  ต่อไป: {
    ค่า: 2,
    ต่อไป: {
      ค่า: 3,
      ต่อไป: {
        ค่า: 4,
        ถัดไป: โมฆะ
      -
    -
  -
-

ฟังก์ชั่น printList (รายการ) {
  ให้ tmp = รายการ;

  ในขณะที่ (tmp) {
    การแจ้งเตือน (tmp.value);
    tmp = tmp.ถัดไป;
  -

-

รายการพิมพ์ (รายการ);

โปรดทราบว่าเราใช้ตัวแปรชั่วคราว tmp เพื่อข้ามรายการ ในทางเทคนิคแล้ว เราสามารถใช้ list พารามิเตอร์ของฟังก์ชันแทนได้:

 ฟังก์ชั่น printList (รายการ) {

  ในขณะที่ (รายการ) {
    การแจ้งเตือน(list.value);
    รายการ = รายการถัดไป;
  -

-

…แต่นั่นจะไม่ฉลาดเลย ในอนาคตเราอาจจำเป็นต้องขยายฟังก์ชัน ทำอย่างอื่นกับรายการ ถ้าเราเปลี่ยน list เราก็จะสูญเสียความสามารถดังกล่าว

เมื่อพูดถึงชื่อตัวแปรที่ดี list นี่คือรายการนั่นเอง องค์ประกอบแรกของมัน และมันควรจะคงอยู่เช่นนั้น ที่ชัดเจนและเชื่อถือได้

ในอีกด้านหนึ่ง บทบาทของ tmp เป็นเพียงการแวะผ่านรายการเท่านั้น เช่น i อยู่ใน for loop

โซลูชันแบบเรียกซ้ำ

โซลูชันแบบเรียกซ้ำ

รูปแบบการเรียกซ้ำของ printList(list) เป็นไปตามตรรกะง่ายๆ: ในการส่งออกรายการเราควรส่งออกองค์ประกอบปัจจุบัน list จากนั้นทำเช่นเดียวกันกับ list.next :

 ให้รายการ = {
  ค่า: 1,
  ต่อไป: {
    ค่า: 2,
    ต่อไป: {
      ค่า: 3,
      ต่อไป: {
        ค่า: 4,
        ถัดไป: โมฆะ
      -
    -
  -
-

ฟังก์ชั่น printList (รายการ) {

  การแจ้งเตือน(list.value); // ส่งออกรายการปัจจุบัน

  ถ้า (รายการถัดไป) {
    printList(รายการถัดไป); // ทำแบบเดียวกันกับรายการที่เหลือ
  -

-

รายการพิมพ์ (รายการ);

ตอนนี้มีอะไรดีกว่า?

ในทางเทคนิคแล้ว การวนซ้ำจะมีประสิทธิภาพมากกว่า ตัวแปรทั้งสองนี้ทำเช่นเดียวกัน แต่การวนซ้ำไม่ได้ใช้ทรัพยากรสำหรับการเรียกใช้ฟังก์ชันที่ซ้อนกัน

ในอีกด้านหนึ่ง รูปแบบที่เกิดซ้ำจะสั้นกว่าและบางครั้งก็เข้าใจง่ายกว่า

เอาท์พุตรายการลิงค์เดียวในลำดับย้อนกลับ

ความสำคัญ: 5

เอาท์พุตรายการลิงค์เดียวจากงานก่อนหน้า เอาท์พุตรายการลิงค์เดียวในลำดับย้อนกลับ

สร้างวิธีแก้ปัญหาสองวิธี: การใช้การวนซ้ำและการใช้การเรียกซ้ำ

สารละลาย

การใช้การเรียกซ้ำ

การใช้การเรียกซ้ำ

ตรรกะการเรียกซ้ำค่อนข้างยุ่งยากเล็กน้อยที่นี่

เราจำเป็นต้องส่งออกรายการที่เหลือก่อนแล้ว จึง ส่งออกรายการปัจจุบัน:

 ให้รายการ = {
  ค่า: 1,
  ต่อไป: {
    ค่า: 2,
    ต่อไป: {
      ค่า: 3,
      ต่อไป: {
        ค่า: 4,
        ถัดไป: โมฆะ
      -
    -
  -
-

ฟังก์ชั่น printReverseList (รายการ) {

  ถ้า (รายการถัดไป) {
    printReverseList (รายการถัดไป);
  -

  การแจ้งเตือน(list.value);
-

printReverseList (รายการ);

การใช้ลูป

การใช้ลูป

ตัวแปรลูปยังซับซ้อนกว่าเอาท์พุตโดยตรงเล็กน้อย

ไม่มีทางที่จะได้ค่าสุดท้ายใน list ของเรา เรายัง "ย้อนกลับไป" ไม่ได้

ดังนั้นสิ่งที่เราทำได้คือขั้นแรกไล่ดูไอเท็มตามลำดับโดยตรงและจดจำมันในอาร์เรย์ จากนั้นจึงส่งออกสิ่งที่เราจำได้ในลำดับย้อนกลับ:

 ให้รายการ = {
  ค่า: 1,
  ต่อไป: {
    ค่า: 2,
    ต่อไป: {
      ค่า: 3,
      ต่อไป: {
        ค่า: 4,
        ถัดไป: โมฆะ
      -
    -
  -
-

ฟังก์ชั่น printReverseList (รายการ) {
  ให้ arr = [];
  ให้ tmp = รายการ;

  ในขณะที่ (tmp) {
    arr.push(tmp.value);
    tmp = tmp.ถัดไป;
  -

  สำหรับ (ให้ i = arr.length - 1; i >= 0; i--) {
    การแจ้งเตือน( arr[i] );
  -
-

printReverseList (รายการ);

โปรดทราบว่าโซลูชันแบบเรียกซ้ำจริง ๆ แล้วทำงานเหมือนกันทุกประการ: เป็นไปตามรายการ จดจำรายการในสายการเรียกที่ซ้อนกัน (ในสแต็กบริบทการดำเนินการ) จากนั้นจึงส่งออกรายการเหล่านั้น