রিকারশনঃ কোন কিছু যদি নিজেকে নিজে পুনরায় ডাকে, তাই হচ্ছে রিকারশন। এটি মূলত একটা প্রসেস, যেখানে প্রথমে কোন একটা সমস্যার ছোট এবং সহজ সমাধান বের করা হয়। তারপর ঐ ছোট সমাধানের উপর ভিত্তি করে বাকি অংশ গুলো সমাধান করা হয়। সেলুনে গেলে যখন আমরা দাঁড়াই, তখন সামনে পেছনে দুই পাশেই আয়না থাকে। এর ফলে নিজের ছবি বার বার প্রতিফলিত হয়। অনেক বার নিজেকে দেখা যায়। এটা হচ্ছে রিকারসনের একটা উদাহরণ।
রিকার্সিভ ফাংশনঃ সে ফাংশন নিজেকে নিজে কল করে, তাই হচ্ছে রিকার্সিভ ফাংশন। এই কল সরাসরি হতে পারে, আবার অন্য আরেকটা ফাংশন থেকেও হতে পারে।
def recursive_funtion()
recursive_funtion()
উপরের কোডটার দিকে তাকাই। এখানে recursive_funtion() হচ্ছে একটা ফাংশন। যার ভেতরে আবার recursive_funtion() দিয়ে ঐ ফাংশনটাকেই আবার কল করা হয়েছে।
রিকার্সিভ অ্যালগরিদমঃ যে অ্যালগরিদম গুলো রিকার্সিভ ফাংশন ব্যবহার করে কোন সমস্যা সমাধান করে, সেগুলো হচ্ছে রিকার্সিভ অ্যালগরিদম। কিছু অ্যালগরিদম রয়েছে যেগুলোতে রিকারশন ব্যবহার করলে টাইম কমপ্লেক্সিটি কমে যায়। প্রোগ্রামের ইফিশিয়েন্সি বাড়ে।
রিকার্সিভ ফাংশনের তিনটা প্রধান অংশ থাকতে হয়ঃ
- Base Case
- General Case বা Recursive Case
- Step toward Base Case বা সমস্যা ছোট করা।
বেস কেসঃ মূল সমস্যার সবচেয়ে ছোট অংশের সমাধান দেওয়া থাকে বেজ কেসে। এই অংশের সমাধান জানা থাকে, তাই রিকার্সিভ কল না করেই এই অংশের সমাধান দেওয়া যায়। বেজ কেসের কাজ হচ্ছে ক্রমাগত রিকার্সিভ কল করা থামানো। না হলে আজীবন রিকার্সিভ কল করা চলতেই থাকবে। বন্ধ হবে না। তাই একে Halting Case ও বলা যায়। প্রতিটা রিকার্সিভ ফাংশনে মিনিমাম একটা বেস কেস থাকতে হবে। একের অধিকও থাকতে পারে। কিন্তু যদি একটা বেস কেস না থাকে, তাহলে প্রোগ্রাম যেভাবে কাজ করার কথা, ঐভাবে কাজ করবে না।
জেনারেল কেসঃ জেনারেল কেস হচ্ছে যেখানে রিকার্সিভ কল করা হয়। এখানে অন্যান্য ক্যালকুলেশন থাকতে পারে।
সমস্যা ছোট করাঃ রিকার্শনের আরেকটা গুরুত্বপূর্ণ অংশ বা শর্ত হচ্ছে প্রতিটা রিকার্সিভ কল করার পর সমস্যাটা আস্তে আস্তে বেজ কেসের দিকে যেতে হবে। যদি বেস কেসের দিকে না যায়, তাহলে তো কখনোই রিকার্শন শেষ হবে না।
একটা বাস্তব উদাহরণ দেখা যাক। একটা একটা প্রোগ্রামের কথা চিন্তা করি, যেখানে একটা সংখ্যা ইউজার থেকে ইনপুট নিবে, তারপর ১ থেকে ঐ সংখ্যা পর্যন্ত সকল সংখ্যার যোগফল প্রিন্ট করবে। ধরা যাক যখন ইনপুট হিসেবে 4 নিবে তখন সাধারণত একটা প্রোগ্রাম যোগফল নির্নয় করবে নিচের মত করেঃ
sum(4) = 1+2+3+4
যখন ইনপুট হিসেবে থাকবে 5 তখনঃ
sum(5) = 1+2+3+4+5
যখন ইনপুট হিসেবে থাকবে 6 তখনঃ
sum(6) = 1+2+3+4+5+6
এখন আমরা sum(6) কে লিখতে পারি এভাবেঃ 6 + sum(5)। কারণ sum(5) = 1+2+3+4+5। আবার sum(5) কে লিখতে পারি 5 + sum(4)। sum(4) = 1+2+3+4।
এভাবে sum(6) এর জন্য যদি পুরো স্টেপ গুলো লিখে ফেলি, তাহলে স্টেপ গুলো হবে এমনঃ
sum(6) = sum(5) + 6 sum(5) = sum(4) + 5 sum(4) = sum(3) + 4 sum(3) = sum(2) + 3 sum(2) = sum(1) + 2 sum(1) = sum(0) + 1 sum(0) = 0
উপরের স্টেপ গুলো ৬টা সংখ্যার জন্য। এখন আমরা n তম সংখ্যার জন্য সহজ একটা ইকুয়েশন লিখে ফেলতে পারি, sum(n) = sum(n-1) + n।
যখন ০ হবে, তখন প্রিন্ট করবে ০, আর যখন n হবে, তখন প্রিন্ট করবে sum(n) = sum(n-1) + n।
আর এটা সুডো কোডে লিখলেঃ
sum( n ) {
if( n == 0 ) return 0;
else return n + sum( n-1 );
}
পাইথনে খুব সহজেই এই প্রোগ্রামটা লিখে ফেলা যায় এভাবেঃ
def sum_of_n(n):
if n == 0:
return 0
else:
return n + sum_of_n(n - 1)
print(sum_of_n(6))
যা প্রিন্ট করবে ২১। এখন ৭ ইনপুট দিলে প্রিন্ট করবে 28। অন্য সংখ্যা ইনপুট দিয়ে দেখতে পারি।
উপরের উদাহরণে মূল ভিত্তি (base case) হচ্ছে if n == 0: return 0। এই রিকার্সিভ ফাংশন যখনি এই কন্ডিশন পূরণ করবে, তখনি রিকার্সিভ কল করা বন্ধ করবে। আর এখানে রিকার্সিভ বা জেনারেল কেস হচ্ছে n + sum_of_n(n – 1)। আর এর ভেতরেই সমস্যাকে ছোট করা হয়েছে sum_of_n(n – 1) এর মাধ্যমে।
রিকার্শনের আরেকটা উদারহণ দেখি, এবার দেখব রিকার্শন ব্যবহার করে Factorial বের করার উপায়।
একটা সংখ্যার Factorial হচ্ছে ১ থেকে ঐ সংখ্যা পর্যন্ত সব গুলো সংখ্যার গুণফল। একটা সংখ্যার ফ্যাক্টোরিয়াল এভাবে দেখানো হয়ঃ n! এখানে প্রথমেই ধরে নেওয়া হয় ০ এর Factorial হচ্ছে ১।
১ এর ফ্যাক্টোরিয়াল ১।
দুই এর ফ্যাক্টোরিয়াল ১*২ =২।
৩ এর ফ্যাক্টোরিয়াল হচ্ছে ১*২*৩ = ৬।
৪ এর ফ্যাক্টোরিয়াল হচ্ছে ১*২*৩*৪ = ২৪।
৫ এর ফ্যাক্টোরিয়ালঃ 5*4*3*2*1 = 120।
এখন n তম সংখ্যার জন্য এভাবে লিখতে পারিঃ
factorial(n) = (n * factorial(n-1))
আর যেহেতু factorial(0) = 1, আমরা factorial এর জন্য একটা রিকার্সিভ ফাংশনের সুডো কোড লিখে ফেলতে পারি এভাবেঃ
factorial(n) {
if (n == 0) return 1;
else return (n * factorial(n-1));
}
factorial(0) = 1। তাহলে যদি আমরা factorial(3) এর মান বের করি, এই রিকার্শিভ ফাংশনটি এভাবে কাজ করবেঃ
factorial(3) = 3 * factorial(2) 3 * 2 * factorial(1) 3 * 2 * 1 * factorial(0) 3 * 2 * 1 * 1 = 6
পাইথনে খুব সহজেই প্রোগ্রামটা লিখে ফেলতে পারি এভাবেঃ
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
যা প্রিন্ট করবে ১২০।
উপরের উদাহরণে মূল ভিত্তি (base case) হচ্ছে if n == 0: return 1। এই রিকার্সিভ ফাংশনের যখনি এই কন্ডিশন পূরণ করবে, তখনি রিকার্সিভ কল করা বন্ধ করবে। আর এখানে জেনারেল বা রিকার্সিভ কল হচ্ছে sum_of_n(n – 1)। এর ভেতরেই সমস্যাকে ছোট করা হয়েছে factorial(n – 1) এর মাধ্যমে।