রিকার্সন (Recursion) হল একটি কৌশল যেখানে একটি ফাংশন নিজেকে কল করে। এটি বিশেষভাবে ব্যবহারযোগ্য যখন সমস্যা একটি ছোট অংশে বিভক্ত হতে পারে, যার সমাধান পূর্বের সমস্যার সমাধানকে ব্যবহার করে। রিকার্সিভ ফাংশন সাধারণত একটি নির্দিষ্ট শর্তের অধীনে নিজেকে পুনরায় কল করে এবং একসময় একটি ভিত্তি শর্তে পৌঁছায়, যেখানে এটি পুনরায় কল করা বন্ধ করে।
টেইল রিকার্সন (Tail Recursion) হল একটি বিশেষ ধরনের রিকার্সন যেখানে ফাংশন নিজেকে কল করার পরে তার ফলাফল কোনো অপারেশন বা গাণিতিক কাজের জন্য ব্যবহার করা হয় না। এই কৌশলে কম মেমরি ব্যবহার হয় কারণ কম্পাইলার বা ইন্টারপ্রেটার অপ্টিমাইজেশন করে ফাংশন কলগুলোকে একত্রিত করতে পারে।
১. রিকার্সিভ ফাংশন (Recursive Functions)
রিকার্সিভ ফাংশন হল এমন একটি ফাংশন যা নিজেকে কল করে একটি বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় বিভক্ত করে সমাধান করে।
রিকার্সিভ ফাংশনের উদাহরণ
একটি সাধারণ উদাহরণ হিসেবে, আমরা ফ্যাক্টোরিয়াল (Factorial) হিসাব করার রিকার্সিভ ফাংশন দেখব। ফ্যাক্টোরিয়াল হল একটি ধনাত্মক পূর্ণসংখ্যার গুণফল যা ঐ সংখ্যার চেয়ে ছোট প্রতিটি ধনাত্মক পূর্ণসংখ্যার গুণফল দিয়ে নির্ধারিত হয়।
ফ্যাক্টোরিয়াল একটি রিকার্সিভ প্রক্রিয়া, কারণ:
\[
n! = n \times (n-1)!
\]
এটি ফাংশনের ভিত্তি শর্তে গিয়ে থামে: \( 0! = 1 \)
-- ফ্যাক্টোরিয়াল হিসাব করার রিকার্সিভ ফাংশন
function factorial(n)
if n == 0 then -- ভিত্তি শর্ত
return 1
else
return n * factorial(n - 1) -- রিকার্সিভ কল
end
end
-- ফাংশন কল
print(factorial(5)) -- আউটপুট: 120এখানে factorial ফাংশনটি নিজেকে কল করছে যতক্ষণ না n == 0 হয়ে যায়, যেখানে ভিত্তি শর্তে ১ রিটার্ন করা হয়।
২. টেইল রিকার্সন (Tail Recursion)
টেইল রিকার্সন এমন একটি রিকার্সন কৌশল যেখানে রিকার্সিভ কলের পর কোনো অতিরিক্ত কাজ করা হয় না, অর্থাৎ রিকার্সিভ কলের ফলাফল সরাসরি রিটার্ন করা হয়। এটি এমনভাবে ডিজাইন করা হয় যাতে কম্পাইলার বা ইন্টারপ্রেটার ফাংশন কলগুলোকে একত্রিত (optimize) করতে পারে, ফলে মেমরি ব্যবস্থাপনায় উন্নতি হয় এবং স্ট্যাকের ওপরে চাপ কমে।
টেইল রিকার্সন উদাহরণ
ফ্যাক্টোরিয়াল ফাংশনটি সাধারণ রিকার্সনে দেখানো হয়েছিল, এখন আমরা টেইল রিকার্সন দিয়ে একই ফাংশন লিখব। এখানে, একটি সহায়ক ভ্যারিয়েবল ব্যবহার করা হবে যা রিকার্সিভ কলের ফলাফল ধারণ করবে।
-- টেইল রিকার্সন দিয়ে ফ্যাক্টোরিয়াল হিসাব করা
function factorial_tail(n, accumulator)
if n == 0 then
return accumulator
else
return factorial_tail(n - 1, accumulator * n) -- টেইল রিকার্সন
end
end
-- ফাংশন কল (অ্যাকিউমুলেটর 1 দিয়ে শুরু)
print(factorial_tail(5, 1)) -- আউটপুট: 120এখানে, ফাংশন factorial_tail দ্বিতীয় প্যারামিটার accumulator ব্যবহার করছে, যা প্রতিটি রিকার্সিভ কলের মাধ্যমে আপডেট হচ্ছে। ফাংশনটির প্রতিটি কলের পরে কোনো অতিরিক্ত কাজ (যেমন গুণফল) করা হয় না, এবং অবশেষে accumulator ফেরত দেওয়া হয়। এই কৌশলে মেমরি ব্যবহারে উন্নতি হয় এবং কম স্ট্যাক মেমরি প্রয়োজন হয়।
৩. রিকার্সন এবং টেইল রিকার্সনের মধ্যে পার্থক্য
| বৈশিষ্ট্য | রিকার্সিভ ফাংশন | টেইল রিকার্সিভ ফাংশন |
|---|---|---|
| স্ট্যাক মেমরি ব্যবহারের ধরন | প্রতিটি কলের জন্য নতুন স্ট্যাক ফ্রেম তৈরি হয়। | স্ট্যাক ফ্রেম একত্রিত হয়, ফলে কম মেমরি ব্যবহৃত হয়। |
| অপ্টিমাইজেশন | অপ্টিমাইজ করা যায় না। | কম্পাইলার/ইন্টারপ্রেটার এটি অপ্টিমাইজ করতে পারে। |
| ফলাফল ব্যবহারের পদ্ধতি | রিকার্সিভ কলের ফলাফল পরে ব্যবহার হয়। | ফলাফল সরাসরি রিটার্ন করা হয়। |
| ফাংশন কলের মধ্যে পার্থক্য | রিকার্সিভ কলের পর অতিরিক্ত অপারেশন থাকে। | কোন অতিরিক্ত অপারেশন থাকে না। |
৪. সারাংশ
- রিকার্সিভ ফাংশন: ফাংশনটি নিজেকে কল করে সমস্যা সমাধান করে। এটি একাধিক স্ট্যাক ফ্রেম তৈরি করে, তাই মেমরি ব্যবস্থাপনায় বেশি চাপ পড়ে।
- টেইল রিকার্সন: একটি বিশেষ ধরনের রিকার্সন যেখানে রিকার্সিভ কলের পরে কোনো অতিরিক্ত কাজ না করা হয়। এটি অপ্টিমাইজযোগ্য, ফলে কম মেমরি ব্যবহার হয় এবং স্ট্যাকের চাপ কমে।
টেইল রিকার্সন, সাধারণ রিকার্সনের তুলনায় বেশি কার্যকরী হতে পারে যখন মেমরি ব্যবস্থাপনা গুরুত্বপূর্ণ, যেমন বড় আকারের পুনরাবৃত্তির ক্ষেত্রে।
Read more
