रिकर्शन में

रिकर्शन के बारे में

रिकर्सिव फंक्शन ऐसे फंक्शन होते हैं जो खुद को कॉल करते हैं।

किसी रिकर्सिव फंक्शन में कम से कम एक बेस केस और कम से कम एक रिकर्सिव केस होना चाहिए।

बेस केस फंक्शन को दोबारा कॉल किए बिना एक वैल्यू लौटाता है। रिकर्सिव केस फंक्शन को दोबारा कॉल करता है और इनपुट में ऐसा बदलाव करता है कि वह किसी समय बेस केस से मेल खाने लगे।

यहाँ एक उदाहरण है, जो एक ऐरे के एलिमेंट गिनता है।

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