স্কালা রিকার্শন এবং টেল রিকার্শন

রিকার্শন (Recursion) হলো একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেরই একটি সংস্করণকে কল করে। স্কালায় রিকার্শন খুবই শক্তিশালী এবং সাধারণভাবে ব্যবহার হয়। তবে, রিকার্শন ব্যবহারের সময় টেল রিকার্শন (Tail Recursion) একটি গুরুত্বপূর্ণ ধারণা, যা পারফরম্যান্স এবং মেমরি ব্যবহারে উন্নতি এনে দেয়।

১. রিকার্শন (Recursion)

রিকার্শন হল একটি কৌশল যেখানে একটি ফাংশন নিজেকেই কল করে, যতক্ষণ না একটি বেস কেস (base case) পূর্ণ হয়। বেস কেস হলো সেই শর্ত যা রিকার্শন বন্ধ করবে এবং ফলাফল প্রদান করবে। এটি সাধারণভাবে পুনরাবৃত্তির মাধ্যমে সমস্যা সমাধান করতে ব্যবহৃত হয়।

সাধারণ রিকার্শন উদাহরণ (ফ্যাক্টোরিয়াল):

ফ্যাক্টোরিয়াল একটি ক্লাসিক্যাল রিকার্শন উদাহরণ, যেখানে n! = n * (n-1) * (n-2) * ... * 1।

object Factorial {
  def fact(n: Int): Int = {
    if (n == 0) 1      // বেস কেস
    else n * fact(n - 1)  // রিকার্শন
  }

  def main(args: Array[String]): Unit = {
    println(fact(5))  // Output: 120
  }
}

এখানে:

• বেস কেস: যখন n == 0 তখন ১ রিটার্ন করবে (কারণ 0! = 1)।
• রিকার্শন: n * fact(n - 1)। ফাংশনটি নিজেকে কল করছে যতক্ষণ না এটি বেস কেসে পৌঁছায়।

২. টেল রিকার্শন (Tail Recursion)

টেল রিকার্শন হল একটি বিশেষ ধরনের রিকার্শন যেখানে ফাংশনটির রিকার্শন কল শেষ কল (last call) হিসেবে ঘটে। এটি ফাংশনের স্ট্যাক ফ্রেমে অতিরিক্ত মেমরি সংরক্ষণ না করে পুনরাবৃত্তি চালাতে সাহায্য করে। স্কালার মতো ভাষা গুলি টেল রিকার্শন অপটিমাইজ করে টেল রিকার্শন অপ্টিমাইজেশন (TRO) ব্যবহার করে, যার মাধ্যমে মেমরি সাশ্রয়ী হয় এবং স্ট্যাকওভারফ্লো রোধ করা যায়।

টেল রিকার্শনের সুবিধা হল যে, এটি কম মেমরি ব্যবহার করে এবং কোনো অতিরিক্ত স্ট্যাক ফ্রেম তৈরি না করেই পরবর্তী কল করতে পারে।

টেল রিকার্শন উদাহরণ (ফ্যাক্টোরিয়াল):

object TailRecursionFactorial {
  def factTail(n: Int, accumulator: Int = 1): Int = {
    if (n == 0) accumulator      // বেস কেস
    else factTail(n - 1, n * accumulator)  // টেল রিকার্শন
  }

  def main(args: Array[String]): Unit = {
    println(factTail(5))  // Output: 120
  }
}

এখানে:

• বেস কেস: যখন n == 0, তখন accumulator রিটার্ন হবে, যা পরবর্তী মানের জন্য ব্যবহৃত হয়।
• টেল রিকার্শন: factTail(n - 1, n * accumulator)। এখানে আমরা পরবর্তী কলের জন্য accumulator ব্যবহার করে রিকার্শন কল করি, যা আগের মানের উপর ভিত্তি করে আপডেট হবে।

এই ফাংশনটি টেল রিকার্শন অপটিমাইজেশন দ্বারা মেমরি সাশ্রয়ী হয় এবং স্ট্যাক ফ্রেম কম ব্যবহার করে, যার ফলে এটি বড় ইনপুটের জন্য আরও উপযোগী।

৩. রিকার্শন বনাম টেল রিকার্শন: পার্থক্য

৪. টেল রিকার্শন অপটিমাইজেশন

টেল রিকার্শন সাধারণভাবে স্ট্যাক ওভারফ্লো প্রতিরোধ করতে সাহায্য করে, কারণ এটি সাধারণ রিকার্শনের তুলনায় কম স্ট্যাক ফ্রেম ব্যবহার করে। স্কালা ভাষা টেল রিকার্শন অপটিমাইজেশন (TRO) সাপোর্ট করে, যাতে রিকার্শন কলগুলিকে "loop" হিসেবে পরিবর্তন করা হয়, এটি কম মেমরি ব্যবহার করে এবং স্ট্যাকের উপর চাপ কমায়।

৫. টেল রিকার্শন উদাহরণ (ফিবোনাচ্চি)

ফিবোনাচ্চি সিকোয়েন্সের টেল রিকার্শন উদাহরণ:

object FibonacciTailRec {
  def fibTail(n: Int, prev: Int = 0, curr: Int = 1): Int = {
    if (n == 0) prev
    else fibTail(n - 1, curr, prev + curr)
  }

  def main(args: Array[String]): Unit = {
    println(fibTail(6))  // Output: 8
  }
}

এখানে:

• fibTail(n - 1, curr, prev + curr) কলটি টেল রিকার্শন কারণ এখানে সমস্ত হিসাব করা হচ্ছে পরবর্তী কলের মধ্যে (শেষ কল হিসেবে)।
• ফিবোনাচ্চি সিকোয়েন্সের জন্য আমাদের পূর্ববর্তী দুটি মান (prev এবং curr) আপডেট করতে হচ্ছে প্রতিটি রিকার্শন কলের মাধ্যমে।

সারাংশ

• রিকার্শন একটি শক্তিশালী কৌশল যা সমস্যা সমাধানে পুনরাবৃত্তি ব্যবহার করে, তবে এটি অনেক মেমরি এবং স্ট্যাক ব্যবহার করতে পারে।
• টেল রিকার্শন হল একটি অপটিমাইজড রিকার্শন কৌশল যেখানে ফাংশনটির রিকার্শন কল শেষ কল হিসেবে ঘটে, ফলে এটি মেমরি এবং পারফরম্যান্স অপটিমাইজ করে।

টেল রিকার্শন ব্যবহার করলে আপনার কোড বেশি দক্ষ হয়, বিশেষত বড় ইনপুটের ক্ষেত্রে।