ในการเขียนโปรแกรมคอมพิวเตอร์ประเภทข้อมูลแบบเรียกซ้ำ (recursive data type)คือประเภทข้อมูลที่มีนิยามประกอบด้วยค่าที่มีประเภทเดียวกัน เรียกอีกอย่างว่า ประเภทข้อมูลที่กำหนดแบบเรียกซ้ำ (recursively defined) , ประเภทข้อมูล ที่กำหนดแบบอุปนัย (inductively defined ) หรือประเภทข้อมูลแบบอุปนัย (inductive data type ) โดยทั่วไปแล้ว ข้อมูลประเภทเรียกซ้ำจะถูกมองว่าเป็นกราฟแบบมีทิศทาง (directed graph )

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

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

ตัวอย่างเช่น ประเภท ข้อมูลลิสต์ในภาษาฮัสเคลล์ :

รายการข้อมูลa = ว่างเปล่า| Cons a ( รายการa )

สิ่งนี้บ่งชี้ว่ารายการของตัวอักษร 'a' นั้นเป็นได้ทั้งรายการว่างเปล่าหรือเซลล์ consที่ประกอบด้วยตัวอักษร 'a' ('หัว' ของรายการ) และรายการอื่น ('ท้าย')

อีกตัวอย่างหนึ่งคือชนิดข้อมูลแบบลิงก์เดี่ยวที่คล้ายกันในภาษา Java :

public class LinkedList < E > { private E value ; private LinkedList < E > next ;// คอนสตรัคเตอร์และเมธอด... }

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

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

f: [t[1], ..., t[k]] t: vf 

ป่าfประกอบด้วยรายการของต้นไม้ ในขณะที่ต้นไม้tประกอบด้วยคู่ของค่าvและป่าf (ลูกของมัน) คำจำกัดความนี้สง่างามและง่ายต่อการใช้งานในเชิงนามธรรม (เช่น เมื่อพิสูจน์ทฤษฎีบทเกี่ยวกับคุณสมบัติของต้นไม้) เนื่องจากมันแสดงต้นไม้ในแง่ที่เรียบง่าย: รายการของประเภทหนึ่ง และคู่ของสองประเภท

นิยามแบบเรียกซ้ำซึ่งกันและกันนี้สามารถแปลงเป็นนิยามแบบเรียกซ้ำครั้งเดียวได้โดยการแทรกนิยามของป่าเข้าไป:

t: v [t[1], ..., t[k]] 

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

ในStandard MLประเภทข้อมูลต้นไม้และป่าสามารถกำหนดแบบเรียกซ้ำซึ่งกันและกันได้ดังต่อไปนี้ โดยอนุญาตให้มีต้นไม้ว่าง: ^{[ 1 ]}

ชนิดข้อมูล'a tree = ว่างเปล่า| โหนดของ'a * 'a forest และ'a forest = ว่างเปล่า| ข้อเสียของ'a tree * 'a forest

ในภาษา Haskell สามารถกำหนดชนิดข้อมูล tree และ forest ได้ในลักษณะเดียวกัน:

ข้อมูลTree a = Empty | Node ( a , Forest a )ข้อมูลForest a = Nil | Cons ( Tree a ) ( Forest a )

ในทฤษฎีประเภท (type theory ) ประเภทแบบเรียกซ้ำ (recursive type) มีรูปแบบทั่วไปเป็นμα . Tโดยที่ตัวแปรประเภทαอาจปรากฏในประเภทTและหมายถึงประเภททั้งหมดนั้นเอง

ตัวอย่างเช่น จำนวนธรรมชาติ (ดูเลขคณิตของพีอาโน ) อาจถูกกำหนดโดยชนิดข้อมูลของ Haskell ได้:

ข้อมูลNat = ศูนย์| Succ Nat

ในทฤษฎีประเภท เราจะกล่าวว่า: โดยที่แขนทั้งสองข้างของประเภทผลรวมแทนตัวสร้างข้อมูล Zero และ Succ Zero ไม่รับอาร์กิวเมนต์ใดๆ (ดังนั้นจึงแทนด้วยประเภทหน่วย ) และ Succ รับ Nat อีกตัวหนึ่ง (ดังนั้นจึงเป็นองค์ประกอบอีกตัวหนึ่งของ) ${\displaystyle {\text{nat}}=\mu \alpha .1+\alpha }$${\displaystyle \mu \alpha .1+\alpha }$

ประเภทเรียกซ้ำมีสองรูปแบบ ได้แก่ ประเภทเรียกซ้ำแบบไอโซ (isorecursive types) และประเภทเรียกซ้ำแบบเอกเกอเร (equirecursive types) ความแตกต่างระหว่างสองรูปแบบนี้อยู่ที่วิธีการนำเทอมของประเภทเรียกซ้ำเข้ามาและกำจัดออกไป

สำหรับชนิดข้อมูลแบบไอโซเคิร์ซซีฟ ชนิดข้อมูลแบบเรียกซ้ำและการขยาย (หรือการคลี่คลาย ) (โดยที่สัญลักษณ์บ่งชี้ว่าอินสแตนซ์ทั้งหมดของ Z ถูกแทนที่ด้วย Y ใน X) เป็นชนิดข้อมูลที่แตกต่างกัน (และไม่ทับซ้อนกัน) โดยมีโครงสร้างเทอมพิเศษ ซึ่งโดยทั่วไปเรียกว่าrollและunrollที่สร้างไอโซมอร์ฟิซึมระหว่างกัน กล่าวคือและและทั้งสองนี้เป็นฟังก์ชันผกผันกัน ${\displaystyle \mu \alpha .T}$${\displaystyle T[\mu \alpha .T/\alpha ]}$${\displaystyle X[Y/Z]}$${\displaystyle roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T}$${\displaystyle unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]}$

ภายใต้กฎ equirecursive ประเภทแบบเรียกซ้ำและการคลี่คลายของประเภทนั้นจะเท่ากันกล่าวคือ นิพจน์ประเภททั้งสองนั้นเข้าใจได้ว่าหมายถึงประเภทเดียวกัน ในความเป็นจริง ทฤษฎีส่วนใหญ่ของประเภท equirecursive ไปไกลกว่านั้นและระบุโดยพื้นฐานว่านิพจน์ประเภทสองแบบใดๆ ที่มี "การขยายอนันต์" เดียวกันนั้นเทียบเท่ากัน ผลจากกฎเหล่านี้ ประเภท equirecursive จึงทำให้ระบบประเภทมีความซับซ้อนมากกว่าประเภท isorecursive อย่างมาก ปัญหาเชิงอัลกอริทึม เช่น การตรวจสอบประเภทและการอนุมานประเภทก็ยากขึ้นสำหรับประเภท equirecursive เช่นกัน เนื่องจากการเปรียบเทียบโดยตรงไม่มีความหมายในประเภท equirecursive จึงสามารถแปลงเป็นรูปแบบมาตรฐานได้ในเวลา O(n log n) ซึ่งสามารถเปรียบเทียบได้ง่าย^{[ 2 ]}${\displaystyle \mu \alpha .T}$${\displaystyle T[\mu \alpha .T/\alpha ]}$

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

ในTypeScriptอนุญาตให้มีการเรียกซ้ำในนามแฝงประเภท^{[ 4 ]}

• นิยามแบบเรียกซ้ำ
• ประเภทข้อมูลพีชคณิต
• ประเภทเหนี่ยวนำ
• โหนด (วิทยาการคอมพิวเตอร์)

• Harper, Robert (1998), การประกาศชนิดข้อมูล , เก็บถาวรจากต้นฉบับเมื่อ 1 ตุลาคม 1999