रिकर्शन क्या है?
फ़ंक्शन कोड का एक नाम वाला हिस्सा है जो एक काम करता है। आम तौर पर यह दूसरे फ़ंक्शनों को पुकारता है।
रिकर्सिव फ़ंक्शन ख़ुद को पुकारता है। यह बड़े प्रश्न को हल करने के लिए पहले उसी प्रश्न की छोटी कॉपी हल करता है।
उदाहरण: फ़ैक्टोरियल n! = n × (n − 1) × … × 1। ध्यान दीजिए 5! = 5 × 4!। तो fact(5) के लिए fact(4) निकालकर 5 से गुणा कीजिए।
def fact(n):
if n == 1: # आधार स्थिति
return 1
return n * fact(n - 1) # रिकर्सिव स्थिति
आधार स्थिति और रिकर्सिव स्थिति
हर सही रिकर्सिव फ़ंक्शन के दो हिस्से होते हैं:
- आधार स्थिति (base case): सबसे सरल इनपुट, जिसका उत्तर बिना और पुकारे सीधे मिलता है। फ़ैक्टोरियल में n = 1 (या n = 0) पर 1।
- रिकर्सिव स्थिति (recursive case): फ़ंक्शन छोटे इनपुट के साथ ख़ुद को पुकारता है, ताकि हर क़दम आधार स्थिति के पास पहुँचे।
कोई भी हिस्सा ग़लत हो तो फ़ंक्शन कभी नहीं रुकता। जैसे आधार स्थिति के बिना fact(n − 1), या fact(n + 1) जो उससे दूर जाता है।
कॉल स्टैक और स्टैक फ़्रेम
कंप्यूटर अधूरी पुकारों का हिसाब कॉल स्टैक से रखता है। स्टैक थालियों के ढेर जैसा है: जो आख़िर में रखी, वही पहले उठेगी (LIFO)।
हर पुकार को एक स्टैक फ़्रेम मिलता है। इसमें उसके पैरामीटर (जैसे n), स्थानीय चर और रिटर्न पता (ख़त्म होने के बाद कहाँ लौटना है) रहते हैं।
- fact(4) शुरू होता है और fact(3) का इंतज़ार करता है। उसका फ़्रेम स्टैक पर रहता है।
- fact(3), fact(2) का और fact(2), fact(1) का इंतज़ार करता है।
- fact(1) आधार स्थिति पर 1 लौटाता है। उसका फ़्रेम हट जाता है।
- अब हर इंतज़ार करता फ़्रेम अपना गुणा पूरा करके बारी-बारी हटता है।
बहुत सारे फ़्रेम स्टैक की मेमोरी भर देते हैं। प्रोग्राम स्टैक ओवरफ़्लो से रुक जाता है (Python में RecursionError)।
रिकर्सिव फ़ंक्शन को ट्रेस करना
ट्रेस करने के लिए हर पुकार नई पंक्ति में, एक स्तर अंदर खिसकाकर लिखिए। पुकार लौटे तो उसका मान लिखकर ऊपर लौटिए।
power(2, 3)
power(2, 2)
power(2, 1)
power(2, 0) returns 1
returns 2 × 1 = 2
returns 2 × 2 = 4
returns 2 × 4 = 8जो फ़ंक्शन ख़ुद को दो बार पुकारे, जैसे फ़िबोनाची fib(n) = fib(n − 1) + fib(n − 2), वह पुकारों का पेड़ बनाता है। fib(5) में fib(3) दो बार और fib(2) तीन बार बनता है, यानी बहुत काम दोहराया जाता है। पहले से निकाले उत्तर सँभालकर रखना (मेमोइज़ेशन) इसे ठीक करता है।
रिकर्सिव खोज और छँटाई
बाइनरी सर्च (क्रमबद्ध सूची में): बीच वाला आइटम देखिए। वही लक्ष्य हो तो रुकिए (आधार स्थिति)। लक्ष्य छोटा हो तो बाएँ आधे में, बड़ा हो तो दाएँ आधे में खोजिए। ख़ाली सीमा दूसरी आधार स्थिति है (नहीं मिला)। हर पुकार सूची आधी करती है, तो 1 000 आइटमों के लिए लगभग 10 पुकारें काफ़ी हैं।
मर्ज सॉर्ट: 0 या 1 आइटम की सूची पहले से क्रम में है (आधार स्थिति)। वरना सूची को दो आधों में बाँटिए, हर आधे को रिकर्शन से क्रम में लगाइए, फिर दोनों क्रमबद्ध आधों को मिलाइए। यह "बाँटो और जीतो" विचार कई तेज़ एल्गोरिदम की नींव है।
रिकर्शन या लूप?
रिकर्शन से होने वाला हर काम लूप (इटरेशन) से भी हो सकता है, और उल्टा भी।
- रिकर्शन उन प्रश्नों के लिए छोटा और साफ़ है जो स्वभाव से एक-के-अंदर-एक हैं: पेड़, फ़ोल्डर, बाँटो-और-जीतो, फ़्रैक्टल।
- लूप कम मेमोरी लेता है (फ़्रेमों का ढेर नहीं) और स्टैक ओवरफ़्लो नहीं होता।
कुछ भाषाएँ (फ़ंक्शनल भाषाएँ) दोहराने के लिए मुख्य रूप से रिकर्शन ही उपयोग करती हैं।
करके देखिए: कक्षा की क़तार
क़तार के आख़िरी विद्यार्थी से पूछिए: "तुम्हारे आगे कितने लोग हैं?" वह गिनता नहीं। वह आगे वाले से यही प्रश्न पूछता है और उत्तर में 1 जोड़ता है। क़तार में पहले विद्यार्थी के आगे कोई नहीं, वह 0 कहता है (आधार स्थिति)। उत्तर पीछे लौटते आते हैं। फिर Python में fact(n) लिखकर n = 5 पर चलाइए और 3D के चरण 4 से मिलाइए।
मुख्य सूत्र और परिभाषाएँ
- fact(n) = 1 अगर n = 1, वरना n × fact(n − 1)
- fib(n) = n अगर n < 2, वरना fib(n − 1) + fib(n − 2)
- sum(सूची) = 0 अगर ख़ाली, वरना पहला + sum(बाक़ी)
- बाइनरी सर्च: n आइटम के लिए लगभग log₂(n) पुकारें
- fact(n) की स्टैक गहराई = n फ़्रेम
हल किए गए उदाहरण
1. 1 से n तक की संख्याएँ जोड़ने वाला रिकर्सिव फ़ंक्शन लिखिए।
आधार स्थिति: n = 0 → 0 लौटाओ। रिकर्सिव स्थिति: n + total(n − 1) लौटाओ। <pre>def total(n): if n == 0: return 0 return n + total(n - 1)</pre>total(4) = 4 + 3 + 2 + 1 + 0 = 10।
2. fact(3) ट्रेस कीजिए और स्टैक दिखाइए।
पुकारें: fact(3) → fact(2) → fact(1)। सबसे ऊँचा स्टैक: fact(3) के ऊपर fact(2), उसके ऊपर fact(1)। लौटना: fact(1) = 1, fact(2) = 2 × 1 = 2, fact(3) = 3 × 2 = 6।
3. इसमें क्या ग़लत है: def f(n): return n * f(n - 1)
आधार स्थिति नहीं है। f(3) → f(2), f(1), f(0), f(−1)… बिना रुके। Python इसे RecursionError (स्टैक ओवरफ़्लो) से रोकता है। जोड़िए: if n <= 1: return 1।
4. स्ट्रिंग उल्टी करने वाला रिकर्सिव फ़ंक्शन लिखिए।
आधार स्थिति: ख़ाली स्ट्रिंग वैसी ही लौटे। वरना आख़िरी अक्षर + बाक़ी का उल्टा। <pre>def rev(s): if s == "": return "" return s[-1] + rev(s[:-1])</pre>rev("cat") = "t" + rev("ca") = "t" + "a" + rev("c") = "tac"।
5. सादे रिकर्शन में fib(4) कुल कितनी पुकारें करता है?
fib(4) → fib(3), fib(2)। fib(3) → fib(2), fib(1)। हर fib(2) → fib(1), fib(0)। गिनती: fib(4) 1, fib(3) 1, fib(2) 2, fib(1) 3, fib(0) 2 = 9 पुकारें।
6. [3, 8, 15, 23, 42, 57, 61] में 57 को बाइनरी सर्च से खोजिए।
पुकार 1: बीच में 23 (इंडेक्स 3); 23 < 57 → दायाँ आधा [42, 57, 61]। पुकार 2: बीच में 57 → मिल गया। 2 पुकारें।
आम गलतियाँ
- आधार स्थिति भूल जाना, जिससे फ़ंक्शन कभी नहीं रुकता और स्टैक ओवरफ़्लो होता है।
- ऐसी रिकर्सिव स्थिति लिखना जो छोटी न हो, जैसे f(n − 1) की जगह फिर f(n) पुकारना।
- फ़ंक्शन पुकारना पर उसका परिणाम न लौटाना: return n * fact(n − 1) की जगह सिर्फ़ fact(n − 1) लिखना।
- सोचना कि सारी पुकारें एक साथ चलती हैं। वे स्टैक पर क्रम से इंतज़ार करती हैं; आख़िर में पुकारी गई सबसे पहले ख़त्म होती है।