पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण
हर कॉल का अनुसरण किए बिना factorial, power और sum-of-digits के सही पुनरावर्ती समाधान लिखने के लिए तीन-चरणीय विधि अपनाइए।
पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
पुनरावर्तन कठिन क्यों लगता है
अधिकांश शुरुआती लोग हर पुनरावर्ती आह्वान को मन में ट्रेस करने की कोशिश करते हैं, जो पाँच स्तर तक गहरे पुनरावर्तन के लिए भी जल्दी ही भारी लगने लगता है। पेशेवर तरीका तीन-चरणीय ढाँचे — आधार-स्थिति, भरोसा और निर्माण — का उपयोग करना है। इससे आप पूरे आह्वान-वृक्ष का मानसिक अनुकरण किए बिना सही पुनरावर्ती फ़ंक्शन लिख सकते हैं।
इस ढाँचे को कभी-कभी विश्वास की छलाँग भी कहा जाता है: आप भरोसा करते हैं कि आपका फ़ंक्शन छोटे इनपुट मानों पर काम करता है और इस मान्यता का उपयोग बड़े इनपुट मानों के लिए समाधान बनाने में करते हैं।
चरण 1: आधार स्थिति परिभाषित करें
आधार स्थिति वह सबसे सरल प्रवेश मान है जिसका उत्तर आगे पुनरावर्तन किए बिना ज्ञात होता है। प्रत्येक पुनरावर्ती फ़ंक्शन में कम-से-कम एक आधार स्थिति होनी चाहिए; इसके बिना फ़ंक्शन अनंत तक पुनरावर्तित होता रहेगा (स्टैक अतिप्रवाह)। अच्छी आधार स्थितियाँ हैं: खाली सूची, एकल तत्व, n == 0, n == 1, या समस्या किसी तुच्छ सर्वसमिका तक सिमट जाए।
किसी भी पुनरावर्ती तर्क से पहले आधार स्थिति लिखें। इसे इस प्रश्न से पहचानें: 'इस समस्या का सबसे छोटा रूप कौन-सा है जिसका उत्तर मैं तुरंत दे सकता हूँ?'
# Base cases for common problems
def factorial(n):
if n == 0: # base case: 0! = 1
return 1
# ... recursive step below
def sum_list(lst):
if not lst: # base case: sum of empty list is 0
return 0
# ...
def height(node):
if node is None: # base case: height of null node is 0
return 0
# ...
print('Base cases identified')चरण 2: पुनरावर्ती कॉल पर भरोसा रखें
भरोसे का चरण विश्वास की छलाँग है: मान लें कि आपका फ़ंक्शन वर्तमान प्रवेश मान से वास्तव में छोटे किसी भी प्रवेश मान के लिए पहले से सही ढंग से काम करता है। आपको अभी प्रत्येक छोटे प्रवेश मान के लिए इसे सिद्ध करने की आवश्यकता नहीं है — आगमनात्मक प्रमाण इसकी गारंटी देता है। बस छोटे उप-समस्या पर अपने फ़ंक्शन को कॉल करें और भरोसा रखें कि वह सही परिणाम लौटाएगा।
शुरुआती सीखने वाले अक्सर इस चरण को छोड़कर इसके बजाय सब कुछ मन-ही-मन चलाने की कोशिश करते हैं। इस आग्रह का विरोध करें; एक बार इस ढाँचे को अच्छी तरह समझ लेने पर यह मनमानी गहराई वाले पुनरावर्तन तक प्रभावी रहता है।
# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11 (we TRUST this, don't trace it)
# Build: 3 + 11 = 14
# So:
def sum_list(lst):
if not lst:
return 0
# Trust that sum_list(lst[1:]) returns sum of the rest
return lst[0] + sum_list(lst[1:])
print(sum_list([3, 1, 4, 1, 5])) # 14चरण 3: समाधान तैयार करें
निर्माण चरण भरोसेमंद उप-समस्या के परिणाम को वर्तमान तत्व के योगदान के साथ मिलाकर पूरे प्रवेश मान का उत्तर तैयार करता है। यह आम तौर पर एक ही पंक्ति होती है: वर्तमान तत्व और पुनरावर्ती कॉल के परिणाम पर कोई क्रिया लागू करना। सामान्य निर्माण इस प्रकार हैं: योग में जोड़ना, सूची के आरंभ में जोड़ना, गिनती बढ़ाना, या दो उप-परिणामों को मिलाना।
def factorial(n):
if n == 0:
return 1
# Trust: factorial(n-1) gives (n-1)!
# Build: n * (n-1)! = n!
return n * factorial(n - 1)
def power(base, exp):
if exp == 0:
return 1
# Trust: power(base, exp-1) gives base^(exp-1)
# Build: base * base^(exp-1) = base^exp
return base * power(base, exp - 1)
print(factorial(6)) # 720
print(power(2, 10)) # 1024अंकों के योग पर रूपरेखा लागू करना
समस्या: किसी गैर-ऋणात्मक पूर्णांक के अंकों का योग निकालना। आधार स्थिति: n == 0 → योग 0 है (या n < 10 → n स्वयं)। भरोसा: sumDigits(n // 10) अंतिम अंक को छोड़कर बाकी सभी अंकों का योग लौटाता है। निर्माण: अंतिम अंक n % 10 को भरोसेमंद परिणाम में जोड़ें। यह रूपरेखा तीन घोषणात्मक चरणों में समाधान तैयार करती है।
def sumDigits(n):
if n < 10:
return n # base case: single digit
# Trust: sumDigits(n // 10) gives sum of all digits except last
# Build: add the last digit
return n % 10 + sumDigits(n // 10)
print(sumDigits(0)) # 0
print(sumDigits(7)) # 7
print(sumDigits(123)) # 6
print(sumDigits(9999)) # 36फ़िबोनाची: दो उप-समस्याएँ
फ़िबोनाची के लिए दो पुनरावर्ती कॉल आवश्यक हैं: fib(n-1) और fib(n-2)। रूपरेखा लागू करें: आधार स्थितियाँ fib(0) = 0 और fib(1) = 1 हैं। भरोसा: दोनों छोटी कॉल सही फ़िबोनाची मान लौटाती हैं। निर्माण: उनके योग को लौटाएँ। यह सरल कार्यान्वयन O(2^n) है — हम मेमोइज़ेशन वाले पाठ में इसे सुधारेंगे।
def fib(n):
if n <= 1:
return n # base cases: fib(0)=0, fib(1)=1
# Trust both smaller sub-problems
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f'fib({i}) = {fib(i)}') # 0,1,1,2,3,5,8,13पुनरावर्तन से स्ट्रिंग उलटना
समस्या: किसी स्ट्रिंग को पुनरावर्तन से उलटना। आधार स्थिति: खाली स्ट्रिंग या एकल वर्ण — वह पहले से उलटी हुई है। भरोसा: reverse(s[1:]) पहले वर्ण के बाद के सभी वर्णों का उलटा हुआ रूप लौटाता है। निर्माण: पहले वर्ण को उलटे हुए शेष भाग के अंत में जोड़ें। इस रूपरेखा से तीन पंक्तियों का समाधान मिलता है।
def reverse_str(s):
if len(s) <= 1:
return s # base case
# Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
# Build: append first character at end
return reverse_str(s[1:]) + s[0]
print(reverse_str('')) # ''
print(reverse_str('a')) # 'a'
print(reverse_str('hello')) # 'olleh'
print(reverse_str('racecar')) # 'racecar'पुनरावर्तन से आवृत्तियों की गिनती
समस्या: किसी सूची में लक्ष्य मान की आवृत्तियों की गिनती पुनरावर्तन से करना। आधार स्थिति: खाली सूची — गिनती 0 है। भरोसा: count(lst[1:], target) शेष भाग में गिनती लौटाता है। निर्माण: यदि पहला तत्व लक्ष्य से मेल खाता है तो 1 जोड़ें, अन्यथा 0 जोड़ें। सूची का आकार 1 घटाकर प्रत्येक पुनरावर्ती चरण आधार स्थिति की दिशा में आगे बढ़ता है।
def count_occurrences(lst, target):
if not lst:
return 0
# Trust: count in rest of list is handled recursively
# Build: add 1 if first element matches, else 0
return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)
print(count_occurrences([1, 2, 3, 2, 4, 2], 2)) # 3
print(count_occurrences([], 5)) # 0
print(count_occurrences([7, 7, 7], 7)) # 3जाँचें कि सूची क्रमबद्ध है
समस्या: यह जाँचना कि कोई सूची पुनरावर्तन से आरोही क्रम में क्रमबद्ध है या नहीं। आधार स्थिति: 0 या 1 तत्वों वाली सूची हमेशा क्रमबद्ध होती है। भरोसा: is_sorted(lst[1:]) बताता है कि शेष भाग क्रमबद्ध है या नहीं। निर्माण: सूची तब क्रमबद्ध है जब पहला तत्व <= दूसरा तत्व हो AND शेष भाग क्रमबद्ध हो। यह एक स्पष्ट उदाहरण है जिसमें निर्माण चरण दो शर्तों के तार्किक AND का उपयोग करता है।
def is_sorted(lst):
if len(lst) <= 1:
return True
# Trust: is_sorted(lst[1:]) tells us if tail is sorted
# Build: head <= second element AND tail is sorted
return lst[0] <= lst[1] and is_sorted(lst[1:])
print(is_sorted([])) # True
print(is_sorted([1])) # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # Falseपुनरावर्तन से द्विआधारी खोज (पुनरावलोकन)
रूपरेखा के माध्यम से पुनरावर्तन में व्यक्त द्विआधारी खोज: आधार स्थिति: lo > hi → मान नहीं मिला (−1 लौटाएँ)। भरोसा: सही आधे हिस्से पर की गई पुनरावर्ती कॉल लक्ष्य ढूँढती है या −1 लौटाती है। निर्माण: मध्य मान निकालें, तुलना करें और उपयुक्त आधे हिस्से को कॉल करें। पुनरावर्ती रूप विभाजन-और-विजय संरचना को स्पष्ट रूप से दिखाता है, हालाँकि उत्पादन में O(1) स्थान के लिए पुनरावृत्तिमूलक रूप को प्राथमिकता दी जाती है।
def binary_search(arr, target, lo, hi):
if lo > hi: # base case: search space exhausted
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# Trust both halves return correct results
if arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 3
print(binary_search(arr, 4, 0, len(arr) - 1)) # -1पुनरावर्तन बनाम पुनरावृत्ति का उपयोग कब करें
पुनरावर्तन तब उत्कृष्ट होता है जब समस्या स्वाभाविक रूप से उसी प्रकार की छोटी उप-समस्याओं में विभाजित हो जाती है (वृक्ष, विभाजन-और-विजय, पीछे लौटकर खोजना)। पुनरावृत्ति को प्राथमिकता दें जब: पुनरावर्तन की गहराई अधिक हो (पायथन में स्टैक अतिप्रवाह का जोखिम, जिसकी डिफ़ॉल्ट सीमा लगभग 1000 है), पुनरावर्ती और पुनरावृत्तिमूलक रूप समान रूप से स्पष्ट हों, या समस्या एक सरल चक्र हो (factorial, मेमोइज़ेशन के बिना फ़िबोनाची)।
एक अच्छा सामान्य नियम है: यदि पुनरावर्तन वृक्ष बनाना स्वाभाविक लगे, तो पुनरावर्तन का उपयोग करें। यदि वृक्ष सीधी रेखा जैसा हो (अंतिम-कॉल पुनरावर्तन), तो उसे पुनरावृत्ति में बदल दें।
import sys
# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit()) # 1000
# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
total = 0
for x in lst:
total += x
return total
big = list(range(2000))
print(sum_list_iter(big)) # 1999000 — no stack overflowत्वरित जाँच
इस पाठ में सिखाई गई डेटा संरचनाओं और एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी — संबंधी अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: तीन-चरणीय रूपरेखा है आधार स्थिति (सबसे सरल ज्ञात उत्तर), भरोसा (मान लें कि उप-समस्या हल है), और निर्माण (वर्तमान तत्व को भरोसेमंद परिणाम के साथ मिलाना), पहले आधार स्थितियाँ लिखें और पूरे कॉल-वृक्ष को मन-ही-मन ट्रेस करने से बचें, और जब पुनरावर्तन की गहराई से स्टैक अतिप्रवाह का जोखिम हो या पुनरावर्ती और पुनरावृत्तिमूलक रूप समान रूप से स्पष्ट हों, तब पुनरावृत्ति का उपयोग करें। आगे हम कॉल स्टैक को विस्तार से दृश्य रूप में देखेंगे।
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण” पाठ निःशुल्क है?
हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण” में मैं क्या सीखूँगा?
हर कॉल का अनुसरण किए बिना factorial, power और sum-of-digits के सही पुनरावर्ती समाधान लिखने के लिए तीन-चरणीय विधि अपनाइए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ DSA Interview Prep का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- पुनरावृत्ति ढाँचा: आधार स्थिति, भरोसा, निर्माण
- कॉल स्टैक का दृश्यांकन
- पुनरावर्ती बनाम पुनरावृत्तीय संतुलन
- Memoisation: पुनरावर्ती परिणामों का कैशिंग