पुनरावृत्ति (Recursion)
प्रोग्रामिंग सीखते समय, हम अक्सर कार्यों को एक रैखिक, सीधे तरीके से हल करते हैं। लेकिन अगर हमें ऐसी समस्या का सामना करना पड़े जिसे छोटे, समान समस्याओं में तोड़ने की आवश्यकता हो, तब क्या होगा? यहीं पर पुनरावृत्ति उपयोगी होती है।
सरल शब्दों में, पुनरावृत्ति वह होती है जब कोई फ़ंक्शन अपने निष्पादन के दौरान स्वयं को कॉल करता है। यह सुनकर ऐसा लग सकता है कि यह एक अंतहीन लूप बना देगा, लेकिन अगर हम अपने फ़ंक्शन को सही ढंग से डिज़ाइन करें, तो यह अंततः ऐसे बिंदु पर पहुंचेगा जहां यह स्वयं को और कॉल नहीं करेगा।
एक मातृयोश्का गुड़िया की कल्पना करें। हर बार जब आप एक गुड़िया खोलते हैं, तो उसके अंदर एक और छोटी गुड़िया होती है, और आप तब तक ऐसा करते रहते हैं जब तक आपको सबसे छोटी गुड़िया नहीं मिल जाती जिसे खोला नहीं जा सकता। गुड़ियाओं को खोलने की यह प्रक्रिया कुछ हद तक पुनरावृत्ति जैसी है। सबसे छोटी गुड़िया तक पहुंचने के लिए, जो सबसे जटिल समस्या को हल करने जैसा है, आप इसी समस्या के आसान संस्करणों (बड़ी गुड़ियाओं को खोलना) को बार-बार हल करके इसे प्राप्त करते हैं, जब तक कि आप ऐसे बिंदु पर न पहुंच जाएं जहां समस्या को और छोटा नहीं किया जा सकता (अंतिम गुड़िया)।
किसी बड़ी समस्या को पुनरावृत्तिगत रूप से छोटे समस्याओं में विभाजित करते हुए तब तक हल करने की प्रक्रिया जब तक कि सबसे छोटी/सरल संभव समस्या तक नहीं पहुंचा जाए, "पुनरावृत्ति के विश्वास की छलांग" की अवधारणा से सबसे अच्छी तरह समझी जा सकती है।
पुनरावृत्ति के विश्वास की छलांग
जब किसी समस्या का पुनरावृत्तिगत समाधान लागू करते हैं, तो आमतौर पर एक फ़ंक्शन बनाया जाता है जो किसी बिंदु पर स्वयं को कॉल करके काम करता है। स्वयं को कॉल करने वाले हिस्से को आमतौर पर पुनरावृत्तिगत कॉल कहा जाता है।
पुनरावृत्तिगत समाधानों का सबसे अच्छा हिस्सा यह है कि आप मान सकते हैं कि फ़ंक्शन सरल तर्कों के साथ सही ढंग से काम करता है, और फिर कठिन तर्कों के लिए सही व्यवहार लागू करते हैं। जैसे हम अन्य फ़ंक्शन्स जैसे
sqrt, max, abs आदि को कॉल करते हैं, आप मान सकते हैं कि फ़ंक्शन छोटे/सरल तर्कों के लिए काम करता है और वर्तमान परिणाम को उन पर आधारित करके बनाते हैं।💡
एकमात्र आवश्यकता यह सुनिश्चित करना है कि फ़ंक्शन आधार मामले (सबसे सरल मामला) तक पहुंचेगा। अन्यथा, हमारा पुनरावृत्तिगत फ़ंक्शन अनंत समय तक चलेगा और StackOverflow हो सकता है!
इस बात का प्रदर्शन करने के लिए कि कैसे एक पुनरावृत्तिगत फ़ंक्शन में गणना हो सकती है, हम संख्या
n दिए जाने पर 0, 1, 2, ..., n तक की सभी संख्याओं का योग निकालने का प्रयास कर सकते हैं।आइए हम चरण-दर-चरण
sum फ़ंक्शन को लागू करें। पहला चरण यह सुनिश्चित करना है कि फ़ंक्शन सबसे सरल मामले में सही ढंग से काम करता है (जब n 0 या 1 हो तो सही ढंग से योग निकालें):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # यदि n 0 है => योग 0 है
return 0 # यहाँ फ़ंक्शन का निष्पादन रोकें
if n == 1: # यदि n 1 है => योग 1 है
return 1 # यहाँ फ़ंक्शन का निष्पादन रोकें
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (क्योंकि हमने इस भाग को अभी तक लागू नहीं किया है)फ़ंक्शन के इस हिस्से के साथ, हम पहले से ही इस तथ्य का उपयोग कर सकते हैं कि
sum(0) हमेशा सही ढंग से 0 लौटाएगा, जबकि sum(1) हमेशा 1 लौटाएगा। फ़ंक्शन सही ढंग से काम करेगा, भले ही हम sum फ़ंक्शन को 0 या 1 तर्कों के साथ स्वयं से कॉल करें।तो, हम एक कदम और आगे बढ़ सकते हैं और
sum(1) और sum(0) के परिणामों का उपयोग करके n = 2 और n = 3 के लिए sum फ़ंक्शन को लागू कर सकते हैं:def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # यदि n 2 है, तो हम sum(1) के परिणाम में 2 जोड़ सकते हैं
return n + sum(1) # या n + sum(n - 1)
if n == 3: # यदि n 3 है, तो हम sum(2) के परिणाम में 3 जोड़ सकते हैं
return n + sum(2) # या n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (क्योंकि हमने इस भाग को अभी तक लागू नहीं किया है)इस तरह, यह स्पष्ट है कि
sum फ़ंक्शन छोटे मामलों जैसे n के 0, 1, 2, या 3 होने पर सही ढंग से काम करता है।अब, हम उन अन्य
n मूल्यों के लिए फ़ंक्शन को लागू कर सकते हैं जो 3 से बड़े हैं। एकमात्र आवश्यकता यह है कि जब हम sum फ़ंक्शन को स्वयं से कॉल करें, तो हम उन छोटे n मूल्यों (0, 1, 2, या 3) तक पहुंचें। तो, बड़े n मूल्यों के लिए, जैसे 4, 5, या 6, आदि, हम sum फ़ंक्शन को इस तथ्य का उपयोग करके लागू कर सकते हैं कि sum(4) की गणना करते समय, हम sum(3) के परिणाम में 4 जोड़ सकते हैं, जबकि sum(5) की गणना 5 को sum(4) के परिणाम में जोड़कर की जा सकती है:def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# अन्य सभी मामलों के लिए (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...पुनरावृत्तिगत फ़ंक्शन के मुख्य हिस्से हैं:
- आधार मामला: एक शर्त जो पुनरावृत्ति को रोकती है। इसके बिना, फ़ंक्शन स्वयं को अनिश्चितकाल तक कॉल करता रहेगा, जिससे एक अनंत लूप बन जाएगा।
यहाँ, यह है
n == 0औरn == 1।
- पुनरावृत्तिगत चरण: जहाँ फ़ंक्शन स्वयं को कॉल करता है, आमतौर पर एक अलग तर्क के साथ।
यहाँ, यह है
sum(n - 1)।
चूंकि
n == 1, n == 2, और n == 3 के लिए कॉल्स बिल्कुल n == 4, n == 5 आदि के समान हैं, हम sum फ़ंक्शन को केवल एक आधार मामले (जब n == 0 हो) के साथ और भी सरल बना सकते हैं:def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...इस तरह, पुनरावृत्ति के विश्वास की छलांग लेते हुए, हम मानते हैं/जानते हैं कि फ़ंक्शन छोटे/सरल मामलों के लिए सही ढंग से काम करता है, और उन सरल मामलों के आधार पर फ़ंक्शन के बाकी हिस्सों का निर्माण करते हैं। इससे यह समझने में मदद मिलती है कि पुनरावृत्तिगत फ़ंक्शन्स कैसे काम करते हैं और उन्हें कैसे लागू किया जा सकता है।
💡
पुनरावृत्तिगत रूप से फ़ंक्शन को कॉल करना ऐसा है जैसे आप एक पूरी तरह से अलग फ़ंक्शन को कॉल कर रहे हैं जिसके बारे में आप निश्चित रूप से जानते हैं कि वह दिए गए तर्कों के साथ काम करेगा।