রিকার্সন মধ্যে

রিকার্সন সম্পর্কে

কোনো কিছুকে তার নিজের মাধ্যমেই সংজ্ঞায়িত করার ক্ষমতাকে রিকার্সন বলা হয়। 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