Python Language
प्रत्यावर्तन
खोज…
टिप्पणियों
stopCondition को रोकने के लिए स्टॉप कंडीशन stopCondition आवश्यकता होती है।
मूल चर को पुनरावर्ती फ़ंक्शन पर पारित किया जाना चाहिए ताकि यह संग्रहीत हो जाए।
1 से n तक संख्याओं का योग
यदि मैं 1 से n तक की संख्याओं का पता लगाना चाहता था जहाँ n एक प्राकृतिक संख्या है, तो मैं 1 + 2 + 3 + 4 + ... + (several hours later) + n । वैकल्पिक रूप से, मैं एक लूप के for लिख सकता हूं:
n = 0
for i in range (1, n+1):
n += i
या मैं एक ऐसी तकनीक का उपयोग कर सकता हूं जिसे रिकर्सन के नाम से जाना जाता है:
def recursion(n):
if n == 1:
return 1
return n + recursion(n - 1)
उपरोक्त दो विधियों में रिकर्सन के फायदे हैं। 1 से 3 तक की राशि के लिए 1 + 2 + 3 लिखने से recursion(4) कम समय लगता है। recursion(4) , पुनरावृत्ति का उपयोग पीछे की ओर काम करने के लिए किया जा सकता है:
फंक्शन कॉल: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
जबकि लूप के for फॉरवर्ड सख्ती से काम कर रहा है: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10)। कभी-कभी पुनरावर्ती समाधान पुनरावृत्त समाधान की तुलना में सरल होता है। यह स्पष्ट है जब एक लिंक्ड सूची के उलट को लागू करना।
क्या, कैसे, और कब की पुनरावृत्ति
पुनरावृत्ति तब होती है जब कोई फ़ंक्शन कॉल मूल फ़ंक्शन कॉल समाप्त होने से पहले उसी फ़ंक्शन को फिर से कॉल करने का कारण बनता है। उदाहरण के लिए, प्रसिद्ध गणितीय अभिव्यक्ति x! विचार करें x! (यानी तथ्यपरक संचालन)। भाज्य संचालन को सभी गैर-पूर्णांक पूर्णांक के लिए परिभाषित किया गया है:
- यदि संख्या 0 है, तो उत्तर 1 है।
- अन्यथा, उत्तर यह है कि संख्या उस संख्या की तुलना में कम के भाज्य को गुणा करती है।
पायथन में, फैक्टोरियल ऑपरेशन के एक भोले कार्यान्वयन को एक फ़ंक्शन के रूप में परिभाषित किया जा सकता है:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
पुनरावृत्ति कार्यों को कभी-कभी समझ पाना मुश्किल हो सकता है, तो चलिए इस चरण-दर-चरण चलते हैं। अभिव्यक्ति के factorial(3) पर विचार करें factorial(3) । यह और सभी फ़ंक्शन कॉल एक नया वातावरण बनाते हैं । एक पर्यावरण मूल रूप से केवल एक तालिका है जो पहचानकर्ताओं (जैसे n , factorial , print , आदि) को उनके संबंधित मूल्यों पर मैप करता है। किसी भी समय, आप locals() का उपयोग करके वर्तमान वातावरण तक पहुंच सकते हैं। पहले फ़ंक्शन कॉल में, केवल स्थानीय चर जो परिभाषित होता है वह n = 3 । इसलिए, मुद्रण locals() दिखाएगा {'n': 3} । n == 3 बाद से, वापसी मूल्य n * factorial(n - 1) ।
इस अगले चरण में, जहां चीजें थोड़ी भ्रमित हो सकती हैं। हमारी नई अभिव्यक्ति को देखते हुए, हम पहले से ही जानते हैं कि n क्या है। हालाँकि, हम अभी तक नहीं जानते हैं कि factorial(n - 1) है। सबसे पहले, n - 1 2 मूल्यांकन करता है। फिर, n लिए मान के रूप में 2 factorial लिए पारित कर दिया है। चूंकि यह एक नया फ़ंक्शन कॉल है, इसलिए इस नए n को संग्रहीत करने के लिए एक दूसरा वातावरण बनाया जाता है। बता दें कि A पहला पर्यावरण है और B दूसरा पर्यावरण है। एक अभी भी मौजूद है और {'n': 3} बराबर है, हालांकि, B (जो {'n': 2} बराबर है) वर्तमान परिवेश है। फ़ंक्शन बॉडी को देखते हुए, वापसी मान फिर से, n * factorial(n - 1) । इस अभिव्यक्ति का मूल्यांकन किए बिना, इसे मूल प्रतिफल अभिव्यक्ति में प्रतिस्थापित करते हैं। ऐसा करने से, हम मानसिक रूप से बी को त्याग रहे हैं, इसलिए n अनुसार विकल्प को याद रखें (यानी B के n संदर्भ को n - 1 साथ बदल दिया जाता है जो A के n का उपयोग करता है)। अब, मूल वापसी अभिव्यक्ति n * ((n - 1) * factorial((n - 1) - 1)) । यह सुनिश्चित करने के लिए एक सेकंड लें कि आप समझते हैं कि ऐसा क्यों है।
अब, आइए factorial((n - 1) - 1)) भाग का मूल्यांकन करें। A के n == 3 , हम 1 को factorial में पास कर रहे हैं। इसलिए, हम एक नया वातावरण C बना रहे हैं, जो {'n': 1} बराबर है। फिर से, वापसी मूल्य n * factorial(n - 1) । तो आइए "मूल" रिटर्न एक्सप्रेशन की तरह factorial((n - 1) - 1)) को बदल दें कि हमने पहले वाले ऑरिजिनल एक्सप्रेशन को कैसे समायोजित किया। "मूल" अभिव्यक्ति अब n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) ।
लगभग हो गया। अब, हमें factorial((n - 2) - 1) का मूल्यांकन करने की आवश्यकता है। इस बार, हम 0 गुजर रहे हैं। इसलिए, यह 1 मूल्यांकन करता है। अब, हम अपना अंतिम प्रतिस्थापन करते हैं। "मूल" वापसी अभिव्यक्ति अब n * ((n - 1) * ((n - 2) * 1)) । यह याद करते हुए कि मूल रिटर्न अभिव्यक्ति का मूल्यांकन ए के तहत किया जाता है, अभिव्यक्ति 3 * ((3 - 1) * ((3 - 2) * 1)) । यह, निश्चित रूप से, 6 का मूल्यांकन करता है। यह पुष्टि करने के लिए कि यह सही उत्तर है, उस 3! == 3 * 2 * 1 == 6 याद करें 3! == 3 * 2 * 1 == 6 । किसी भी आगे पढ़ने से पहले, सुनिश्चित करें कि आप पूरी तरह से वातावरण की अवधारणा को समझते हैं और कैसे वे पुनरावृत्ति पर लागू होते हैं।
if n == 0: return 1 कथन if n == 0: return 1 को आधार मामला कहा जाता है। इसका कारण यह है, यह कोई पुनरावृत्ति प्रदर्शित नहीं करता है। एक आधार मामला पूरी तरह से आवश्यक है। एक के बिना, आप अनंत पुनरावृत्ति में भाग लेंगे। इसके साथ ही कहा, जब तक आपके पास कम से कम एक आधार मामला है, आपके पास जितने चाहें उतने मामले हो सकते हैं। उदाहरण के लिए, हम समतुल्य रूप लिख सकता factorial इस प्रकार है:
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)
आपके पास कई बार पुनरावृत्ति के मामले भी हो सकते हैं, लेकिन हम इसमें शामिल नहीं होंगे क्योंकि यह अपेक्षाकृत असामान्य है और मानसिक रूप से प्रक्रिया के लिए अक्सर मुश्किल होता है।
आपके पास "समानांतर" पुनरावर्ती फ़ंक्शन कॉल भी हो सकते हैं। उदाहरण के लिए, फिबोनाची अनुक्रम पर विचार करें जो निम्नानुसार परिभाषित किया गया है:
- यदि संख्या 0 है, तो उत्तर 0 है।
- यदि संख्या 1 है, तो उत्तर 1 है।
- अन्यथा, उत्तर पिछले दो फाइबोनैचि संख्याओं का योग है।
हम इस प्रकार परिभाषित कर सकते हैं:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
मैं इस फ़ंक्शन के माध्यम से पूरी तरह से नहीं चलूंगा क्योंकि मैंने factorial(3) साथ किया था, लेकिन fib(5) का अंतिम रिटर्न मूल्य निम्नलिखित ( सिंटैक्टिकली अमान्य) अभिव्यक्ति के बराबर है:
(
fib((n - 2) - 2)
+
(
fib(((n - 2) - 1) - 2)
+
fib(((n - 2) - 1) - 1)
)
)
+
(
(
fib(((n - 1) - 2) - 2)
+
fib(((n - 1) - 2) - 1)
)
+
(
fib(((n - 1) - 1) - 2)
+
(
fib((((n - 1) - 1) - 1) - 2)
+
fib((((n - 1) - 1) - 1) - 1)
)
)
)
यह (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) जो बेशक 5 मूल्यांकन करता है।
अब, कुछ और शब्दावली शब्दों को शामिल करते हैं:
- एक टेल कॉल केवल एक पुनरावर्ती फ़ंक्शन कॉल है जो मान वापस करने से पहले किया जाने वाला अंतिम ऑपरेशन है। स्पष्ट होने के लिए,
return foo(n - 1)एक पूंछ कॉल है, लेकिनreturn foo(n - 1) + 1नहीं है (चूंकि जोड़ अंतिम ऑपरेशन है)। - टेल कॉल ऑप्टिमाइज़ेशन (TCO) पुनरावर्ती कार्यों में पुनरावृत्ति को स्वचालित रूप से कम करने का एक तरीका है।
- टेल कॉल एलिमिनेशन (TCE) एक एक्स कॉल की कमी है जो एक एक्सप्रेशन के बिना मूल्यांकन किया जा सकता है। TCE एक प्रकार का TCO है।
टेल कॉल ऑप्टिमाइज़ेशन कई कारणों से मददगार है:
- दुभाषिया वातावरण में व्याप्त स्मृति की मात्रा को कम कर सकता है। चूंकि किसी भी कंप्यूटर में असीमित मेमोरी नहीं है, इसलिए अत्यधिक पुनरावर्ती फ़ंक्शन कॉल से स्टैक ओवरफ़्लो हो जाएगा ।
- दुभाषिया स्टैक फ्रेम स्विच की संख्या को कम कर सकता है।
पायथन में कई कारणों से लागू TCO का कोई रूप नहीं है । इसलिए, इस सीमा को स्कर्ट करने के लिए अन्य तकनीकों की आवश्यकता होती है। पसंद का तरीका उपयोग के मामले पर निर्भर करता है। कुछ अंतर्ज्ञान के साथ, factorial और fib की परिभाषाओं को अपेक्षाकृत आसानी से पुनरावृत्त कोड में परिवर्तित किया जा सकता है:
def factorial(n):
product = 1
while n > 1:
product *= n
n -= 1
return product
def fib(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
यह आमतौर पर पुनरावृत्ति को मैन्युअल रूप से समाप्त करने का सबसे कुशल तरीका है, लेकिन यह अधिक जटिल कार्यों के लिए कठिन हो सकता है।
एक अन्य उपयोगी उपकरण पायथन का lru_cache डेकोरेटर है जिसका उपयोग अनावश्यक गणनाओं की संख्या को कम करने के लिए किया जा सकता है।
अब आपके पास एक विचार है कि पायथन में पुनरावृत्ति से कैसे बचा जाए, लेकिन आपको पुनरावृत्ति का उपयोग कब करना चाहिए ? जवाब "अक्सर नहीं" है। सभी पुनरावर्ती कार्यों को इसे लागू किया जा सकता है। यह केवल यह पता लगाने की बात है कि ऐसा कैसे किया जाए। हालांकि, ऐसे दुर्लभ मामले हैं जिनमें पुनरावृत्ति ठीक है। पायथन में पुनरावृत्ति आम है जब अपेक्षित इनपुट एक महत्वपूर्ण संख्या में पुनरावर्ती फ़ंक्शन कॉल का कारण नहीं होगा।
यदि पुनरावृत्ति एक ऐसा विषय है जिसमें आपकी रुचि है, तो मैं आपको योजना या हास्केल जैसी कार्यात्मक भाषाओं का अध्ययन करने के लिए बाध्य करता हूं। ऐसी भाषाओं में, पुनरावृत्ति अधिक उपयोगी है।
कृपया ध्यान दें कि फाइबोनैचि अनुक्रम के लिए उपरोक्त उदाहरण, हालांकि यह दिखाने में अच्छा है कि पाइथन में परिभाषा को कैसे लागू किया जाए और बाद में ल्रु कैश का उपयोग किया जाए, इसमें एक अक्षम समय होता है क्योंकि यह प्रत्येक गैर आधार मामले के लिए 2 पुनरावर्ती कॉल करता है। फ़ंक्शन के लिए कॉल की संख्या तेजी से n तक बढ़ जाती है।
बल्कि गैर-सहज रूप से एक अधिक कुशल कार्यान्वयन रैखिक पुनरावर्तन का उपयोग करेगा:
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)
लेकिन उस एक नंबर की जोड़ी को वापस करने का मुद्दा है। यह इस बात पर जोर देता है कि कुछ कार्य वास्तव में पुनरावृत्ति से अधिक लाभ नहीं लेते हैं।
पुनरावृत्ति के साथ पेड़ की खोज
कहें कि हमारे पास निम्नलिखित पेड़ हैं:
root
- A
- AA
- AB
- B
- BA
- BB
- BBA
अब, यदि हम तत्वों के सभी नामों को सूचीबद्ध करना चाहते हैं, तो हम इसे एक साधारण फॉर-लूप के साथ कर सकते हैं। हम मानते हैं कि एक फ़ंक्शन get_name() नोड के नाम की एक स्ट्रिंग वापस करने के लिए है, एक फ़ंक्शन get_children() ट्री में दिए गए नोड के सभी उप-नोड्स की एक सूची वापस करने के लिए, और एक फ़ंक्शन get_root() करने के लिए रूट नोड प्राप्त करें।
root = get_root(tree)
for node in get_children(root):
print(get_name(node))
for child in get_children(node):
print(get_name(child))
for grand_child in get_children(child):
print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA
यह अच्छी तरह से और तेजी से काम करता है, लेकिन क्या होगा अगर उप-नोड्स को अपने स्वयं के उप-नोड्स मिले? और उन उप-नोड्स में अधिक उप-नोड्स हो सकते हैं ... क्या होगा यदि आप पहले से नहीं जानते हैं कि कितने होंगे? इसे हल करने के लिए एक विधि पुनरावृत्ति का उपयोग है।
def list_tree_names(node):
for child in get_children(node):
print(get_name(child))
list_tree_names(node=child)
list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA
शायद आप प्रिंट नहीं करना चाहते हैं, लेकिन सभी नोड नामों की एक फ्लैट सूची वापस करें। यह एक रोलिंग सूची को एक पैरामीटर के रूप में पारित करके किया जा सकता है।
def list_tree_names(node, lst=[]):
for child in get_children(node):
lst.append(get_name(child))
list_tree_names(node=child, lst=lst)
return lst
list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']
अधिकतम पुनरावृत्ति गहराई बढ़ रही है
संभावित पुनरावृत्ति की गहराई की एक सीमा है, जो पायथन कार्यान्वयन पर निर्भर करता है। जब सीमा पूरी हो जाती है, तो RuntimeError अपवाद उठाया जाता है:
RuntimeError: Maximum Recursion Depth Exceeded
यहां एक कार्यक्रम का एक नमूना है जो इस त्रुटि का कारण होगा:
def cursing(depth):
try:
cursing(depth + 1) # actually, re-cursing
except RuntimeError as RE:
print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!
उपयोग करके पुनरावृत्ति की गहराई सीमा को बदलना संभव है
sys.setrecursionlimit(limit)
आप जाँच सकते हैं कि सीमा के वर्तमान पैरामीटर क्या चल रहे हैं:
sys.getrecursionlimit()
अपनी नई सीमा के साथ एक ही विधि ऊपर चल रही है
sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!
पायथन 3.5 से, अपवाद एक रिकर्सियन एरर है, जो रंटाइमइर्र से लिया गया है।
पूंछ पुनरावृत्ति - बुरा अभ्यास
जब किसी फ़ंक्शन से लौटी एकमात्र चीज़ एक पुनरावर्ती कॉल होती है, तो इसे पूंछ पुनरावृत्ति के रूप में संदर्भित किया जाता है।
यहाँ एक उदाहरण उलटी गिनती पूंछ पुनरावृत्ति का उपयोग करते हुए लिखा गया है:
def countdown(n):
if n == 0:
print "Blastoff!"
else:
print n
countdown(n-1)
पुनरावृत्ति का उपयोग करके बनाई जाने वाली कोई भी गणना पुनरावृत्ति का उपयोग करके भी बनाई जा सकती है। यहाँ पूंछ पुनरावृत्ति का उपयोग करते हुए find_max का एक संस्करण लिखा गया है:
def find_max(seq, max_so_far):
if not seq:
return max_so_far
if max_so_far < seq[0]:
return find_max(seq[1:], seq[0])
else:
return find_max(seq[1:], max_so_far)
पाइथन में पूंछ की पुनरावृत्ति को एक बुरा अभ्यास माना जाता है, क्योंकि पायथन संकलक पूंछ पुनरावर्ती कॉल के लिए अनुकूलन को नहीं संभालता है। इस तरह के मामलों में पुनरावर्ती समाधान समकक्ष पुनरावृत्ति समाधान की तुलना में अधिक प्रणाली संसाधनों का उपयोग करते हैं।
स्टैक आत्मनिरीक्षण के माध्यम से पूंछ पुनरावृत्ति अनुकूलन
डिफ़ॉल्ट रूप से पायथन की पुनरावृत्ति स्टैक 1000 फ्रेम से अधिक नहीं हो सकती है। यह sys.setrecursionlimit(15000) को सेट करके बदला जा सकता है जो कि तेज है, लेकिन यह विधि अधिक मेमोरी खाती है। इसके बजाय, हम स्टैक आत्मनिरीक्षण का उपयोग करके टेल रिकर्सन समस्या को भी हल कर सकते हैं।
#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
This function fails if the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
पुनरावर्ती कार्यों को अनुकूलित करने के लिए, हम अपने फ़ंक्शन को कॉल करने के लिए @tail_call_optimized डेकोरेटर का उपयोग कर सकते हैं। ऊपर वर्णित डेकोरेटर का उपयोग करते हुए कुछ सामान्य पुनरावर्तन उदाहरण दिए गए हैं:
तथ्य का उदाहरण:
@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
फाइबोनैचि उदाहरण:
@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.