রিকার্সন (Recursion) একটি শক্তিশালী ধারণা যা প্রোগ্রামিং ভাষায় এমন একটি পদ্ধতি যা একটি ফাংশন বা নিয়ম নিজেকে কল (call) করে। প্রোলগে রিকার্সিভ নিয়ম (Recursive Rules) ব্যবহার করে আমরা এমন সম্পর্ক বা কার্যকলাপ তৈরি করতে পারি যা নিজের উপর নির্ভরশীল হয়। প্রোলগের ক্ষেত্রে, রিকার্সিভ নিয়মগুলোর মাধ্যমে সমস্যার সমাধান করার জন্য আমরা একটি শর্তিত সীমা বা বেস কেস (Base Case) নির্ধারণ করি, এবং তার পরে ওই শর্ত পূর্ণ হলে পুনরায় কল করা হয়।
রিকার্সিভ নিয়ম (Recursive Rules) এর ধারণা:
প্রোলগে রিকার্সিভ নিয়ম এমন এক ধরনের নিয়ম যা নিজেই নিজেকে কল করে। এটি সাধারণত তখন ব্যবহার করা হয় যখন সমাধানটি একটি ছোট সমস্যা থেকে তৈরি করা যেতে পারে, যা মূল সমস্যার একটি অংশ। রিকার্সিভ নিয়মগুলির মধ্যে দুটি প্রধান উপাদান থাকে:
- বেস কেস (Base Case): এটি শর্ত যা শেষের দিকে পৌঁছানোর জন্য নির্ধারিত হয় এবং যেখানে রিকার্সন থেমে যায়।
- রিকার্সিভ কেস (Recursive Case): এটি একটি শর্ত যা পুনরায় নিজেকে কল করে, যাতে সমাধান ধীরে ধীরে ছোট ছোট অংশে ভাগ হয়ে যায়।
রিকার্সিভ নিয়মের উদাহরণ:
ধরা যাক, আমাদের একটি সমস্যা আছে যা ফ্যাক্টোরিয়াল (Factorial) গণনা করতে হবে। ফ্যাক্টোরিয়াল হল একটি পজিটিভ পূর্ণসংখ্যা n এর সমস্ত সংখ্যা গুণফল, যা n! দিয়ে প্রকাশ করা হয়। উদাহরণস্বরূপ:
5! = 5 * 4 * 3 * 2 * 1
আমরা যদি রিকার্সিভ নিয়ম ব্যবহার করি, তবে n! = n * (n-1)! রূপে একটি নিয়ম তৈরি করা যায়।
১. ফ্যাক্টোরিয়াল এর রিকার্সিভ নিয়ম:
ফ্যাক্টোরিয়াল(0, 1). % বেস কেস: 0! = 1
ফ্যাক্টোরিয়াল(N, Result) :- N > 0, N1 is N - 1, ফ্যাক্টোরিয়াল(N1, R1), Result is N * R1.এখানে:
- প্রথম ফ্যাক্টটি বেস কেস:
0! = 1 - দ্বিতীয়টি রিকার্সিভ কেস:
N! = N * (N-1)!
এই নিয়মে, ফ্যাক্টোরিয়াল(N, Result) যদি N > 0 হয়, তাহলে এটি পুনরায় ফ্যাক্টোরিয়াল(N-1, R1) কল করবে, এবং যখন N = 0 হবে, তখন Result = 1 হবে।
উদাহরণ ১: ফ্যাক্টোরিয়াল গণনা
ধরা যাক, আমরা ফ্যাক্টোরিয়াল(5, X) জানতে চাই।
?- ফ্যাক্টোরিয়াল(5, X).প্রোলগের আউটপুট হবে:
X = 120.এটি গণনা করে:
ফ্যাক্টোরিয়াল(5, X) = 5 * 4!ফ্যাক্টোরিয়াল(4, X) = 4 * 3!ফ্যাক্টোরিয়াল(3, X) = 3 * 2!ফ্যাক্টোরিয়াল(2, X) = 2 * 1!ফ্যাক্টোরিয়াল(1, X) = 1 * 0!ফ্যাক্টোরিয়াল(0, 1) = 1
তাহলে, 5! = 5 * 4 * 3 * 2 * 1 = 120
আরও উদাহরণ: রিকার্সিভ রুলস
২. লিস্টের দৈর্ঘ্য গণনা:
ধরা যাক, আমাদের একটি লিস্টের দৈর্ঘ্য বের করতে হবে। রিকার্সিভ নিয়ম ব্যবহার করে লিস্টের দৈর্ঘ্য বের করা যায়। এই নিয়মে, আমরা লিস্টের প্রথম উপাদান (হেড) এবং বাকী অংশ (টেইল) নিয়ে কাজ করি।
লিস্ট_দৈর্ঘ্য([], 0). % বেস কেস: খালি লিস্টের দৈর্ঘ্য 0
লিস্ট_দৈর্ঘ্য([_|Tail], Length) :- লিস্ট_দৈর্ঘ্য(Tail, Length1), Length is Length1 + 1.এখানে:
- প্রথম ফ্যাক্টটি বেস কেস: একটি খালি লিস্টের দৈর্ঘ্য
0 - দ্বিতীয় ফ্যাক্টটি রিকার্সিভ কেস: লিস্টের প্রথম উপাদান বাদ দিয়ে বাকী অংশের দৈর্ঘ্য বের করা হয় এবং এক এক করে দৈর্ঘ্য বাড়ানো হয়।
উদাহরণ ২: লিস্টের দৈর্ঘ্য গণনা
ধরা যাক, আমাদের একটি লিস্ট আছে: [a, b, c]
?- লিস্ট_দৈর্ঘ্য([a, b, c], Length).এখানে, প্রোলগের আউটপুট হবে:
Length = 3.এটি একে একে খালি লিস্ট পর্যন্ত চলে যায়, এবং প্রতিটি ধাপে দৈর্ঘ্য গুণফলে বাড়ায়।
রিকার্সিভ রুলস এর সুবিধা:
- সহজ এবং পরিষ্কার সমাধান: রিকার্সিভ নিয়মের মাধ্যমে কিছু জটিল সমস্যা খুব সহজে সমাধান করা যায়, যেমন ফ্যাক্টোরিয়াল, ফিবোনাচ্চি সিরিজ, এবং লিস্টের দৈর্ঘ্য।
- ফাংশনাল প্রকৃতি: রিকার্সন ব্যবহার করে আপনি কমপ্লেক্স সম্পর্ক এবং কার্যকলাপ তৈরি করতে পারেন যা সহজভাবে সমাধান করা সম্ভব।
- ডেটা স্ট্রাকচার সমাধান: রিকার্সিভ নিয়মগুলি লিস্ট এবং ট্রি এর মতো ডেটা স্ট্রাকচারগুলির সাথে কাজ করার জন্য খুবই উপযোগী। উদাহরণস্বরূপ, লিস্ট ট্র্যাভার্সাল বা বাইনারি ট্রি ডিপথ ফার্স্ট অনুসন্ধান।
রিকার্সিভ রুলস এর সীমাবদ্ধতা:
- পারফরম্যান্স: একাধিক রিকার্সিভ কলের কারণে স্ট্যাক ওভারফ্লো হতে পারে, বিশেষ করে যখন খুব গভীর রিকার্সন হয়।
- কঠিন ডিবাগিং: রিকার্সিভ নিয়মগুলি ডিবাগ করা কিছুটা কঠিন হতে পারে, কারণ এটি একাধিক পর্যায়ে কল করে এবং একের পর এক রিকার্সন ঘটে।
সারসংক্ষেপ:
রিকার্সিভ রুলস প্রোলগে একটি অত্যন্ত শক্তিশালী ধারণা, যা সমস্যার সমাধান করতে স্বয়ংক্রিয়ভাবে নিজেকে কল করে। ফ্যাক্টোরিয়াল, লিস্টের দৈর্ঘ্য এবং ফিবোনাচ্চি সিরিজ এর মতো সমস্যাগুলিতে রিকার্সিভ নিয়মের ব্যবহার অত্যন্ত জনপ্রিয়। এটি সমস্যাগুলির সহজ, পরিষ্কার, এবং কার্যকরী সমাধান প্রদান করতে সহায়ক।
Read more
