রুবিতে রিকার্শন (recursion) কী?
রিকার্সিভ ফাংশনগুলো হলো যেগুলো নিজেদের কল করতে থাকে যতক্ষণ না তারা একটি এন্ড গোয়াল পর্যন্ত পৌঁছায় (যাকে বেস কেস ও বলা হয়)। প্রতিটি ফাংশন কলের পর আপনি এই বেস কেসের দিকে অগ্রসর হন, বাকি কাজের পরিমাণ কমিয়ে।
একবার বেস কেস পাওয়া যাওয়ায়, রিকার্শন শেষ হয়, এবং ফাংশনগুলো রিটার্ন করা শুরু করে।
রুবি রিকার্শন
রিকার্শন শিখতে একটি ক্লাসিক উদাহরণ হলো ফ্যাক্টোরিয়াল নাম্বার ক্যালকুলেট করা।
দেখি রুবিতে ইটেরেশন এবং রিকার্শন দুটি দিয়ে আমরা কীভাবে এটি করতে পারি!
একটি নাম্বারের ফ্যাক্টোরিয়াল ক্যালকুলেট করতে হলে ১ থেকে আমাদের টার্গেট নাম্বার পর্যন্ত সকল নাম্বার গুন করতে হয়। উদাহরণস্বরূপ, ৫-এর ফ্যাক্টোরিয়াল: 1 * 2 * 3 * 4 * 5 = 120।
দেখি রুবি এবং রিকার্শন দিয়ে আমরা কীভাবে এটি করতে পারি।
উদাহরণ:
def iterative_factorial(n) (1..n).inject(:*) end def recursive_factorial(n) # Base case return 1 if n <= 1 # Recursive call n * recursive_factorial(n-1) end
এই উদাহরণে আমি আপনাকে ফ্যাক্টোরিয়াল নাম্বার ক্যালকুলেট করার দুটি পদ্ধতি দেখিয়েছি। ইটেরেটিভ এবং রিকার্সিভ সমাধান।
রিকার্সিভ সমাধানে আমরা যে নাম্বারের সাথে কাজ করছি সেটি কমিয়ে (n-1) প্রগতি করি। একবার (n <= 1) হলে আর কোনো রিকার্সিভ কল থাকে না, এবং যা হয় সেটি হলো:
return 1 # recursive_factorial(1) return 2 * 1 # recursive_factorial(2) return 3 * 2 # recursive_factorial(3) return 4 * 6 # recursive_factorial(4) return 5 * 24 # recursive_factorial(5)
রুবি ডেভেলপাররা অধিকাংশ সময় ইটেরেটিভ সমাধানই বেছে নেয়, এবং এটি চমৎকার, কিন্তু আমি মনে করি রিকার্শন কীভাবে কাজ করে সেটা জানা ও চাকরি।
এখন আরেকটি ক্লাসিক উদাহরণ দেখি: ফিবোনাচ্চি নম্বর।
ফিবোনাচ্চি সিকোয়েন্স
লিওনার্দো ফিবোনাচ্চি এই সিকোয়েন্সটি আবিষ্কার করেছিলেন আদর্শ কন্ডিশনে খরগোশ জনসংখ্যার বৃদ্ধি মডেল করার সময়।
সিকোয়েন্সটি ক্যালকুলেট করা হয় বর্তমানটির আগের দুটি নাম্বার যোগ করে।
উদাহরণ:
1, 1, 2, 3, 5, 8, 13, 21
রুবিতে এটি ক্যালকুলেট করতে আপনি একটি রিকার্সিভ ফাংশন ব্যবহার করতে পারেন:
def fib(n) return n if n < 2 fib(n-1) + fib(n-2) end
এই ফাংশন এবং একটি রেঞ্জ ব্যবহার করে আপনি সহজে প্রথম ২০টি ফিবোনাচ্চি নাম্বার ক্যালকুলেট করতে পারেন।
(1..20).each { |n| puts fib(n) }
তবে, একটা সমস্যা আছে:
আপনার ফাংশনটি অনেক এক্সট্রা কাজ করছে যেটার প্রয়োজন নেই। এটি বুঝতে নিচের ছবিটি দেখুন।
ছবিতে আমরা দেখতে পাচ্ছি fib(3) পাঁচবার ক্যালকুলেট হচ্ছে। এটি আপনার ফাংশনকে খুব স্লো করে দেবে আপনি যদি লম্বা ফিবোনাচ্চি সিকোয়েন্স ক্যালকুলেট করার চেষ্টা করেন।
সমাধান? মেমোইজেশন।
মেমোইজেশন: ইতিমধ্যে করা কাজ পুনরায় ব্যবহার
কি হয় যদি আপনি ইতিমধ্যে করা কাজগুলো পिछले স্টেপগুলোতে পুনরায় ব্যবহার করতে পারেন?
আমরা এটা মেমোইজেশন ব্যবহার করে করতে পারি।
আমাদের ব্যয়বহুল ক্যালকুলেশন রেজাল্ট সেভ করতে আমরা একটি ক্যাশ ব্যবহার করি। এই কেসে, একটি অ্যারে যথেষ্ট।
উদাহরণ:
@cache = [0,1] def fib(n) return @cache[n] if @cache[n] @cache[n] = fib(n-1) + fib(n-2) end
প্রথমে আমরা চেক করি রেজাল্ট ক্যাশে আছে কিনা, থাকলে রিটার্ন করি, অন্যথায় ক্যালকুলেশন করি এবং রেজাল্ট সেভ করি।
এটি অনেক দ্রুত রান করবে এবং অনেক বড় ফিবোনাচ্চি নাম্বার ক্যালকুলেট করতে পারবে।
রিকার্শনের সীমাবদ্ধতা
যেসব পাঠক বলেছেন, রিকার্সিভ সমাধান SystemStackError: stack level too deep দিয়ে ফেল করতে পারে বড় ইনপুট নাম্বারের সাথে (প্রায় ৭৫০০ এর আশেপাশে, সঠিক নাম্বার আপনার সিস্টেমের ওপর নির্ভর করে)।
আপনি যদি আরও বড় নাম্বার ক্যালকুলেট করতে চান তবে আপনাকে ইটেরেটিভ সমাধান ব্যবহার করতে হবে।
উদাহরণ:
memo = [] (0..n).each do |i| memo[i] = i < 2 ? i : memo[i-1] + memo[i-2] end
উপসংহার
রিকার্শন দারুণ কিন্তু কখনো কখনো এটি বুঝতে কঠিন হতে পারে। এখন আপনার পালা, প্র্যাকটিস ইজ মাস্টারি!
দয়া করে এই পোস্ট শেয়ার করুন আপনার পছন্দ হলে এবং আমার নিউজলেটার সাবস্ক্রাইব করুন 🙂
