রিকার্সন মধ্যে

রিকার্সন সম্পর্কে

রিকার্সিভ ফাংশন হলো এমন ফাংশন যা নিজেকে নিজে কল করে।

একটি রিকার্সিভ ফাংশনে অন্তত একটি বেস কেস এবং অন্তত একটি রিকার্সিভ কেস থাকা দরকার।

একটি বেস কেস ফাংশনটিকে আবার কল না করেই একটি মান রিটার্ন করে। একটি রিকার্সিভ কেস ফাংশনটিকে আবার কল করে এবং ইনপুট এমনভাবে পরিবর্তন করে যাতে একসময় তা বেস কেসের সাথে মিলে যায়।

এখানে একটি উদাহরণ দেওয়া হলো যা একটি অ্যারের এলিমেন্টগুলো গোনে।

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

একটি রিকার্সিভ ফাংশনে অনেকগুলো বেস কেস এবং/অথবা অনেকগুলো রিকার্সিভ কেস থাকতে পারে। উদাহরণস্বরূপ ফিবোনাচি সিকোয়েন্স হলো একটি রিকার্সিভ সিকোয়েন্স, যার দুটি বেস কেস আছে।

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

কোনো অ্যারেতে প্রদত্ত কোনো মান x কতবার আছে তা গোনার দুটি রিকার্সিভ কেস আছে।

def count_occurrences(x):
  if length == 0 then
    0
  elif first == x then
    1 + (.[1:] | count_occurrences(x))
  else
    (.[1:] | count_occurrences(x))
  end;

[11, 22, 33, 22, 44] | count_occurrences(22)    # => 2

বাস্তবে অ্যারে ও অন্যান্য ইনুমারেবল ডেটা স্ট্রাকচারের উপর ইটারেশন বেশিরভাগ ক্ষেত্রেই map ও reduce-এর মতো বিল্ট-ইন ফাংশন দিয়ে করা হয়, অথবা [.[] | select(...)]-এর মতো স্ট্রিম ব্যবহার করে করা হয়। ভেতরে ভেতরে কিছু বিল্ট-ইন রিকার্সন ব্যবহার করে তৈরি করা হয়েছে।

অসীম রিকার্সন

রিকার্সিভ ফাংশন ভুলভাবে তৈরি করলে সেটি হয়তো কখনোই তার ফলাফল রিটার্ন করবে না। এটি সমস্যার সৃষ্টি করতে পারে, কারণ প্রতিবার কোনো ফাংশন কল করা হলে মেমরিতে এমন একটি রেফারেন্স সংরক্ষিত হয় যেখানে VM ফলাফলটি রিটার্ন করবে (কল স্ট্যাক-এ)। কোনো রিকার্সিভ ফাংশন যদি অসীমভাবে নিজেকে কল করে, তাহলে মেমরি শেষ হয়ে যেতে পারে এবং VM একটি স্ট্যাক ওভারফ্লো এরর নিয়ে ক্র্যাশ করতে পারে।

অসীম রিকার্সনের এই সমস্যাটি যেসব কারণে হতে পারে:

• বেস কেস লিখতে ভুলে যাওয়া।
• বেস কেসটিকে প্রথম ক্লজ হিসেবে না লেখা।
• রিকার্সিভ কল করার সময় আর্গুমেন্ট ঠিকভাবে পরিবর্তন না করা, ফলে বেস কেসে কখনোই পৌঁছানো না যায়।

টেল কল অপটিমাইজেশন

উইকিপিডিয়ায় যেমন বর্ণনা করা হয়েছে:

টেল কল হলো একটি প্রসিডিউরের শেষ কাজ হিসেবে করা একটি সাবরুটিন কল। টেল কলের লক্ষ্য যদি একই সাবরুটিন হয়, তবে সেই সাবরুটিনকে টেল রিকার্সিভ বলা হয়।

উপরে ইমপ্লিমেন্ট করা fibonacci-টি লক্ষ্য করুন। এর রিকার্সিভ কেসটি নিজেকে দুবার কল করে। ফাংশনটিকে যে শেষ কাজটি করতে হয় তা হলো যোগ। যেহেতু শেষ কাজটি নিজেকে কল করা নয়, তাই ফাংশনটি রিকার্সিভ, তবে টেল রিকার্সিভ নয়।

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

jq আসলেই টেল কল অপটিমাইজেশন করে, তবে কেবল ০-আর্গুমেন্ট ফাংশনের জন্য। এটি কাজে লাগানোর উপায় হলো এমন একটি "ভেতরের" ০-আর্গুমেন্ট ফাংশন ডিফাইন করা, যা ইনপুট হিসেবে একধরনের স্টেট নেয়। ভেতরের ফাংশনটি প্রয়োজন অনুযায়ী স্টেট পরিবর্তন করতে পারে এবং নতুন স্টেটটি টেল রিকার্সিভ কলে পাঠাতে পারে। বাইরের ফাংশনটি প্রাথমিক স্টেট তৈরি করে এবং রিকার্সন শুরু করার জন্য সেটি ভেতরের ফাংশনে পাঠায়।

এখন পর্যন্ত গণনা করা সিরিজটি স্টেটের অংশ হিসেবে রেখে একটি টেল-রিকার্সিভ fibonacci ফাংশন ইমপ্লিমেন্ট করা যেতে পারে।

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55