การเรียกซ้ำเกิดขึ้นเมื่อคำจำกัดความของแนวคิดหรือกระบวนการขึ้นอยู่กับเวอร์ชันที่ง่ายกว่าหรือก่อนหน้าของตัวมันเอง^{[ 1 ]}การเรียกซ้ำถูกใช้ในหลากหลายสาขาวิชาตั้งแต่ภาษาศาสตร์ไปจนถึงตรรกศาสตร์การประยุกต์ใช้การเรียกซ้ำที่พบบ่อยที่สุดคือในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ซึ่งฟังก์ชันที่กำลังถูกกำหนดจะถูกนำไปใช้ภายในคำจำกัดความของมันเอง แม้ว่าสิ่งนี้จะกำหนดอินสแตนซ์ (ค่าฟังก์ชัน) จำนวนอนันต์อย่างเห็นได้ชัด แต่มักจะทำในลักษณะที่ไม่มีลูปอนันต์หรือห่วงโซ่การอ้างอิงอนันต์เกิดขึ้นได้

กระบวนการที่แสดงลักษณะการเรียกซ้ำเรียกว่ากระบวนการแบบเรียกซ้ำ ภาพที่แสดงผลลัพธ์ แบบเรียกซ้ำนั้นแสดงด้วยภาพวิดีโอ เช่นเดียวกับ กระจกอินฟินิตี้

ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กลุ่มของวัตถุหรือวิธีการจะแสดงพฤติกรรมแบบเรียกซ้ำเมื่อสามารถกำหนดได้ด้วยคุณสมบัติสองประการดังนี้:

• กรณีพื้นฐานอย่างง่าย(หรือหลายกรณี) — สถานการณ์ที่สิ้นสุดลงโดยไม่ได้ใช้การเรียกซ้ำเพื่อหาคำตอบ
• ขั้นตอนแบบเรียกซ้ำ — ชุดของกฎที่ลดกรณีต่างๆ ที่ตามมาทั้งหมดให้เข้าใกล้กรณีพื้นฐาน

ตัวอย่างเช่น ต่อไปนี้คือคำจำกัดความแบบเวียนเกิดของบรรพบุรุษ ของบุคคล บรรพบุรุษของบุคคลอาจเป็น:

• ผู้ปกครอง ( กรณีพื้นฐาน ) หรือ
• บรรพบุรุษของบิดามารดา ( ขั้นตอนแบบวนซ้ำ )

ลำดับฟิโบนาชชีเป็นอีกตัวอย่างคลาสสิกของการเรียกซ้ำ:

Fib(0) = 0เป็นกรณีฐานที่ 1

Fib(1) = 1เป็นกรณีฐาน 2

สำหรับจำนวนเต็มn > 1 ทุก ตัวFib( n ) = Fib( n − 1) + Fib( n − 2 )

สัจพจน์ทางคณิตศาสตร์จำนวนมากมีพื้นฐานมาจากกฎการเรียกซ้ำ ตัวอย่างเช่น นิยามอย่างเป็นทางการของจำนวนธรรมชาติโดยสัจพจน์ของ Peanoสามารถอธิบายได้ว่า: "ศูนย์เป็นจำนวนธรรมชาติ และจำนวนธรรมชาติแต่ละจำนวนจะมีตัวสืบทอด ซึ่งเป็นจำนวนธรรมชาติเช่นกัน" ^{[ 2 ]}ด้วยกรณีพื้นฐานและกฎการเรียกซ้ำนี้ เราสามารถสร้างเซตของจำนวนธรรมชาติทั้งหมดได้

วัตถุทางคณิตศาสตร์อื่นๆ ที่นิยามแบบเวียนซ้ำ ได้แก่แฟกทอเรียลฟังก์ชัน ( เช่นความสัมพันธ์เวียนเกิด ) เซต (เช่นเซตไตรภาคของแคนเตอร์ ) และแฟรกทัล

นอกจากนี้ยังมีคำจำกัดความของการเรียกซ้ำในเชิงเสียดสีอีกหลายแบบ โปรดดูที่ อารมณ์ขันแบบเรียกซ้ำ

การเรียกซ้ำคือกระบวนการที่ขั้นตอนหนึ่งดำเนินไปเมื่อขั้นตอนหนึ่งของกระบวนการเกี่ยวข้องกับการเรียกใช้กระบวนการนั้นเอง กระบวนการที่ดำเนินไปโดยการเรียกซ้ำเรียกว่า 'แบบเรียกซ้ำ' ^{[ 3 ]}

เพื่อให้เข้าใจเรื่องการเรียกซ้ำ (recursion) เราต้องแยกแยะความแตกต่างระหว่างกระบวนการ (procedure) และการเรียกใช้กระบวนการ (running of a procedure) กระบวนการคือชุดของขั้นตอนที่อิงตามชุดของกฎ ในขณะที่การเรียกใช้กระบวนการนั้นเกี่ยวข้องกับการปฏิบัติตามกฎและดำเนินการตามขั้นตอนจริง ๆ

การเรียกซ้ำมีความเกี่ยวข้องกับ แต่ไม่ใช่สิ่งเดียวกันกับ การอ้างอิงภายในข้อกำหนดของกระบวนการไปยังการดำเนินการของกระบวนการอื่น

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

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

นักภาษาศาสตร์Noam Chomskyและอีกหลายคนได้โต้แย้งว่า การที่ไม่มีขีดจำกัดสูงสุดของจำนวนประโยคไวยากรณ์ในภาษา และการที่ไม่มีขีดจำกัดสูงสุดของความยาวประโยคไวยากรณ์ (นอกเหนือจากข้อจำกัดในทางปฏิบัติ เช่น เวลาที่มีอยู่ในการพูดประโยคหนึ่ง) สามารถอธิบายได้ว่าเป็นผลสืบเนื่องมาจากการเรียกซ้ำในภาษาธรรมชาติ^{[ 4 ] [ 5 ]}

นอกจากประโยคแล้ว ยังมีโครงสร้างอีกมากมายที่สามารถกำหนดแบบเรียกซ้ำได้ และด้วยเหตุนี้ ประโยคจึงสามารถฝังตัวอย่างของหมวดหมู่หนึ่งไว้ภายในอีกหมวดหมู่หนึ่งได้หลายวิธี^{[ 6 ]}ตลอดหลายปีที่ผ่านมา ภาษาโดยทั่วไปพิสูจน์แล้วว่าเหมาะสมกับการวิเคราะห์ประเภทนี้

แนวคิดที่ได้รับการยอมรับโดยทั่วไปว่าการเรียกซ้ำเป็นคุณสมบัติที่สำคัญของภาษามนุษย์นั้นถูกท้าทายโดยDaniel Everettโดยอ้างอิงจากข้อกล่าวอ้างของเขาเกี่ยวกับภาษา Pirahã Andrew Nevins, David Pesetsky และ Cilene Rodrigues เป็นหนึ่งในหลายคนที่โต้แย้งเรื่องนี้^{[ 7 ]}การอ้างอิงตนเองในวรรณกรรมสามารถโต้แย้งได้ว่าแตกต่างจากการเรียกซ้ำทางคณิตศาสตร์หรือตรรกะในทุกกรณี^{[ 8 ]}

การเรียกซ้ำมีบทบาทสำคัญไม่เพียงแต่ในไวยากรณ์เท่านั้น แต่ยังรวมถึงความหมายของภาษาธรรมชาติ ด้วย ตัวอย่างเช่น คำว่า " และ " สามารถตีความได้ว่าเป็นฟังก์ชันที่สามารถนำไปใช้กับความหมายของประโยคเพื่อสร้างประโยคใหม่ และเช่นเดียวกันสำหรับความหมายของวลีคำนาม ความหมายของวลีคำกริยา และอื่นๆ นอกจากนี้ยังสามารถใช้กับคำกริยาที่ไม่ต้องการกรรม คำกริยาที่ต้องการกรรม หรือคำกริยาที่ต้องการกรรมสองตัวได้ เพื่อให้มีการกำหนดความหมายเดียวที่ยืดหยุ่นได้อย่างเหมาะสมและโดยทั่วไปจะกำหนดไว้เพื่อให้สามารถรับความหมายประเภทต่างๆ เหล่านี้เป็นอาร์กิวเมนต์ได้ สามารถทำได้โดยการกำหนดสำหรับกรณีง่ายๆ ที่รวมประโยคเข้าด้วยกัน จากนั้นกำหนดกรณีอื่นๆ ซ้ำๆ ในแง่ของกรณีง่ายๆ นั้น^{[ 9 ]}

ไวยากรณ์แบบเรียกซ้ำคือไวยากรณ์เชิงรูปธรรมที่มีกฎการผลิต^แบบ เรียกซ้ำ [ ^{10 ]}

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

การเรียกซ้ำดู การเรียกซ้ำ^{[ 11 ]}

พบรูปแบบที่แตกต่างกันในหน้า 269 ของสารบัญ ใน หนังสือThe C Programming Language บางฉบับของBrian KernighanและDennis Ritchieโดยรายการในสารบัญอ้างอิงถึงตัวเองแบบวนซ้ำ ("recursion 86, 139, 141, 182, 202, 269") เวอร์ชันแรกๆ ของมุกตลกนี้สามารถพบได้ในหนังสือLet's talk Lispโดย Laurent Siklóssy (ตีพิมพ์โดย Prentice Hall PTR เมื่อวันที่ 1 ธันวาคม 1975 โดยมีลิขสิทธิ์ปี 1976) และในหนังสือSoftware Toolsโดย Kernighan และ Plauger (ตีพิมพ์โดย Addison-Wesley Professional เมื่อวันที่ 11 มกราคม 1976) มุกตลกนี้ยังปรากฏในหนังสือ The UNIX Programming Environmentโดย Kernighan และ Pike ด้วย แต่ไม่ปรากฏในฉบับพิมพ์ครั้งแรกของThe C Programming Languageมุกตลกนี้เป็นส่วนหนึ่งของตำนานการเขียนโปรแกรมเชิงฟังก์ชันและแพร่หลายในชุมชนการเขียนโปรแกรมเชิงฟังก์ชันอยู่แล้วก่อนการตีพิมพ์หนังสือดังกล่าว^{[ 12 ] [ 13 ]}

เรื่องตลกอีกเรื่องหนึ่งคือ "เพื่อที่จะเข้าใจการเรียกซ้ำ คุณต้องเข้าใจการเรียกซ้ำ" ^{[ 11 ]}ในเวอร์ชันภาษาอังกฤษของเครื่องมือค้นหาเว็บ Google เมื่อค้นหาคำว่า "recursion" เว็บไซต์จะแนะนำว่า "คุณหมายถึง: recursion หรือ ไม่" ^{[ 14 ]}รูปแบบอื่นคือข้อความต่อไปนี้จากAndrew Plotkin : "ถ้าคุณรู้อยู่แล้วว่าการเรียกซ้ำคืออะไร ก็แค่จำคำตอบไว้ มิฉะนั้น ให้หาคนที่ยืนอยู่ใกล้Douglas Hofstadterมากกว่าคุณ แล้วถามเขาหรือเธอว่าการเรียกซ้ำคืออะไร"

ตัวย่อแบบวนซ้ำเป็นอีกตัวอย่างหนึ่งของอารมณ์ขันแบบวนซ้ำเช่นPHP ย่อมาจาก "PHP Hypertext Preprocessor" (โปรแกรมประมวลผลข้อความไฮเปอร์เท็กซ์), WINEย่อมาจาก "WINE Is Not an Emulator" (โปรแกรม WINE ไม่ใช่โปรแกรมจำลอง), RPMย่อมาจาก "RPM Package manager" (ตัวจัดการแพ็กเกจ RPM), GNUย่อมาจาก "GNU's not Unix" (ระบบ GNU ไม่ใช่ Unix) และSPARQLย่อมาจาก "SPARQL Protocol and RDF Query Language" (ภาษาค้นหาโปรโตคอล SPARQL และ RDF)

ตัวอย่างที่เป็นแบบอย่างของเซตที่กำหนดโดยวิธีเวียนเกิดคือจำนวนธรรมชาติ :

0 อยู่ใน${\displaystyle \mathbb {N} }$

ถ้าnอยู่ในแล้วn + 1 ก็อยู่ใน เช่นกัน${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$

เซตของจำนวนธรรมชาติคือเซตที่เล็กที่สุดที่สอดคล้องกับคุณสมบัติสองข้อก่อนหน้านี้

ในตรรกศาสตร์ทางคณิตศาสตร์สัจพจน์ของพีอาโน (หรือสัจพจน์ของพีอาโน หรือสัจพจน์ของเดเดคินด์-พีอาโน) คือสัจพจน์สำหรับจำนวนธรรมชาติ ซึ่งนำเสนอโดยริชาร์ด เดเดคินด์ นักคณิตศาสตร์ชาวเยอรมัน และจูเซปเป พีอาโน นักคณิตศาสตร์ชาวอิตาลี ในศตวรรษที่ 19 สัจพจน์ของพีอาโนนิยามจำนวนธรรมชาติโดยอ้างอิงถึงฟังก์ชันผู้สืบทอดแบบเวียนเกิด และการบวกและการคูณเป็นฟังก์ชันเวียนเกิด

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

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

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

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

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

การเขียนโปรแกรมเชิงพลวัต (Dynamic programming)เป็นแนวทางในการหาค่าเหมาะสมที่สุดที่แปลงปัญหาการหาค่าเหมาะสมที่สุดแบบหลายช่วงเวลาหรือหลายขั้นตอนให้อยู่ในรูปแบบเวียนเกิด ผลลัพธ์สำคัญในการเขียนโปรแกรมเชิงพลวัตคือสมการเบลล์แมน (Bellman equation ) ซึ่งเขียนค่าของปัญหาการหาค่าเหมาะสมที่สุด ณ เวลาที่เร็วกว่า (หรือขั้นตอนที่เร็วกว่า) ในรูปของค่า ณ เวลาที่ช้ากว่า (หรือขั้นตอนที่ช้ากว่า)

ในทฤษฎีเซตนี่คือทฤษฎีบทที่รับประกันว่าฟังก์ชันที่กำหนดแบบเวียนเกิดนั้นมีอยู่จริง กำหนดให้เซตX , สมาชิกaของXและฟังก์ชันf : X → X ทฤษฎีบทนี้กล่าวว่ามีฟังก์ชัน f เพียงฟังก์ชันเดียว(โดยที่X หมายถึงเซตของจำนวนธรรมชาติรวมถึงศูนย์) ที่ทำให้ f : X → X${\displaystyle F:\mathbb {N} \to X}$${\displaystyle \mathbb {N} }$

${\displaystyle F(0)=a}$

${\displaystyle F(n+1)=f(F(n))}$

สำหรับจำนวนธรรมชาติn ใด ๆ

Dedekind เป็นคนแรกที่ตั้งปัญหาของคำจำกัดความที่ไม่ซ้ำกันของฟังก์ชันทฤษฎีเซตบนโดยการเรียกซ้ำ และได้ร่างข้อโต้แย้งไว้ในบทความปี 1888 เรื่อง "Was sind und was sollen die Zahlen?" ^{[ 15 ]}${\displaystyle \mathbb {N} }$

แหล่งที่มา: ^{[ 16 ]}

อนุญาต. ${\displaystyle S=\{A\subseteq {\mathbb {N} }\times X:(0,a)\in A{\text{ และถ้า }}(x,y)\in A{\text{ แล้ว }}(x+1,f(y))\in A\}}$

S ไม่ว่างเปล่าเนื่องจากให้เนื่องจากมันอยู่ในทุก ๆยิ่งไปกว่านั้น ถ้าแล้วสำหรับทุก ๆแต่แล้วสำหรับทุก ๆดังนั้นดังนั้นและมันเป็นองค์ประกอบที่เล็กที่สุดของ S ${\displaystyle {\mathbb {N} }\times X\in S}$${\displaystyle g=\bigcap _{A\in S}A}$${\displaystyle (0,a)\in g}$${\displaystyle A\in S}$${\displaystyle (x,y)\in g}$${\displaystyle (x,y)\in A}$${\displaystyle A\in S}$${\displaystyle (x+1,f(y))\in A}$${\displaystyle A\in S}$${\displaystyle (x+1,f(y))\in g}$${\displaystyle g\in S}$

ให้. เนื่องจาก. สมมติว่า. ดังนั้นสำหรับบาง. สิ่งนี้ให้. ดังนั้น. จึงสรุปได้โดยการอุปมานทางคณิตศาสตร์ว่า. ${\displaystyle T=\{n\in {\mathbb {N} }:\exists z\in X{\text{ such that }}(n,z)\in g\}}$${\displaystyle 0\in T}$${\displaystyle (0,a)\in g}$${\displaystyle n\in T}$${\displaystyle (n,z)\in g}$${\displaystyle z\in X}$${\displaystyle (n+1,f(z))\in g}$${\displaystyle n+1\in T}$${\displaystyle T={\mathbb {N} }}$

ให้. สมมติเพื่อความขัดแย้งว่า. นั่นคือ สมมติว่าเรามีนอกจากนี้ โดยที่. ดังนั้น ซึ่ง ขัดแย้งกับข้อเท็จจริงที่ว่า g เป็นสมาชิกที่เล็กที่สุดของ S ดังนั้น. ${\displaystyle U=\{x\in {\mathbb {N} }:{\text{ถ้า }}(x,y),(x,z)\in g{\text{ แล้ว }}y=z\}}$${\displaystyle 0\notin U}$${\displaystyle (0,z)}$${\displaystyle (0,a)\in g}$${\displaystyle z\neq a}$${\displaystyle g\backslash \{(0,z)\}\in S}$${\displaystyle 0\in U}$

เราแสดงให้เห็นว่าถ้าแล้วสมมติว่าไม่ใช่เช่นนั้น ดังนั้น ดังนั้นเนื่องจากและจึงมีค่าที่ไม่ซ้ำกันเพียงค่าเดียวที่มีดังนั้นเนื่องจากจึงมีนอกเหนือจาก โดยที่แต่แล้วซึ่งขัดแย้งกับข้อเท็จจริงที่ว่า g เป็นองค์ประกอบที่เล็กที่สุดของ S การอุปมานทางคณิตศาสตร์จึงกล่าวว่าดังนั้นจึงมีฟังก์ชันที่มีกราฟเป็น g ให้เรียกว่า F ${\displaystyle x\in U}$${\displaystyle x+1\in U}$${\displaystyle \exists m\in U}$${\displaystyle m+1\notin U}$${\displaystyle m\in U}$${\displaystyle T={\mathbb {N} }}$${\displaystyle n\in \mathbb {N} }$${\displaystyle (m,n)\in g}$${\displaystyle (m+1,f(n))\in g}$${\displaystyle m+1\notin U}$${\displaystyle (m+1,z)\in g}$${\displaystyle (m+1,f(n))\in g}$${\displaystyle z\neq f(n)}$${\displaystyle g\backslash \{(m+1,z)\}\in S}$${\displaystyle U={\mathbb {N} }}$

พิจารณาฟังก์ชันสองฟังก์ชันและโดยที่: ${\displaystyle F:\mathbb {N} \to X}$${\displaystyle G:\mathbb {N} \to X}$

${\displaystyle F(0)=a}$

${\displaystyle G(0)=a}$

${\displaystyle F(n+1)=f(F(n))}$

${\displaystyle G(n+1)=f(G(n))}$

โดยที่a เป็นสมาชิกของX

สามารถพิสูจน์ได้โดยการอุปมานทางคณิตศาสตร์ว่าF ( n ) = G ( n ) สำหรับจำนวนธรรมชาติ nทุกจำนวน :

กรณีพื้นฐาน : F (0) = a = G (0)ดังนั้นความเท่าเทียมกันจึงเป็นจริงสำหรับn = 0

ขั้นตอนอุปนัย : สมมติว่าF ( k ) = G ( k )สำหรับบางค่าแล้ว F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1 ) ${\displaystyle k\in \mathbb {N} }$

ดังนั้นF ( k ) = G ( k )จึงหมายความว่าF ( k + 1) = G ( k + 1 )

โดยการอุปนัยF ( n ) = G ( n )สำหรับทุกๆ ${\displaystyle n\in \mathbb {N} }$

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

ตัวอย่างคลาสสิกของการเรียกซ้ำคือคำนิยามของ ฟังก์ชัน แฟกทอเรียลซึ่งแสดงไว้ในโค้ด Python ดังนี้:

def factorial ( n ): if n > 0 : return n * factorial ( n - 1 ) else : return 1

ฟังก์ชันนี้เรียกตัวเองซ้ำโดยใช้ค่าที่น้อยกว่าของอินพุต(n - 1)และคูณผลลัพธ์ของการเรียกซ้ำด้วยค่าดังกล่าวไปเรื่อยๆnจนกว่าจะถึงค่าพื้นฐานซึ่งคล้ายคลึงกับนิยามทางคณิตศาสตร์ของแฟกทอเรียล

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

ความสัมพันธ์เวียนเกิดคือสมการที่กำหนดลำดับหนึ่งหรือมากกว่านั้นแบบเวียนเกิด ความสัมพันธ์เวียนเกิดบางประเภทสามารถ "แก้" เพื่อให้ได้นิยามที่ไม่ใช้การเวียนเกิด (เช่นนิพจน์ในรูปแบบปิด )

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

รูปร่างที่ดูเหมือนจะถูกสร้างขึ้นโดยกระบวนการวนซ้ำบางครั้งปรากฏในพืชและสัตว์ เช่น ในโครงสร้างแบบแตกแขนงซึ่งส่วนใหญ่แตกแขนงออกเป็นสองส่วนหรือมากกว่านั้นที่เล็กกว่า ตัวอย่างหนึ่งคือบรอกโคลีโรมาเนสโก^{[ 17 ]}

บางครั้งใน วิทยาการจัดการการเรียกซ้ำหมายถึงกระบวนการวนซ้ำผ่านระดับนามธรรมในหน่วยงานธุรกิจขนาดใหญ่^{[ 18 ]}ตัวอย่างทั่วไปคือลักษณะการเรียกซ้ำของลำดับชั้น การจัดการ ตั้งแต่การจัดการระดับปฏิบัติการไปจนถึงการจัดการระดับสูง  ผ่านการจัดการระดับกลางนอกจากนี้ยังครอบคลุมถึงประเด็นที่ใหญ่กว่าของโครงสร้างเงินทุนใน การกำกับ ดูแลกิจการ^{[ 19 ]}

ตุ๊กตามาตรโยชก้าเป็นตัวอย่างทางศิลปะเชิงกายภาพของแนวคิดการวนซ้ำ^{[ 20 ]}

การใช้ การเรียกซ้ำได้ถูกนำมาใช้ในงานจิตรกรรมตั้งแต่ภาพสามส่วน StefaneschiของGiottoซึ่งสร้างขึ้นในปี 1320 แผงกลางของภาพประกอบด้วยรูปของพระคาร์ดินัล Stefaneschi กำลังคุกเข่าและถือภาพสามส่วนนั้นไว้เป็นเครื่องบูชา^{[ 21 ] [ 22 ]}การปฏิบัตินี้โดยทั่วไปเรียกว่าปรากฏการณ์ Drosteซึ่งเป็นตัวอย่างของเทคนิค Mise en abyme

ภาพพิมพ์ "Print Gallery " ของMC Escher (1956) เป็นภาพพิมพ์ที่แสดงให้เห็นเมืองที่บิดเบี้ยวซึ่งมีแกลเลอรีที่บรรจุภาพนั้นไว้ภายในซ้ำแล้วซ้ำเล่าไปเรื่อยๆ^{[ 23 ]}

ภาพยนตร์เรื่อง Inceptionได้นำคำต่อท้าย-ceptionมาใช้กับคำนามเพื่อบ่งบอกถึงการวนซ้ำของบางสิ่งบางอย่างในเชิงล้อเล่น^{[ 24 ]}

• Corecursion  – ประเภทของอัลกอริธึมในวิทยาการคอมพิวเตอร์
• การเรียกซ้ำแบบลำดับค่า  – เทคนิคในการกำหนดฟังก์ชันเชิงทฤษฎีจำนวนโดยการเรียกซ้ำ
• ดิจิทัลอินฟินิตี้  – ศัพท์เฉพาะในทางภาษาศาสตร์เชิงทฤษฎี
• ความฝันซ้อนความฝัน (บทกวี)  – บทกวีโดย เอ็ดการ์ อัลลัน โพหน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง
• ปรากฏการณ์ดรอสเต  – เอฟเฟกต์ภาพแบบวนซ้ำ
• การตื่นนอนปลอม  – ความฝันที่ชัดเจนและสมจริงเกี่ยวกับการตื่นจากหลับนอน
• ตัวรวมจุดตรึง  – ฟังก์ชันอันดับสูง Y ซึ่ง Y f = f (Y f)หน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง
• การเรียงตัวแบบอนันต์ของฟังก์ชันวิเคราะห์  – ทฤษฎีทางคณิตศาสตร์เกี่ยวกับการเรียงตัวของฟังก์ชันที่ทำซ้ำแบบอนันต์
• ลูปอนันต์  – สำนวนการเขียนโปรแกรม
• การถอยหลังอย่างไม่มีที่สิ้นสุด  – ปัญหาเชิงปรัชญา
• ลัทธิอนันต์นิยม  – มุมมองทางปรัชญาที่ว่า ความรู้สามารถพิสูจน์ได้ด้วยห่วงโซ่เหตุผลที่ไม่มีที่สิ้นสุด
• กระจกอินฟินิตี้  – กระจกขนานหรือกระจกทำมุมที่สะท้อนซึ่งกันและกัน
• ฟังก์ชันแบบวนซ้ำ  – ผลลัพธ์จากการประยุกต์ใช้ฟังก์ชันทางคณิตศาสตร์ซ้ำๆ กัน
• การอุปมานทางคณิตศาสตร์  – รูปแบบหนึ่งของการพิสูจน์ทางคณิตศาสตร์
• Mise en abyme  – เทคนิคการซ้อนภาพหนึ่งภาพไว้ในตัวมันเอง หรือซ้อนเรื่องราวหนึ่งไว้ในอีกเรื่องราวหนึ่ง
• รีเอนแทรนต์ (ซับรูทีน)  – แนวคิดในการเขียนโปรแกรมคอมพิวเตอร์หน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง
• การอ้างอิงตนเอง  – ประโยค แนวคิด หรือสูตรที่อ้างถึงตัวมันเอง
• Spiegel im Spiegel  – ประพันธ์ดนตรีโดย Arvo Pärt, พ.ศ. 2521
• วงวนแปลกประหลาด  – วงจรที่วนเวียนอยู่ในลำดับชั้น
• การเรียก ซ้ำแบบหาง (Tail recursion)  – การเรียกใช้ซับรูทีนเป็นขั้นตอนสุดท้ายของกระบวนการหน้าเว็บที่แสดงคำอธิบายสั้น ๆ ของเป้าหมายการเปลี่ยนเส้นทาง
• สูตรอ้างอิงตนเองของทัปเปอร์  – สูตรที่แสดงภาพตัวเองเมื่อวาดเป็นกราฟ
• เต่าเรียงลงมาเรื่อยๆ  – คำแถลงการถอยหลังอย่างไม่มีที่สิ้นสุด

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับการเรียกซ้ำ (Recursion )

ค้นหาคำว่า "recursion"  หรือ"recursivity"ใน Wiktionary ซึ่งเป็นพจนานุกรมออนไลน์ฟรี

• การเรียกซ้ำ - บทเรียนโดย Alan Gauld
• ไฟล์ Zip ดาวน์โหลดทั้งหมด
• เนวินส์, แอนดรูว์ และ เดวิด เพเซตสกี และ ซิเลน โรดริเกส หลักฐานและการโต้แย้ง: คำตอบต่อเอเวอเร็ตต์ (2009) ภาษา 85.3: 671--681 (2009)