रिकर्शन में

रिकर्शन के बारे में

किसी चीज़ को उसी के आधार पर परिभाषित करने की क्षमता को रिकर्शन कहते हैं। 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