بازگشت در

درباره‌ی بازگشت

وقتی چیزی بر اساس خودش تعریف می‌شود، به آن «بازگشت» می‌گویند. در F#، بازگشت بیشتر از همه در توابع بازگشتی دیده می‌شود؛ توابعی که خودشان را فراخوانی می‌کنند.

یک تابع بازگشتی باید حداقل یک حالت پایه و حداقل یک حالت بازگشتی داشته باشد. حالت پایه مقداری را برمی‌گرداند بدون این که تابع را دوباره فراخوانی کند. حالت بازگشتی تابع را دوباره فراخوانی می‌کند و ورودی را طوری تغییر می‌دهد که در نقطه‌ای با حالت پایه مطابقت پیدا کند.

توابع بازگشتی مانند توابع معمولی تعریف می‌شوند، اما با اصلاح‌کننده‌ی rec. بدون این اصلاح‌کننده، یک تابع نمی‌تواند خودش را فراخوانی کند و هر تلاشی برای این کار به خطای کامپایل می‌انجامد. بنابراین باید بازگشت را به‌صراحت انتخاب کرد.

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

لیست‌ها اغلب به‌صورت بازگشتی پردازش می‌شوند. برای مثال، در ادامه می‌بینید چگونه از بازگشت برای محاسبه‌ی طول یک لیست استفاده کنید:

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

بسیاری از توابع توکار به‌صورت بازگشتی تعریف شده‌اند.

یکی از مشکلات احتمالی توابع بازگشتی این است که هر فراخوانی (بازگشتی) تابع به تخصیص‌هایی روی پشته می‌انجامد و باعث رشد آن می‌شود. چون پشته حافظه‌ی محدودی دارد، توابعی که فراخوانی‌های بازگشتی زیادی انجام می‌دهند ممکن است باعث پرتاب یک StackOverflowException شوند. این که چند فراخوانی بازگشتی این رفتار را فعال می‌کند به عوامل متعددی بستگی دارد، مانند حافظه‌ی در دسترس روی پشته و این که هر فراخوانی تابع چه مقدار داده روی پشته اشغال می‌کند.

بهترین راه برای جلوگیری از سرریز شدن پشته توسط توابع بازگشتی این است که آن‌ها را به‌صورت توابع بازگشتی دنباله‌دار بنویسید. وقتی تابعی بازگشتی دنباله‌دار باشد، کامپایلر می‌تواند خروجی آن را طوری بهینه کند که برای هر فراخوانی بازگشتی، هیچ تخصیص اضافی روی پشته صورت نگیرد. تنها قاعده‌ی توابع بازگشتی دنباله‌دار این است که نتیجه‌ی فراخوانی بازگشتی باید مستقیماً از تابع برگردانده شود و هیچ کد اضافی نباید نتیجه‌ی فراخوانی بازگشتی را پردازش کند. رایج‌ترین راه برای این کار، ساختن یک تابع کمکی است که یک آرگومان انباشتگر اضافی می‌گیرد؛ این آرگومان برای هر فراخوانی بازگشتی به‌روزرسانی می‌شود و وقتی بازگشت پایان می‌یابد برگردانده می‌شود. این صفحه با جزئیات فراوان توضیح می‌دهد که کامپایلر چگونه توابع بازگشتی دنباله‌دار را پردازش می‌کند.

در ادامه یک نسخه‌ی بازگشتی دنباله‌دار از تابع طول لیست آمده است:

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

تعریف تابع کمکی بازگشتی به‌صورت یک تابع تودرتو بسیار رایج است؛ این کار ماهیت بازگشتی تابع را از فراخوان‌کننده پنهان می‌کند:

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F# از انواع بازگشتی از طریق انواع اتحاد متمایز پشتیبانی می‌کند. یک نوع اتحاد متمایز بازگشتی، یک یا چند حالت دارد که در داده‌ی خودشان به خودِ آن نوع اتحاد متمایز ارجاع می‌دهند. مانند توابع بازگشتی، انواع بازگشتی هم باید یک حالت پایه داشته باشند. برخلاف توابع بازگشتی، انواع بازگشتی از کلیدواژه‌ی rec استفاده نمی‌کنند.

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

در ادامه یک تابع (نه بازگشتی دنباله‌دار) برای کار با نوع بازگشتی بالا می‌بینید:

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1