রিকার্সিভ ফাংশন

রিকার্সন

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

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

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

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

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(...)]-এর মতো স্ট্রিম ব্যবহার করে। পর্দার আড়ালে, কিছু বিল্টইন রিকার্সন ব্যবহার করে ইমপ্লিমেন্ট করা হয়েছে।