রিকারশন হল একটি সমস্যা সমাধানের কৌশল যেখানে একটি ফাংশন নিজেকে কল করে। নিচে তিনটি মৌলিক রিকারশন প্রোগ্রামের উদাহরণ দেওয়া হলো: ফ্যাক্টোরিয়াল, ফিবোনাচ্চি সিরিজ এবং টাওয়ার অফ হ্যানয়।
১. ফ্যাক্টোরিয়াল (Factorial)
ফ্যাক্টোরিয়াল একটি সংখ্যা \( n \)এর জন্য সকল ধনাত্মক পূর্ণসংখ্যার গুণফল, যা \( n! \) দিয়ে চিহ্নিত করা হয়।
ফর্মুলা:
- \( n! = n \times (n-1)! \)
- বেস কেস: \( 0! = 1 \)
উদাহরণ:
def factorial(n):
if n == 0: # বেস কেস
return 1
else:
return n * factorial(n - 1) # রিকারসিভ কেস
# ব্যবহার
num = 5
print(f"Factorial of {num} is {factorial(num)}") # আউটপুট: 120
২. ফিবোনাচ্চি (Fibonacci)
ফিবোনাচ্চি সিরিজ হল এমন একটি সংখ্যা সিরিজ যেখানে প্রতিটি সংখ্যার মান পূর্ববর্তী দুইটি সংখ্যার যোগফল।
ফর্মুলা:
- \( F(n) = F(n-1) + F(n-2) \)
- বেস কেস: \( F(0) = 0, F(1) = 1 \)
উদাহরণ:
def fibonacci(n):
if n == 0: # বেস কেস
return 0
elif n == 1: # বেস কেস
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2) # রিকারসিভ কেস
# ব্যবহার
num = 6
print(f"Fibonacci of {num} is {fibonacci(num)}") # আউটপুট: 8
৩. টাওয়ার অফ হ্যানয় (Tower of Hanoi)
টাওয়ার অফ হ্যানয় একটি ক্লাসিকাল রিকারশন সমস্যা যেখানে তিনটি স্ট্যাকে (এ, বি, সি) ডিস্কগুলি স্থানান্তর করতে হয়। লক্ষ্য হল প্রথম স্ট্যাক থেকে সব ডিস্কগুলি দ্বিতীয় স্ট্যাকে স্থানান্তর করা, তবে কোনো বড় ডিস্ক ছোট ডিস্কের উপরে রাখতে হবে না।
ফর্মুলা:
- \( 1 \) ডিস্ক: সরাসরি গন্তব্যে স্থানান্তর করুন।
- \( n \) ডিস্ক:
1. \( n-1 \) ডিস্ককে একটি সহায়ক স্ট্যাকে সরান।
2. বড় ডিস্ককে গন্তব্যে সরান।
3. \( n-1 \) ডিস্ককে গন্তব্যে সরান।
উদাহরণ:
def tower_of_hanoi(n, source, target, auxiliary):
if n == 1: # বেস কেস
print(f"Move disk 1 from {source} to {target}")
return
tower_of_hanoi(n - 1, source, auxiliary, target) # 1. Move n-1 disks from source to auxiliary
print(f"Move disk {n} from {source} to {target}") # 2. Move the nth disk from source to target
tower_of_hanoi(n - 1, auxiliary, target, source) # 3. Move n-1 disks from auxiliary to target
# ব্যবহার
num_disks = 3
tower_of_hanoi(num_disks, 'A', 'C', 'B') # 'A' source, 'C' target, 'B' auxiliary
উপসংহার
রিকারশন একটি শক্তিশালী সমস্যা সমাধানের কৌশল যা বিভিন্ন সমস্যায় কার্যকরী। ফ্যাক্টোরিয়াল, ফিবোনাচ্চি সিরিজ এবং টাওয়ার অফ হ্যানয় উদাহরণ হিসেবে দেখানো হয়েছে। এই উদাহরণগুলো রিকারশন কিভাবে কাজ করে এবং সমস্যা সমাধানে কিভাবে ব্যবহার করা যায় তার একটি পরিষ্কার ধারণা প্রদান করে।
