recursion.md

#রিকারসন

ফাংশনাল প্রোগ্রামিং -এ রিকারসন খুব গুরুত্বপূর্ণ একটি বিষয়। খুব সহজে বলতে গেলে, রিকারসন হচ্ছে এমন একটা অবস্থা যেখানে একটি ফাংশন নিজেকেই কল করে।

একটা সমস্যা যেটাকে সমাধানের জন্য ছোট ছোট ভাগে ভাগ করা যেতে পারে এবং প্রত্যেকটি ভাগের কাজ আবার অনেকটা একই রকম হবে, সেরকম ক্ষেত্রে রিকারসিভ ফাংশন তথা রিকারসন খুব কাজে লাগে।

বাস্তব উদাহরণ

ফ্যাক্টরিয়াল সম্পর্কে অনেকেই জানেন, একটা সংখ্যার ফ্যাক্টরিয়াল মানে হচ্ছে সেই সংখ্যা থেকে শুরু করে তার নিচের ক্রমিক সংখ্যা গুলোর প্রত্যেকটির সামগ্রিক গুণফল। অর্থাৎ, 5 এর ফ্যাক্টরিয়াল = 5x4x3x2x1 = 120

এটাকে এভাবেও চিন্তা করা যায়,

5 এর ফ্যাক্টরিয়াল
= 5x(4 এর ফ্যাক্টরিয়াল)
= 5x4x(3 এর ফ্যাক্টরিয়াল)
= 5x4x3(2 এর ফ্যাক্টরিয়াল) = 5x4x3x2(1 এর ফ্যাক্টরিয়াল)
= 5x4x3x2x1

অর্থাৎ প্রত্যেকবার একই কাজ করতে হয় কিন্তু আলাদা আলাদা সংখ্যার জন্য। এবং এই কাজের ফাংশন একটাই হলেই চলে। তাই কি করা যেতে পারে? একই ফাংশনকে বার বার কল করা অর্থাৎ নিজেকে নিজেই একতা নির্দিষ্ট সময় পর্যন্ত কল করা।

প্রোগ্রাম

def factorial(x):
  if x == 1:
    return 1
  else: 
    return x * factorial(x-1)
    
print(factorial(5))

উপরের প্রোগ্রামটি দিয়েই যেকোনো সংখ্যার ফ্যাক্টরিয়াল বের করা সম্ভব। এখানে ফাংশনের শুরুতেই চেক করা হয়েছে যে সংখ্যার ফ্যাক্টরিয়াল বের করতে হবে সেটি 1 কিনা। যদি তাই হয় তাহলে ফ্যাক্টরিয়াল 1 এর মান 1 রিটার্ন করা হচ্ছে। এই অবস্থায় রিকারসন থেমে যায়। এটাকে বেইজ কেস বলা হয়।

এই কন্ডিশন মিথ্যা হলে আরেকটি জিনিষ রিটার্ন করা হয়। কি রিটার্ন করা হয় সেটাই মজার। রিটার্ন করা হচ্ছে সেই সংখ্যা এবং তার সাথে গুন আকারে ঠিক এই ফাংশনকেই (কল) শুধু আর্গুমেন্ট হিসেবে এক ক্রম কমিয়ে দিয়ে। এভাবে ঘটনা ক্রমে এবং প্রয়োজন অনুসারে একটি ফাংশন নিজেই নিজেকে কল করছে যেটাকেই রিকারসন বলা হয়।

আউটপুট

120

বেইজ কেস এর গুরুত্ব

নিচের প্রোগ্রামে কোন বেইজ কেস নাই কিন্তু একটি ফাংশন নিজেই নিজেকে কল করছে। অর্থাৎ এর কল থামার কোন লজিক সেট করা হয় নাই। এটা অনন্তকাল পর্যন্ত চলার চেষ্টা করবে।

def factorial(x):
  return x * factorial(x-1)
    
print(factorial(5))

আউটপুট

RuntimeError: maximum recursion depth exceeded

ডিরেকশন বা দিক

রিকারসন যেকোনো দিকেই ঘটতে পারে। অর্থাৎ প্রথম একটি ফাংশন আরেকটি দ্বিতীয় ফাংশনকে কল করতে পারে আবার সেই দ্বিতীয় ফাংশন প্রথেম ফাংশনকে কল করতে পারে যেটা কিনা আবার দ্বিতীয় ফাংশনকে কল করতে পারে।

উদাহরণ

def is_even(x):
  if x == 0:
    return True
  else:
    return is_odd(x-1)

def is_odd(x):
  return not is_even(x)


print(is_odd(17))
print(is_even(23))

আউটপুট

>>>
True
False
>>>