Corecursion
کمپیوٹر سائنس میں، کورکرشن ایک قسم کا آپریشن ہے جو ریکرشن سے دوگنا ہے۔ جبکہ ریکرشن تجزیاتی طور پر کام کرتا ہے، بیس کیس سے مزید ڈیٹا پر شروع ہوتا ہے اور اسے چھوٹے ڈیٹا میں توڑتا ہے اور اس وقت تک دہراتا ہے جب تک کہ کوئی بیس کیس تک نہ پہنچ جائے، کورکرشن مصنوعی طور پر کام کرتا ہے، بیس کیس سے شروع ہوتا ہے اور اسے تیار کرتا ہے، بار بار بیس کیس سے مزید ڈیٹا تیار کرتا ہے۔ سیدھے الفاظ میں، کورکورسیو الگورتھم ان اعداد و شمار کا استعمال کرتے ہیں جو وہ خود تیار کرتے ہیں، جیسے جیسے وہ دستیاب ہوتے ہیں، اور ضرورت ہوتی ہے، ڈیٹا کے مزید بٹس تیار کرنے کے لیے۔ اسی طرح کا لیکن الگ تصور جنریٹو ریکرشن ہے جس میں کورکرشن اور ریکرشن میں موروثی "سمت" کی کمی ہو سکتی ہے۔ جہاں ریکرشن پروگراموں کو من مانی طور پر پیچیدہ ڈیٹا پر کام کرنے کی اجازت دیتا ہے، جب تک کہ انہیں سادہ ڈیٹا (بیس کیسز) تک کم کیا جا سکے، کورکرسن پروگراموں کو من مانی طور پر پیچیدہ اور ممکنہ طور پر لامحدود ڈیٹا ڈھانچے، جیسے اسٹریمز تیار کرنے کی اجازت دیتا ہے، جب تک کہ یہ محدود مراحل کی ترتیب میں سادہ ڈیٹا (بیس کیسز) سے تیار کیا جا سکے۔ جہاں تکرار ختم نہیں ہو سکتا، کبھی بھی بنیادی حالت تک نہیں پہنچ سکتا، کورکرسن ایک بنیادی حالت سے شروع ہوتا ہے، اور اس طرح بعد کے اقدامات کو تعیناتی طور پر پیدا کرتا ہے، حالانکہ یہ غیر معینہ مدت تک آگے بڑھ سکتا ہے (اور اس طرح سخت تشخیص کے تحت ختم نہیں ہوتا ہے)، یا یہ پیدا ہونے سے زیادہ استعمال کر سکتا ہے اور اس طرح غیر پیداواری ہو جاتا ہے۔ بہت سے افعال جن کا روایتی طور پر تکرار کے طور پر تجزیہ کیا جاتا ہے، متبادل طور پر، اور زیادہ قدرتی طور پر، بنیادی تکرار کے افعال کے طور پر تشریح کی جا سکتی ہے جو کسی دیئے گئے مرحلے پر ختم ہو جاتے ہیں، مثال کے طور پر تکرار کے تعلقات جیسے کہ فیکٹوریئل۔ کورکرشن نتائج کے طور پر محدود اور لامحدود ڈیٹا ڈھانچے دونوں پیدا کر سکتا ہے، اور خود حوالہ جاتی ڈیٹا ڈھانچے کو استعمال کر سکتا ہے۔ کوریکرشن کو اکثر سست تشخیص کے ساتھ مل کر استعمال کیا جاتا ہے، تاکہ ممکنہ طور پر لامحدود ڈھانچے کا صرف ایک محدود ذیلی سیٹ تیار کیا جا سکے (بجائے اس کے کہ ایک ہی بار میں ایک مکمل لامحدود ڈھانچہ تیار کرنے کی کوشش کی جائے)۔ کوریکرشن فنکشنل پروگرامنگ میں ایک خاص طور پر اہم تصور ہے، جہاں کوریکرشن اور کوڈیٹا کل زبانوں کو لامحدود ڈیٹا ڈھانچے کے ساتھ کام کرنے کی اجازت دیتے ہیں۔ مثال کوریکرشن کو ریکرشن کے برعکس سمجھا جا سکتا ہے، جو کہ زیادہ واقف ہے۔ اگرچہ کورکرشن بنیادی طور پر فنکشنل پروگرامنگ میں دلچسپی کا حامل ہے، لیکن اسے لازمی پروگرامنگ کا استعمال کرتے ہوئے واضح کیا جا سکتا ہے، جو کہ ذیل میں پائتھون میں جنریٹر کی سہولت کا استعمال کرتے ہوئے کیا گیا ہے۔ ان مثالوں میں مقامی متغیرات کا استعمال کیا جاتا ہے، اور اقدار کو لازمی طور پر (تباہ کن) تفویض کیا جاتا ہے، حالانکہ یہ خالص فنکشنل پروگرامنگ میں کورکرن میں ضروری نہیں ہیں۔ خالص فنکشنل پروگرامنگ میں، مقامی متغیرات کو تفویض کرنے کے بجائے، یہ گنتی شدہ اقدار ایک غیر متغیر ترتیب بناتی ہیں، اور سابقہ اقدار تک خود حوالہ کے ذریعے رسائی حاصل کی جاتی ہے (ترتیب میں بعد کی اقدار، گنتی کی جانے والی ترتیب میں سابقہ اقدار کا حوالہ دیتی ہیں)۔ اسائنمنٹس محض اس کا اظہار لازمی نمونے میں کرتے ہیں اور واضح طور پر اس بات کی وضاحت کرتے ہیں کہ گنتی کہاں ہوتی ہے، جو نمائش کو واضح کرنے کا کام کرتی ہے۔ فیکٹوریل ریکرشن کی ایک کلاسک مثال فیکٹوریل کا حساب لگانا ہے، جس کی تعریف 0 سے بار بار کی جاتی ہے! : = 1 اور n! : = n × (n-1)! کسی دیئے گئے ان پٹ پر اپنے نتائج کا بار بار حساب لگانے کے لیے، ایک ریکرسو فنکشن (کی ایک کاپی) خود کو ایک مختلف ("چھوٹے") ان پٹ کے ساتھ کال کرتا ہے اور اس کال کے نتیجے کو اپنا نتیجہ بنانے کے لیے استعمال کرتا ہے۔ ریکرسو کال بھی ایسا ہی کرتی ہے، جب تک کہ بیس کیس تک نہ پہنچ جائے۔ اس طرح اس عمل میں ایک کال اسٹیک تیار ہوتا ہے۔ مثال کے طور پر، فیکس (3) کا حساب لگانے کے لیے، یہ بار بار فیکس (2)، فیکس (1)، فیکس (0) (اسٹیک کو "سمیٹنا") کو کال کرتا ہے، جس مقام پر ریکرشن فیکس (0) = 1 کے ساتھ ختم ہوتا ہے، اور پھر اسٹیک الٹا ترتیب میں کھل جاتا ہے اور نتائج کا حساب کال اسٹیک کے ساتھ ساتھ ابتدائی کال فریم فیکس (3) پر واپس جاتے ہوئے کیا جاتا ہے جو حتمی نتیجہ کا حساب لگانے کے لیے فیکس (2) = 2 کا نتیجہ استعمال کرتا ہے۔ 3 × 2 = 3 × فیکس (2) =: فیکس (3) اور آخر میں ریٹرن فیکس (3) = 6۔ اس مثال میں ایک فنکشن ایک واحد قدر واپس کرتا ہے۔ اس اسٹیک ان وائنڈنگ کی وضاحت کی جا سکتی ہے، جس میں فیکٹوریئل کورکورسیلی کو ایک تکرار کے طور پر بیان کیا جاتا ہے، جہاں کوئی کیس کے ساتھ شروع ہوتا ہے، پھر اس ابتدائی قدر سے بڑھتی ہوئی تعداد 1، 2، 3 کے لیے فیکٹوریئل ویلیوز بناتی ہیں۔ جیسا کہ اوپر کی تکرار تعریف میں "ٹائم ایرو" کے ساتھ الٹا، جیسا کہ تھا، اسے پیچھے کی طرف پڑھ کر کورکورسییو الگورتھم اس طرح بیان کیا گیا ہے کہ تمام فیکٹوریئلز کا ایک سلسلہ پیدا کرتا ہے۔ اسے ٹھوس طور پر جنریٹر کے طور پر لاگو کیا جا سکتا ہے۔ علامتی طور پر، یہ نوٹ کرتے ہوئے کہ اگلی فیکٹوریل ویلیو کا حساب لگانے کے لیے n اور f (ایک پچھلی فیکٹوریل ویلیو) دونوں کا سراغ لگانے کی ضرورت ہوتی ہے، اس کی نمائندگی اس طرح کی جا سکتی ہے: یا ہاسکل میں، (\(n, f)-> (n + 1, f * (n + 1)) 'تکرار' (0,1) جس کا مطلب ہے، "ہر مرحلے سے شروع کرتے ہوئے، اگلی اقدار کا حساب اس طرح کیا جاتا ہے"۔ یہ ریاضیاتی طور پر مساوی ہے اور تقریبا تکراری تعریف سے ملتا جلتا ہے، لیکن اس بات پر زور دیتا ہے کہ فیکٹوریل ویلیوز تعمیر کی جا رہی ہیں، ابتدائی کیس سے آگے بڑھ رہی ہیں، بجائے اس کے کہ پہلے پیچھے کی طرف جانے کے بعد، بیس کیس پر، کمی کے ساتھ شمار کیا جائے۔ کورکورسیو فنکشن کی براہ راست آؤٹ پٹ میں محض فیکٹوریئل ویلیوز نہیں ہوتی ہیں، بلکہ ہر ویلیو کے لیے ترتیب میں اس کے انڈیکس n کا معاون ڈیٹا بھی شامل ہوتا ہے، تاکہ ضرورت پڑنے پر ان سب میں سے کسی ایک مخصوص نتیجہ کا انتخاب کیا جا سکے۔ ڈنوٹیشنل سیمنٹکس کے ساتھ ایک تعلق ہے، جہاں ریکرسو پروگراموں کی ڈنوٹیشنز کو اس طرح سے بنیادی طور پر بنایا جاتا ہے۔ پائیتھن میں، ایک ریکرسو فیکٹوریئل فنکشن کی تعریف اس طرح کی جا سکتی ہے: ڈیف فیکٹوریئل (n: int)-> int: "" ریکرسو فیکٹوریئل فنکشن "۔ اگر n = = 0:1 اور واپس کریں: n * فیکٹوریئل (n-1) واپس کریں اس کے بعد اسے مثال کے طور پر فیکٹوریئل (5) کہا جا سکتا ہے تاکہ 5! کا حساب لگایا جا سکے۔ ایک متعلقہ کورکورسیو جنریٹر کی تعریف اس طرح کی جا سکتی ہے: ڈیف فیکٹوریئلز (): "کورکورسیو جنریٹر"۔ n، f = 0، 1 جبکہ سچ: پیداوار f n، f = n + 1، f * (n + 1) یہ ترتیب میں فیکٹوریئلز کا ایک لامحدود سلسلہ پیدا کرتا ہے۔ اس کا ایک محدود حصہ اس طرح تیار کیا جا سکتا ہے: ڈیف n _ فیکٹوریئلز (n: int): k، f = 0، 1 جبکہ k <= n: پیداوار f k، f = k + 1، f * (k + 1) اس کے بعد 5 تک فیکٹوریئلز پیدا کرنے کے لیے کہا جا سکتا ہے! کے ذریعے: f کے لیے (5): پرنٹ (f) اگر ہم صرف ایک مخصوص فیکٹوریئل میں دلچسپی رکھتے ہیں، تو صرف آخری قیمت لی جا سکتی ہے، یا ہم پیداوار اور رسائی کو ایک فنکشن میں فیوز کر سکتے ہیں، ڈیف nth _ فیکٹوریئل (n: int): k، f = 0، 1 جبکہ k <n: k، f = k + 1، f * (k + 1) واپسی f جیسا کہ یہاں آسانی سے دیکھا جا سکتا ہے، یہ عملی طور پر برابر ہے (صرف وہاں صرف پیداوار کے لیے واپسی کو تبدیل کر کے) دم کی تکرار کے لیے جمع کرنے والی دلیل کی تکنیک کے لیے، ایک واضح لوپ میں کھول دیا جاتا ہے۔ اس طرح یہ کہا جا سکتا ہے کہ کورکرشن کا تصور جہاں قابل اطلاق ہو، تکراری تعریفیں کے ذریعے تکراری حساب کے عمل کے مجسمے کی وضاحت ہے۔ اسی طرح، فبونیکی ترتیب کو اس طرح پیش کیا جا سکتا ہے: چونکہ فبونیکی ترتیب ترتیب 2 کا تکرار تعلق ہے، اس لیے کورکورسیو تعلق کو دو مسلسل اصطلاحات کا سراغ لگانا چاہیے، جس میں ایک قدم سے آگے بڑھنے کے لیے متعلقہ، اور اگلی اصطلاح کی کمپیوٹنگ کے لیے متعلقہ۔ اس کے بعد اسے مندرجہ ذیل طریقے سے لاگو کیا جا سکتا ہے (متوازی تفویض کا استعمال کرتے ہوئے): ڈیف فائبونیکی _ سیکوینس (): a، b = 0، 1 جبکہ سچ: a a، b = b، a + b حاصل کریں۔ ہاسکل میں، نقشہ fst ((\(a، b)-> (b، a + b) 'تکرار' (0,1)) گہرائی-پہلے نقطہ نظر کے ذریعے ٹری ٹریورسل ٹری ٹریورسل ریکرشن کی ایک بہترین مثال ہے۔ دوہری طور پر، چوڑائی-پہلے ٹریورسل کو کورکرشن کے ذریعے بہت قدرتی طور پر لاگو کیا جا سکتا ہے۔ بار بار، کوئی شخص کسی درخت کو اس کے جڑ نوڈ کو ڈیٹا ڈھانچے میں رکھ کر عبور کر سکتا ہے، پھر اس ڈیٹا ڈھانچے کے ساتھ اس وقت تک دہرا سکتا ہے جب تک کہ یہ خالی نہ ہو، ہر قدم پر اس میں سے پہلا نوڈ ہٹا کر ہٹائے گئے نوڈ کے چائلڈ نوڈس کو اس ڈیٹا ڈھانچے میں واپس رکھ سکتا ہے۔ اگر ڈیٹا ڈھانچہ ایک اسٹیک (ایل آئی ایف او) ہے، تو اس سے ڈیپتھ-فرسٹ ٹریورسل حاصل ہوتا ہے، اور اگر ڈیٹا ڈھانچہ ایک قطار (ایف آئی ایف او) ہے، تو اس سے چوڑائی-فرسٹ ٹریورسل حاصل ہوتا ہے: ریکرشن کا استعمال کرتے ہوئے، ٹری کی ڈیپتھ-فرسٹ ٹریورسل کو صرف اسی طرح لاگو کیا جاتا ہے جیسے روٹ نوڈ کے چائلڈ نوڈس میں سے ہر ایک کو باری باری گزرتا ہے۔ اس طرح دوسرے چائلڈ سبٹری پر اس وقت تک عمل نہیں کیا جاتا جب تک کہ پہلا چائلڈ سبٹری ختم نہ ہو جائے۔ جڑ نوڈ کی قیمت کو الگ سے سنبھالا جاتا ہے، چاہے پہلے بچے کو عبور کرنے سے پہلے (جس کے نتیجے میں پری آرڈر ٹریورسل ہوتا ہے)، پہلے کے ختم ہونے کے بعد اور دوسرے (ترتیب میں) سے پہلے، یا دوسرے بچے کے نوڈ کے ختم ہونے کے بعد (پوسٹ آرڈر)-- یہ فرض کرتے ہوئے کہ درخت بائنری ہے، نمائش کی سادگی کے لیے۔ کال اسٹیک (ریکرسو ٹریورسل فنکشن انوکیشنز کا) اس اسٹیک سے مطابقت رکھتا ہے جسے اوپر بیان کردہ واضح ایل آئی ایف او ڈھانچے میں ہیرا پھیری کے ساتھ دہرایا جائے گا۔ علامتی طور پر، "ریکرشن" کے یہاں دو معنی ہیں۔ سب سے پہلے، ٹری ٹریورسل افعال کی تکراری دعائیں۔ مزید خاص طور پر، ہمیں اس بات کا مقابلہ کرنے کی ضرورت ہے کہ اقدار کی نتیجہ خیز فہرست یہاں کیسے بنائی گئی ہے۔ بار بار، نیچے سے اوپر آؤٹ پٹ تخلیق کے نتیجے میں دائیں سے بائیں ٹری ٹریورسل ہوگا۔ اسے اصل میں مطلوبہ بائیں سے دائیں ترتیب میں انجام دینے کے لیے ترتیب کو کچھ غیر معمولی ذرائع سے نافذ کرنے کی ضرورت ہوگی، یا یہ خود بخود حاصل ہو جائے گا اگر آؤٹ پٹ کو اوپر سے نیچے کے انداز میں بنایا جائے، یعنی۔ بنیادی طور پر۔ اوپری نیچے کی ترتیب میں اپنی پیداوار پیدا کرنے والا چوڑائی سے پہلا ٹریورسل، بنیادی طور پر، جڑ نوڈ سے شروع کرکے، اس کی قیمت کو آؤٹ پٹ کرکے، پھر سبٹریز کو چوڑائی سے پہلے عبور کرکے بھی نافذ کیا جاسکتا ہے-یعنی، سبٹریز کی پوری فہرست کو اگلے مرحلے تک منتقل کرنا (ایک بھی سبٹری نہیں، جیسا کہ ریکرسو اپروچ میں ہے)-اگلے مرحلے میں ان کے تمام جڑ نوڈس کی اقدار کو آؤٹ پٹ کرنا، پھر ان کے چائلڈ سبٹریز وغیرہ کو منتقل کرنا۔ اس صورت میں جنریٹر فنکشن، درحقیقت آؤٹ پٹ سیکوینس خود، قطار کے طور پر کام کرتا ہے۔ جیسا کہ اوپر کی فیکٹوریل مثال میں، جہاں انڈیکس کی معاون معلومات (جس مرحلے میں ایک تھا، n) کو آگے بڑھایا گیا تھا، اس صورت میں n! کی اصل آؤٹ پٹ کے علاوہ، باقی ذیلی درختوں کی معاون معلومات کو آگے بڑھایا جاتا ہے، اصل آؤٹ پٹ کے علاوہ۔ علامتی طور پر، اس کا مطلب یہ ہے کہ ہر مرحلے پر، اس سطح کے نوڈس میں اقدار کی فہرست کو آؤٹ پٹ کرتا ہے، پھر اگلے درجے کے نوڈس پر جاتا ہے۔ اس ترتیب سے صرف نوڈ ویلیوز پیدا کرنے کے لیے صرف معاون چائلڈ ٹری ڈیٹا کو ضائع کرنے کی ضرورت ہوتی ہے، پھر فہرستوں کی فہرست کو چپٹا کرنا (اقدار کو ابتدائی طور پر سطح (گہرائی) کے لحاظ سے گروپ کیا جاتا ہے ؛ چپٹا کرنا (غیر گروپ کرنا) ایک فلیٹ لکیری فہرست فراہم کرتا ہے)۔ یہ توسیعی طور پر اوپر کی تفصیلات کے مساوی ہے۔ ہاسکل میں، کونکیٹ میپ ایف ایس ٹی (((v, ts)-> (rootValue ts, चाइल्ड ٹریز ts)) 'آئیٹریٹ' ([]، [فل ٹری]) خاص طور پر، ایک لامحدود درخت کو دیکھتے ہوئے، کورکورسیو بریڈتھ-فرسٹ ٹریورسل تمام نوڈس کو عبور کرے گا، بالکل ایک محدود درخت کی طرح، جبکہ ریکورسیو ڈیپتھ-فرسٹ ٹریورسل ایک شاخ سے نیچے جائے گا اور تمام نوڈس کو عبور نہیں کرے گا، اور درحقیقت اگر پوسٹ آرڈر کو عبور کرتا ہے، جیسا کہ اس مثال (یا ترتیب میں) میں ہے، تو یہ بالکل بھی نوڈس کا دورہ نہیں کرے گا، کیونکہ یہ کبھی کسی پتی تک نہیں پہنچتا ہے۔ یہ لامحدود ڈیٹا ڈھانچوں سے نمٹنے کے لیے ریکرشن کے بجائے کورکرشن کی افادیت کو ظاہر کرتا ہے۔ ایک انتباہ اب بھی ان درختوں کے لیے باقی ہے جن میں لامحدود شاخوں کا عنصر ہوتا ہے، جن کو جگہ کو بہتر طریقے سے تلاش کرنے کے لیے زیادہ توجہ دینے والے انٹرلیسنگ کی ضرورت ہوتی ہے۔ ڈوویٹیلنگ دیکھیں۔ ازگر میں، اسے مندرجہ ذیل طریقے سے لاگو کیا جا سکتا ہے۔ عام پوسٹ آرڈر ڈیپتھ-فرسٹ ٹریورسل کی تعریف اس طرح کی جا سکتی ہے: ڈیف ڈی ایف (نوڈ): "پوسٹ آرڈر ڈیپتھ-فرسٹ ٹریورسل"۔ اگر نوڈ کوئی نہیں ہے: df (node.left) df (node.right) پرنٹ (node.value) اس کے بعد پوسٹ آرڈر ڈیپتھ-فرسٹ آرڈر میں ٹری کے نوڈس کی ویلیوز کو پرنٹ کرنے کے لیے df (t) کے ذریعے کال کیا جا سکتا ہے۔ چوڑائی والے پہلے کورکورسیو جنریٹر کی تعریف اس طرح کی جا سکتی ہے: ڈیف بی ایف (ٹری): "چوڑائی والے پہلے کورکورسیو جنریٹر"۔ ٹری _ لسٹ = [tree] جبکہ ٹری _ لسٹ: نیو _ ٹری _ لسٹ = [] ٹری _ لسٹ میں ٹری کے لیے: اگر ٹری کوئی نہیں ہے: ییلڈ tree.value new_tree_list.append (tree.left) new_tree_list.append (tree.right) ٹری _ لسٹ = نیو _ ٹری _ لسٹ اس کے بعد ٹری کے نوڈس کی اقدار کو چوڑائی-پہلی ترتیب میں پرنٹ کرنے کے لیے کہا جا سکتا ہے: bf (t) میں i کے لیے: پرنٹ (i) تعریف ابتدائی ڈیٹا کی اقسام کو کسی قسم کی مساوات کے سب سے کم فکس پوائنٹ (آئسومورفزم تک) کے طور پر بیان کیا جا سکتا ہے۔ اس کے بعد آئسومورفزم کو ابتدائی الجبرا کے ذریعے دیا جاتا ہے۔ دو بار، حتمی (یا ٹرمینل) ڈیٹا کی اقسام کو کسی قسم کی مساوات کا سب سے بڑا فکس پوائنٹ ہونے کے طور پر بیان کیا جا سکتا ہے۔ اس کے بعد آئسومورفزم کو حتمی کوئلہ الجبرا کے ذریعے دیا جاتا ہے۔ اگر ڈسکورس کا ڈومین سیٹوں اور کل افعال کا زمرہ ہے، تو حتمی ڈیٹا کی اقسام میں لامحدود، غیر مستحکم اقدار ہو سکتی ہیں، جبکہ ابتدائی اقسام میں نہیں۔ دوسری طرف، اگر ڈسکورس کا ڈومین مکمل جزوی ترتیبات اور مسلسل افعال کا زمرہ ہے، جو تقریبا ہاسکل پروگرامنگ زبان سے مطابقت رکھتا ہے، تو حتمی اقسام ابتدائی اقسام کے ساتھ موافق ہوتی ہیں، اور متعلقہ حتمی کوئلہ الجبرا اور ابتدائی الجبرا ایک آئسومورفزم تشکیل دیتے ہیں۔ اس کے بعد کورکرسن تکراری طور پر افعال کی وضاحت کرنے کی ایک تکنیک ہے جس کی رینج (کوڈومین) ایک حتمی ڈیٹا ٹائپ ہے، جس طرح سے عام تکراری تکراری طور پر افعال کی وضاحت کرتی ہے جس کا ڈومین ایک ابتدائی ڈیٹا ٹائپ ہے۔ نیچے دی گئی بحث ہاسکل میں کئی مثالیں فراہم کرتی ہے جو کورکرشن میں فرق کرتی ہیں۔ موٹے طور پر، اگر کوئی ان تعریفوں کو سیٹوں کے زمرے میں پیش کرتا ہے، تو وہ پھر بھی بنیادی ہوں گے۔ یہ غیر رسمی استعمال ہاسکل کے بارے میں موجودہ نصابی کتابوں کے مطابق ہے۔ اس مضمون میں استعمال ہونے والی مثالیں کورکرن کی وضاحت کرنے اور اس کی وضاحت کرنے کی کوششوں سے پہلے کی ہیں۔ بحث کوڈاٹا پر ابتدائی کورکرن کا قاعدہ اعداد و شمار پر ابتدائی تکرار کے لیے اس سے دوگنا ہے۔ اس کے کنسٹرکٹرز پر پیٹرن میچنگ کے ذریعے دلیل پر اترنے کے بجائے (جنہیں پہلے کہیں بلایا گیا تھا، لہذا ہم ایک تیار شدہ ڈیٹم وصول کرتے ہیں اور اس کے جزو ذیلی حصوں پر پہنچتے ہیں، یعنی۔ "فیلڈز")، ہم اس کے "تباہ کن" (یا "مبصرین"، جنہیں بعد میں کہیں بلایا جائے گا-کو بھر کر نتیجہ پر چڑھتے ہیں-لہذا ہم اصل میں ایک کنسٹرکٹر کو بلا رہے ہیں، جس سے نتیجہ کا ایک اور ٹکڑا بعد میں مشاہدہ کیا جائے گا)۔ اس طرح کورکرشن (ممکنہ طور پر لامحدود) کوڈاٹا بناتا ہے، جبکہ عام ریکرشن تجزیہ (لازمی طور پر محدود) ڈیٹا۔ عام تکرار کوڈاٹا پر لاگو نہیں ہو سکتا ہے کیونکہ یہ ختم نہیں ہو سکتا ہے۔ اس کے برعکس، اگر نتیجہ کی قسم ڈیٹا ہے تو کورکرشن سختی سے ضروری نہیں ہے، کیونکہ ڈیٹا کو محدود ہونا چاہیے۔ "کوق میں اسٹریمز کے ساتھ پروگرامنگ: ایک کیس اسٹڈی: ایراٹوستھینز کی چھلنی" میں ہم پاتے ہیں کہ ایچ ڈی (کونک اے ایس) = اے ٹی ایل (کونک اے ایس) = ایس (چھلنی پی ایس) = اگر ڈیو پی (ایچ ڈی ایس) ہے تو چھلنی پی (ٹی ایل ایس) اور کونک (ایچ ڈی ایس) (چھلنی پی (ٹی ایل ایس)) ایچ ڈی (پرائم ایس) = (ایچ ڈی ایس) ٹی ایل (پرائم ایس) = پرائمز (چھلنی (ایچ ڈی ایس) (ٹی ایل ایس) جہاں پرائمز "اسٹریم (اینیو 2) پر پرائم آپریشن لاگو کرکے حاصل کیے جاتے ہیں۔ مندرجہ بالا نوٹیشن کے بعد، پرائمز کی ترتیب (جس میں ایک تھرو وے 0 پہلے سے لگا ہوا ہے) اور نمبروں کے سلسلے کو بتدریج چھان لیا جا رہا ہے، اسے ہاسکل میں یا اس کے طور پر پیش کیا جا سکتا ہے، (\(p, s @(h: t)-> (h, sieve ht) 'इटریٹ' (0, [2.]) مصنفین اس بات پر تبادلہ خیال کرتے ہیں کہ کس طرح چھلنی کی تعریف ہمیشہ نتیجہ خیز ہونے کی ضمانت نہیں دی جاتی ہے، اور جیسے کہ پھنس سکتی ہے۔ اگر ابتدائی ندی کے طور پر [5,10.] کے ساتھ کال کیا جائے۔ یہاں ہاسکل میں ایک اور مثال ہے۔ مندرجہ ذیل تعریف لکیری وقت میں فبونیکی نمبروں کی فہرست تیار کرتی ہے: ریشے = 0:1: زپ کے ساتھ (+) ریشے (دم کے ریشے) یہ لامحدود فہرست سست تشخیص پر منحصر ہے ؛ عناصر کا حساب ضرورت کے مطابق کیا جاتا ہے، اور میموری میں صرف محدود سابقہ کی واضح طور پر نمائندگی کی جاتی ہے۔ یہ خصوصیت کوڈیٹا کے کچھ حصوں پر الگورتھم کو ختم کرنے کی اجازت دیتی ہے۔ اس طرح کی تکنیک ہاسکل پروگرامنگ کا ایک اہم حصہ ہیں۔ یہ پائیتھن میں بھی کیا جا سکتا ہے: آئیٹر ٹولز سے امپورٹ ٹی، چین، آئیلیس، آئی میپ ڈیف ایڈ (x, y): ریٹرن x + y ڈیف فائیبونیکی (): ڈیف ڈیفرڈ آؤٹ پٹ (): آؤٹ پٹ میں i کے لیے: ییلڈ i کا نتیجہ، c1، c2 = tee (ڈیفرڈ آؤٹ پٹ ()، 3) پیئرڈ = آئی میپ (ایڈ، c1، آئیلیس (c2,1، کوئی نہیں)) آؤٹ پٹ = چین ([0,1]، پیئرڈ) آئلیس میں i کے لیے ریٹرن نتیجہ (فائیبونیکی ()، 20): پرنٹ (i) زپ کی تعریف جس میں ان لائن کیا جا سکتا ہے، فائبر = 0 عام تکرار خود حوالہ افعال کا استعمال کرتا ہے، لیکن خود حوالہ ڈیٹا کو ایڈجسٹ نہیں کرتا ہے۔ تاہم، یہ فبونیکی مثال کے لیے ضروری نہیں ہے۔ اسے مندرجہ ذیل طریقے سے دوبارہ لکھا جا سکتا ہے: fibs = fibgen (0,1) fibgen (x, y) = x: fibgen (y, x + y) یہ نتیجہ کی تعمیر کے لیے صرف خود حوالہ فنکشن کا استعمال کرتا ہے۔ اگر اسے سخت لسٹ کنسٹرکٹر کے ساتھ استعمال کیا جاتا تو یہ رن وے ریکرشن کی ایک مثال ہوتی، لیکن غیر سخت لسٹ کنسٹرکٹر کے ساتھ یہ محافظ ریکرشن آہستہ آہستہ ایک غیر معینہ مدت تک متعین فہرست تیار کرتا ہے۔ کورکرسن کو ایک لامحدود شے پیدا کرنے کی ضرورت نہیں ہے۔ ایک کورکرسو قطار اس رجحان کی ایک خاص طور پر اچھی مثال ہے۔ مندرجہ ذیل تعریف لکیری وقت میں اوپر سے نیچے کے انداز میں بائنری ٹری کی چوڑائی پیدا کرتی ہے (پہلے سے ہی اوپر بیان کردہ چپٹی کو شامل کرتے ہوئے): ڈیٹا ٹری a b = لیف a | برانچ b (ٹری a b) (ٹری a b) bftrav:: ٹری a b-> [ٹری a b] bftrav ٹری = ٹری: ts جہاں ts = جین 1 (ٹری: ts) جین 0 p = [] جین لین (لیف p) = جین (لین-1) p جین لین (برانچ r: p) = l: r: جین (لین + 1) p---------------------------------------------------------------- یہ فہرست ان پٹ قطار اور نتیجہ دونوں کے طور پر دوہرے مقصد کی تکمیل کرتی ہے (جین لین پی فہرست کے ساتھ اپنے ان پٹ بیک پوائنٹر، پی، سے پہلے اپنی آؤٹ پٹ لین نوچز تیار کرتا ہے)۔ یہ محدود ہے اگر اور صرف اس صورت میں جب ابتدائی درخت محدود ہو۔ ختم ہونے کو یقینی بنانے کے لیے قطار کی لمبائی کو واضح طور پر ٹریک کیا جانا چاہیے ؛ اگر یہ تعریف صرف لامحدود درختوں پر لاگو ہوتی ہے تو اسے محفوظ طریقے سے ختم کیا جا سکتا ہے۔ یہ ہاسکل کوڈ خود حوالہ جاتی ڈیٹا ڈھانچے کا استعمال کرتا ہے، لیکن بنیادی طور پر سست تشخیص پر منحصر نہیں ہے۔ اس کا سیدھا سیدھا ترجمہ کیا جا سکتا ہے۔ پرولاگ جو کوئی سست زبان نہ ہو۔ جو چیز ضروری ہے وہ اوپر سے نیچے کے انداز میں فہرست (قطار کے طور پر استعمال) بنانے کی صلاحیت ہے۔ اس کے لیے، پرولاگ میں ٹیل ریکرشن ماڈیولو کے نقصانات ہیں (یعنی۔ ختم فہرستوں کو کھولیں)۔ جو اسکیم، سی وغیرہ میں بھی قابل تقلید ہے۔ متغیر دم سینٹینل پوائنٹر کے ساتھ منسلک فہرستوں کا استعمال کرتے ہوئے: bftrav (درخت، [Tree|TS]):-bfgen (1، [Tree|TS]، TS)۔ bfgen (0، _، []):-! قطار میں% 0 اندراجات-- bfgen (N، [leef (_) |P]، TS) کی فہرست کو روکیں اور بند کریں:-N2 N-1، bfgen (N2، P، TS) ہے۔ bfgen (N، [شاخ (_، L، R) |P]، [L، R|TS]):-N2 N + 1، bfgen (N2، P، TS) ہے۔ %%------------ لکھیں-آگے-- ایک اور خاص مثال چوڑائی-پہلی لیبلنگ کے مسئلے کا حل فراہم کرتی ہے۔ فنکشن لیبل بائنری ٹری میں ہر نوڈ کو چوڑائی کے پہلے انداز میں دیکھتا ہے، ہر لیبل کو ایک عدد کے ساتھ تبدیل کرتا ہے، اس کے بعد کا ہر عدد آخری سے 1 سے بڑا ہوتا ہے۔ یہ حل ایک خود حوالہ ڈیٹا ڈھانچے کو استعمال کرتا ہے، اور بائنری ٹری محدود یا لامحدود ہو سکتا ہے۔ لیبل:: ٹری اے بی-> ٹری انٹ انٹ لیبل ٹی = ٹی این جہاں (ٹی این، این ایس) = گو ٹی (1: این ایس) جائیں:: ٹری اے بی-> [انٹ]-> (ٹری انٹ انٹ، [انٹ]) جائیں (لیف _) (آئی: اے) = (لیف آئی، آئی + 1: اے) جائیں (برانچ _ ایل آر) (آئی: اے) = (برانچ آئی ایل این آر این، آئی + 1: سی) جہاں (ایل این، بی) = ایل اے (آر این، سی) = جی او آر بی یا پرولاگ میں، موازنہ کے لیے، لیبل (ٹری، ٹی این):-لیبل (ٹری، [1|Ns]، ٹی این، این ایس لیبل (پتی (_)، [I|A]، پتی (I)، [I + 1|A])۔ لیبل (برانچ (_، L، R)، [I|A]، برانچ (I، Ln، Rn)، [I + 1|C]):-لیبل (L، A، Ln، B)، لیبل (R، B، Rn، C)۔ ایک اپومورفزم (جیسے انامورفزم، جیسے کہ انفلڈ) کورکرن کی ایک شکل ہے جس طرح ایک پیرامورفزم (جیسے کیٹامورفزم، جیسے فولڈ) ریکرشن کی ایک شکل ہے۔ کوک پروف اسسٹنٹ کوفیکس پوائنٹ کمانڈ کا استعمال کرتے ہوئے کورکرشن اور کوئنڈکشن کی حمایت کرتا ہے۔ ہسٹری کورکرن، جسے سرکلر پروگرامنگ کہا جاتا ہے، کم از کم اس کی تاریخ ہے، جو جان ہیوز اور فلپ ویڈلر کو کریڈٹ دیتا ہے۔ مزید عمومی شکلیں 1960 میں تیار کی گئیں۔ اصل محرکات میں زیادہ موثر الگورتھم تیار کرنا (کچھ معاملات میں ایک سے زیادہ پاس کی ضرورت کے بجائے ڈیٹا کو پاس کرنے کی اجازت دینا) اور کلاسیکی ڈیٹا ڈھانچے، جیسے کہ دوگنا منسلک فہرستیں اور قطاریں، کو فعال زبانوں میں نافذ کرنا شامل تھا۔ یہ بھی دیکھیں کہ بسیولیشن کوئنڈکشن ریکرشن انامورفزم نوٹس حوالہ جات نظریاتی کمپیوٹر سائنس خود حوالہ مضامین مثال کے طور پر ہاسکل کوڈ مضامین مثال کے طور پر ازگر (پروگرامنگ زبان) کوڈ فنکشنل پروگرامنگ زمرہ تھیوری ریکرشن