۸ - ۱بازگشتی یا recursion
توابعی که با خودارجاعی و برمبنای خودشون تعریف میشن، توابعِ بازگشتی نام دارن. این به این معناست که تابع خودش رو دائماً صدا میزنه و رفتارش رو تکرار می‌کنه، تا یه شرطی برقرار بشه و جواب بده. این یکی از مباحث مهم در هسکل و ریاضیات‌ه، چراکه بیان محاسبات بی‌حد یا افزایشی بدون تکرارِ کُد از این طریق ممکنه. در توابع بازگشتی، داده‌ها تعیین‌کننده‌ی پایانِ محاسبات میشن.
بازگشتی بودن از مشخصه‌های طبیعیِ خیلی از سیستم‌های منطقی و ریاضیاتی‌ه، که زبان هم شامل اونها میشه. همین که هیچ محدودیتی در تعداد جملات صحیح و قابل بیان در یک زبان وجود نداره، به خاطر بازگشتی بودنه. یک جلمه می‌تونه یه جمله‌ی دیگه در خودش داشته باشه. با یه توصیف اجمالی میشه گفت ساختار جملات شامل یه اسم، فعل، و یه جمله‌ی اختیاری میشه. امکان وجودِ جمله در جمله (نامحدود بودن جملاتِ تودرتو) یعنی بازگشتی بودن، و همین باعثِ محدود نبودن قابلیتِ بیان در یک زبان میشه. نوشتار بازگشتی راهی برای نوشتن کُدی هست که برای رسیدن به جواب باید تعداد مراحل نامشخصی رو طی کنه.
در جبر لاندا، به دلیل بی‌نام بودن بیانیه‌ها، به نظر نمیرسه راهی برای نگارش بازگشتی وجود داشته باشه. چطور میشه چیزی رو بدون اسم صدا زد؟ با این حال، توانایی نوشتن توابع بازگشتی از واجبات برای کامل بودن تورینگ ِه. ما از یه ترکیب‌گر – معروف به ترکیب‌گرِ وای یا ترکیب‌گر نقطه‌ثابت – استفاده می‌کنیم تا در جبر لاندا توابعِ بازگشتی بنویسیم. قابلیتِ بازگشتی بودن در هسکل هم بر پایه‌ی همین ترکیب‌گرِ وای هست.
درک خوب از رفتار توابع بازگشتی بسیار حائز اهمیت‌ه. در فصل‌های آینده می‌بینیم که اکثراً لازم نمیشه خودمون توابع بازگشتی بنویسیم، چراکه خیلی از توابع سطح بالا ِ استاندارد، خوداتکایی دارن. ولی بدون پایه‌ی خوب از رفتار بازگشتی و اصول‌ش، کار با اون HOFها* هم دشوار میشه. در این فصل:
بازگشتی بودن و طریقه‌ی محاسبه در توابع بازگشتی رو بررسی می‌کنیم؛
مرحله به مرحله، نوشتنِ توابعِ بازگشتی رو پیش میریم؛
یه کم با تهی خوش می‌گذرونیم.
م. مخفف برای higher-order functions یا توابعِ سطح بالا.