ผู้ที่มีประสบการณ์ในการเขียนโปรแกรมจะต้องคุ้นเคยกับฟังก์ชันแบบเรียกซ้ำ เรามักจะใช้ การเรียกซ้ำ เพื่อแก้ไขปัญหาที่ซับซ้อนต่างๆ มากมาย และพวกเขายังสามารถเพิ่มประสิทธิภาพโค้ดของเราได้อีกด้วย เมื่อใช้การเรียกซ้ำ:
1) การเรียกซ้ำกำลังเรียกใช้ฟังก์ชันภายในฟังก์ชันนั้นเอง
2) ประสิทธิภาพของการเรียกซ้ำค่อนข้างต่ำ และไม่แนะนำให้ใช้หากมีกำหนดเวลา
3) จำเป็นต้องมีเงื่อนไขการสิ้นสุดที่ชัดเจนในกระบวนการแบบเรียกซ้ำ นั่นคือ ทางออกแบบเรียกซ้ำ
มาอธิบายฟังก์ชันแบบเรียกซ้ำโดยละเอียดด้านล่าง
ขั้นแรกเรามาดูการใช้การเรียกซ้ำอย่างง่ายผ่านตัวอย่าง:
m=int(input('ป้อนตัวเลข:'))deftest(x):x+=2ifx<100:test(x)else:print('X สุดท้ายคือ:',x)test(m)ผลลัพธ์คือ:
ป้อนตัวเลข: 20 และ x สุดท้ายคือ: 100
มาวิเคราะห์ตัวอย่างนี้กัน อันดับแรก ในบรรทัดแรกของโค้ด เราป้อนจำนวนเต็ม ในบรรทัดสุดท้าย m จะถูกส่งผ่านเป็นพารามิเตอร์จริงไปยังเมธอด test() ในเมธอด test() นั้น x จะถูกบวกด้วย 2 ก่อน แล้วจึงตัดสิน หากค่า x น้อยกว่า 100 ให้เรียกใช้ฟังก์ชันนี้อีกครั้ง เมื่อเรียกใช้ ค่าปัจจุบันของ x จะถูกใช้เป็นพารามิเตอร์จริงในการเข้าร่วมการโทรซ้ำ =100 พอใจแล้ว
ดูแผนภาพด้านล่าง:
นั่นคือหากไม่ตรงตามเงื่อนไข มันจะกลับไปยังเลเยอร์นอกสุดและเรียกใช้ฟังก์ชันนี้
เมื่อพูดถึงปัญหาแบบคลาสสิกในอัลกอริธึมแบบเรียกซ้ำ ลำดับฟีโบนักชี และ หอคอยแห่งฮานอย จะแยกจากกันไม่ได้ ที่นี่เราจะอธิบายวิธีใช้การเรียกซ้ำเพื่อแก้ลำดับฟีโบนักชี
ก่อนอื่น เราต้องรู้ว่าสูตรเรียกซ้ำของลำดับฟีโบนัชชีคือ F(n)=F(n-1)+F(n-2), F(1) และ F(2) เท่ากับ 1 เรา สามารถใช้การเรียกซ้ำ เพื่อค้นหาค่าของรายการในลำดับฟีโบนัชชี
มีหลายวิธีที่เราสามารถใช้เพื่อแก้ปัญหาลำดับฟีโบนักชีได้
ขั้นแรกเราใช้วิธีเรียกซ้ำที่ใช้กันทั่วไปเพื่อแก้ไขปัญหานี้:
N=int(input(กรอกจำนวนรายการที่จะได้รับ:))deffibonacci(n):ifn<=2:#ถ้าน้อยกว่าหรือเท่ากับ 2 ให้ตั้งค่า n เป็น 1 return1else:returnfibonacci(n-1) +fibonacci(n-2)print ('ค่าที่สอดคล้องกันคือ',fibonacci(n))ผลลัพธ์คือ:
ป้อนจำนวนรายการที่คุณต้องการได้รับ: 4 สอดคล้องกับ 3
สำหรับวิธีการเรียกซ้ำนี้ เมื่อเราป้อนค่า 4 การดำเนินการต่อไปนี้จะดำเนินการแบบเรียกซ้ำ:
ฟีโบนัชชี(3)+ฟีโบนัชชี(2)=ฟีโบนัชชี(2)+ฟีโบนัชชี(1)+ฟีโบนัชชี(2)
จากนั้นเราจะเห็นว่าค่าของเทอมที่สี่คือ 1+1+1=3
ที่จริงแล้ว วิธีการแก้ปัญหานี้ทำให้เสียเวลาเพราะต้องใช้การวนซ้ำมากเกินไป เรายังสามารถใช้พื้นที่แทนเวลาในการแก้ปัญหานี้ได้
รหัสมีดังนี้:
n=int(input(กรอกจำนวนเงื่อนไขที่จะได้รับ:))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print (' ค่าที่สอดคล้องกันคือ',ฟีโบนัชชี[n-1])ผลลัพธ์คือ:
ป้อนจำนวนรายการที่คุณต้องการได้รับ: 4 สอดคล้องกับ 3
ด้วยวิธีนี้เราระบุค่าของสองรายการแรกในรายการแล้วสำหรับจำนวน n ของรายการที่เราต้องการแก้เราจะเติมรายการหมายเลขฟีโบนัชชีโดยตรงไปยังรายการที่เราต้องการผ่านสูตร และสุดท้ายตามดัชนี ค่าจะค้นหาผลลัพธ์เอาต์พุตที่เกี่ยวข้องโดยตรง
เพียงเท่านี้สำหรับฟังก์ชันแบบเรียกซ้ำ ดังที่กล่าวไว้ข้างต้น เราควรให้ความสนใจเป็นพิเศษกับการออกแบบเรียกซ้ำและการจำกัด เวลา เกินเวลาที่กำหนด ในเวลานี้ เราจำเป็นต้องเปลี่ยนความคิดของเราในการแก้ปัญหา วิธีที่สองที่กล่าวมาข้างต้นสามารถช่วยทุกคนในการแก้ปัญหาได้