রিকারশন হল একটি পদ্ধতি যেখানে একটি ফাংশন বা প্রোগ্রাম নিজেই নিজেকে কল করে। এটি সমস্যা সমাধানের একটি শক্তিশালী কৌশল, যেখানে একটি বড় সমস্যাকে ছোট ছোট সাব-প্রোবলেমে ভাগ করা হয় এবং প্রতি সাব-প্রোবলেমের সমাধান আবার মূল সমস্যার সমাধান হিসেবে কাজ করে।
রিকারশন বিশেষভাবে গণনা এবং সমস্যা সমাধান সম্পর্কিত প্রোগ্রামিংয়ের জন্য ব্যবহার করা হয়, যেখানে একই কাজ একাধিক বার করতে হয়। রিকারশন প্রোগ্রামিংয়ের একটি অত্যন্ত গুরুত্বপূর্ণ ধারণা এবং এটি অনেক সিম্পল ও ক্লিন কোড তৈরি করতে সহায়ক।
রিকারশন একটি বেস কেস এবং রিকার্সিভ কেস নিয়ে কাজ করে:
- বেস কেস: এটি সেই শর্ত, যা কোনো ফাংশন কল করার সময় এক্সিকিউট হওয়ার জন্য নির্ধারিত হয়, যাতে রিকারশন থেমে যায়।
- রিকার্সিভ কেস: এটি সেই অংশ যা নিজেই ফাংশনকে পুনরায় কল করে।
Factorial সমস্যা সমাধানে Recursion
ফ্যাক্টোরিয়াল একটি গাণিতিক ফাংশন, যা কোনো ধনাত্মক পূর্ণসংখ্যার গুণফল নির্ধারণ করে। ফ্যাক্টোরিয়াল একটি খুব সাধারণ সমস্যা যা রিকারশন ব্যবহার করে সমাধান করা হয়।
ফ্যাক্টোরিয়াল (n!) গণনার রিকারসিভ সূত্র:
n! = n * (n-1)!এটি তখন থামে যখন n = 0, কারণ 0! = 1।
ফ্যাক্টোরিয়াল সমস্যা সমাধানে প্রোলগে রিকারশন:
ফ্যাক্টরিয়াল(0, 1). % বেস কেস
ফ্যাক্টরিয়াল(N, Result) :-
N > 0,
N1 is N - 1,
ফ্যাক্টরিয়াল(N1, Result1),
Result is N * Result1.এখানে:
- বেস কেস:
ফ্যাক্টরিয়াল(0, 1)যখনn = 0, ফ্যাক্টোরিয়াল হবে ১। - রিকার্সিভ কেস: যখন
n > 0, তখনN * (N-1)!হিসাব করা হয়, এবং এই প্রক্রিয়া আবার নিজেকে কল করে।
উদাহরণ:
?- ফ্যাক্টরিয়াল(5, X).আউটপুট:
X = 120.এখানে, ৫ এর ফ্যাক্টোরিয়াল হলো ১২০।
Fibonacci সিরিজ সমস্যা সমাধানে Recursion
ফিবোনাচ্চি সিরিজ একটি গাণিতিক সিরিজ, যেখানে প্রতি সংখ্যাটি আগের দুটি সংখ্যার যোগফল হয়। প্রথম দুটি সংখ্যার মান হলো 0 এবং 1। সিরিজটি শুরু হয়: 0, 1, 1, 2, 3, 5, 8, 13,...
ফিবোনাচ্চি সিরিজের জন্য রিকারশন সূত্র:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), যেখানে n > 1ফিবোনাচ্চি সিরিজের জন্য প্রোলগে রিকারশন:
ফিবোনাচ্চি(0, 0). % বেস কেস
ফিবোনাচ্চি(1, 1). % বেস কেস
ফিবোনাচ্চি(N, Result) :-
N > 1,
N1 is N - 1,
N2 is N - 2,
ফিবোনাচ্চি(N1, Result1),
ফিবোনাচ্চি(N2, Result2),
Result is Result1 + Result2.এখানে:
- বেস কেস:
ফিবোনাচ্চি(0, 0)এবংফিবোনাচ্চি(1, 1)। - রিকার্সিভ কেস: ফিবোনাচ্চি(n) কে
ফিবোনাচ্চি(n-1)এবংফিবোনাচ্চি(n-2)এর যোগফল হিসেবে নির্ধারণ করা হয়।
উদাহরণ:
?- ফিবোনাচ্চি(6, X).আউটপুট:
X = 8.এখানে, ৬ তম ফিবোনাচ্চি সংখ্যা হলো ৮।
অন্যান্য সমস্যা সমাধানে Recursion
রিকারশন শুধু ফ্যাক্টোরিয়াল এবং ফিবোনাচ্চি সিরিজের জন্য নয়, বরং অনেক ধরনের সমস্যা সমাধানে ব্যবহার করা যায়। যেমন:
List Operations:
প্রোলগে লিস্টের সাথে কাজ করার সময় রিকারশন ব্যবহৃত হয়। উদাহরণস্বরূপ, একটি লিস্টের সব উপাদানের যোগফল বের করতে রিকারশন ব্যবহার করা যেতে পারে।
যোগফল([], 0). % বেস কেস: খালি লিস্টের যোগফল 0
যোগফল([Head|Tail], Result) :-
যোগফল(Tail, TailResult),
Result is Head + TailResult.উদাহরণ:
?- যোগফল([1, 2, 3, 4], X).আউটপুট:
X = 10.এখানে, লিস্ট [1, 2, 3, 4] এর যোগফল ১০।
Tower of Hanoi:
Tower of Hanoi হল একটি ক্লাসিক্যাল রিকারশন সমস্যা, যেখানে ৩টি খুঁটি এবং কিছু ডিস্ক থাকে, এবং ডিস্কগুলোকে একটি খুঁটি থেকে অন্য খুঁটিতে সরানোর জন্য কিছু শর্ত পালন করতে হয়। এটি একটি খুবই জনপ্রিয় রিকারশন ভিত্তিক সমস্যা।
সারসংক্ষেপ
রিকারশন হল একটি শক্তিশালী সমস্যা সমাধান কৌশল, যেখানে একটি ফাংশন নিজেই নিজেকে কল করে। এটি ফ্যাক্টোরিয়াল, ফিবোনাচ্চি সিরিজ, লিস্ট অপারেশনস, Tower of Hanoi সহ বিভিন্ন গাণিতিক ও লজিক্যাল সমস্যার সমাধানে ব্যবহার করা হয়। রিকারশন সাধারণত দুইটি অংশ নিয়ে গঠিত: বেস কেস (যেখানে রিকারশন থামে) এবং রিকার্সিভ কেস (যেখানে ফাংশন নিজেকে পুনরায় কল করে)।
Read more
