🔬
🧬
🔭
🪐
🧪
← डैशबोर्ड पर वापस जाएँ
Font Size:

1. परिचय

रिकर्शन (Recursion) वह प्रक्रिया है जिसमें कोई फलन स्वयं को ही कॉल करता है। यह किसी बड़ी समस्या को छोटी, समान प्रकार की उप-समस्याओं में विभाजित करके हल करने की तकनीक है। रिकर्शन में फलन का प्रत्येक कॉल सिस्टम स्टैक में संग्रहीत होता है, और अंतिम कॉल से लौटने पर पिछले कॉल आगे बढ़ते हैं।

रिकर्सिव फलन के दो आवश्यक भाग होते हैं: 1. आधार स्थिति (Base Case): वह स्थिति जिस पर फलन स्वयं को कॉल करना बंद कर देता है। 2. रिकर्सिव स्थिति (Recursive Case): वह स्थिति जिसमें फलन स्वयं को कॉल करता है।

यदि आधार स्थिति नहीं होगी तो फलन अनंत बार कॉल होता रहेगा और स्टैक ओवरफ्लो (Stack Overflow) हो जाएगा।

2. रिकर्सिव फलन की संरचना

def recursive_function(parameter):
    if base_condition:      # आधार स्थिति
        return base_value
    else:
        # रिकर्सिव कॉल
        return recursive_function(modified_parameter)

उदाहरण: फैक्टोरियल (Factorial)

n का फैक्टोरियल: n! = n × (n-1) × (n-2) × ... × 1, जिसमें 0! = 1

def factorial(n):
    if n == 0:          # आधार स्थिति
        return 1
    else:
        return n * factorial(n - 1)   # रिकर्सिव कॉल

print(factorial(5))   # 120

factorial(4) की कार्यविधि:

factorial(4) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1 * factorial(0)
             = 4 * 3 * 2 * 1 * 1
             = 24

3. रिकर्सिव फलन के उदाहरण

3.1 फिबोनाची श्रृंखला (Fibonacci Series)

फिबोनाची श्रृंखला में प्रत्येक पद पिछले दो पदों का योग होता है: 0, 1, 1, 2, 3, 5, 8, ...

def fibonacci(n):
    if n <= 1:           # आधार स्थिति
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(7):
    print(fibonacci(i), end=" ")   # 0 1 1 2 3 5 8

3.2 प्राकृतिक संख्याओं का योग (Sum of Natural Numbers)

def sum_natural(n):
    if n == 1:           # आधार स्थिति
        return 1
    else:
        return n + sum_natural(n - 1)

print(sum_natural(5))   # 15

3.3 घातांक की गणना

def power(base, exp):
    if exp == 0:         # आधार स्थिति
        return 1
    else:
        return base * power(base, exp - 1)

print(power(2, 5))   # 32

3.4 सूची में अधिकतम तत्व खोजना

def find_max(lst):
    if len(lst) == 1:    # आधार स्थिति
        return lst[0]
    else:
        rest = find_max(lst[1:])
        return lst[0] if lst[0] > rest else rest

print(find_max([4, 9, 2, 7]))   # 9

4. रिकर्शन कैसे कार्य करता है (How Recursion Works)

रिकर्सिव फलन कॉल की प्रक्रिया स्टैक पर आधारित होती है:

  1. प्रत्येक फलन कॉल सिस्टम स्टैक में एक नया एक्टिवेशन रिकॉर्ड बनाता है।
  2. आधार स्थिति तक पहुँचने पर फलन मान लौटाता है।
  3. स्टैक से प्रत्येक कॉल एक-एक कर हटता है और पिछला कॉल अपनी गणना पूरी करता है।
def count_down(n):
    if n == 0:                       # आधार स्थिति
        print("समाप्त!")
    else:
        print(n)
        count_down(n - 1)            # रिकर्सिव कॉल

count_down(3)
# आउटपुट: 3, 2, 1, समाप्त!

5. रिकर्सन बनाम इटरेशन (Recursion vs Iteration)

विशेषता रिकर्शन इटरेशन
परिभाषा फलन स्वयं को कॉल करता है लूप का उपयोग
कोड छोटा, संक्षिप्त अपेक्षाकृत लंबा
मेमोरी स्टैक में प्रत्येक कॉल केवल चर
गति धीमी (कॉल ओवरहेड) तेज़
स्टैक ओवरफ्लो संभव नहीं
उपयोग विभाजित-और-जीत समस्याएँ सरल पुनरावृत्ति

6. रिकर्शन के अनुप्रयोग (Applications of Recursion)

  1. फैक्टोरियल और फिबोनाची: गणितीय परिभाषाओं का सीधा कार्यान्वयन।
  2. ट्री/ग्राफ की यात्रा: ट्री का preorder, inorder, postorder traversal।
  3. बाइनरी सर्च: रिकर्सिव रूप में बाइनरी सर्च सरल होती है।
  4. टावर ऑफ हनोई: क्लासिक रिकर्सिव समस्या।
  5. समस्या विभाजन (Divide and Conquer): मर्ज सॉर्ट, क्विक सॉर्ट जैसे एल्गोरिथ्म।
  6. परम्यूटेशन/कॉम्बिनेशन: सभी संभव व्यवस्थाएँ उत्पन्न करना।

7. टावर ऑफ हनोई (Tower of Hanoi)

टावर ऑफ हनोई रिकर्शन की एक प्रसिद्ध समस्या है। इसमें तीन खूँटे (rods) होते हैं और पहले खूँटे पर आकार के अवरोही क्रम में रखी डिस्कें होती हैं। कार्य है सभी डिस्कों को नियमों के अनुसार तीसरे खूँटे पर ले जाना:

  1. एक समय में केवल एक डिस्क हटाई जा सकती है।
  2. बड़ी डिस्क को छोटी डिस्क के ऊपर नहीं रखा जा सकता।
  3. केवल ऊपर की डिस्क ही हटाई जा सकती है।
def tower_of_hanoi(n, source, helper, target):
    if n == 1:                        # आधार स्थिति
        print(source, "से", target, "ले जाएँ")
        return
    tower_of_hanoi(n - 1, source, target, helper)
    print(source, "से", target, "ले जाएँ")
    tower_of_hanoi(n - 1, helper, source, target)

tower_of_hanoi(3, 'A', 'B', 'C')

n डिस्कों के लिए आवश्यक चालों की संख्या 2^n - 1 होती है। अतः 3 डिस्कों के लिए 7 चालें, 4 के लिए 15 चालें। यह समस्या स्पष्ट रूप से दिखाती है कि रिकर्शन जटिल समस्याओं को छोटे, समान प्रकार के चरणों में कैसे विभाजित करता है।

8. रिकर्शन के लाभ और सीमाएँ (Advantages and Limitations)

लाभ:

  1. कोड संक्षिप्त और स्पष्ट होता है।
  2. गणितीय परिभाषाओं का सीधा कार्यान्वयन होता है।
  3. ट्री/ग्राफ जैसी संरचनाओं में स्वाभाविक रूप से उपयुक्त है।
  4. विभाजित-और-जीत एल्गोरिथ्मों की नींव है।

सीमाएँ:

  1. प्रत्येक कॉल स्टैक मेमोरी उपयोग करता है, जिससे मेमोरी खपत अधिक होती है।
  2. बिना आधार स्थिति के स्टैक ओवरफ्लो होता है।
  3. फलन कॉल का अतिरिक्त व्यय (overhead) होता है, जिससे गति धीमी होती है।
  4. फिबोनाची जैसी समस्याओं में बार-बार समान गणना होती है, जो अकुशल है।

सरल गिनती जैसी समस्याओं में लूप (इटरेशन) अधिक उपयुक्त होता है, जबकि ट्री ट्रैवर्सल जैसी समस्याओं में रिकर्शन स्वाभाविक है। परीक्षा में पूछे जाने पर रिकर्शन और इटरेशन की तुलना लाभ-सीमाओं के साथ लिखना चाहिए।

9. रिकर्सिव समस्याओं को हल करने की विधि

रिकर्सिव फलन लिखते समय निम्नलिखित चरणों का पालन करें:

  1. आधार स्थिति पहचानें: वह सरलतम स्थिति जिसका उत्तर सीधे ज्ञात हो।
  2. रिकर्सिव संबंध स्थापित करें: बड़ी समस्या को छोटी समस्या से जोड़ें।
  3. पैरामीटर परिवर्तन करें: प्रत्येक कॉल में समस्या का आकार घटाएँ।
  4. स्टैक परिणाम का उपयोग करें: रिकर्सिव कॉल के लौटाए मान को गणना में जोड़ें।

उदाहरण के लिए, प्राकृतिक संख्याओं के योग में आधार स्थिति n == 1 है (योग 1), और रिकर्सिव संबंध sum(n) = n + sum(n-1) है। इसी प्रकार प्रत्येक रिकर्सिव समस्या को इन चार चरणों में हल किया जा सकता है। अभ्यास से रिकर्सिव सोच विकसित होती है जो कंप्यूटर विज्ञान के अनेक क्षेत्रों में उपयोगी है।

त्वरित पुनरावृत्ति तालिकाएँ

रिकर्सिव फलनों का सारांश

फलन आधार स्थिति रिकर्सिव संबंध
फैक्टोरियल n == 0 → 1 n! = n × (n-1)!
फिबोनाची n <= 1 → n f(n) = f(n-1) + f(n-2)
प्राकृतिक योग n == 1 → 1 sum(n) = n + sum(n-1)
घातांक exp == 0 → 1 b^e = b × b^(e-1)

रिकर्सिव फलन के घटक

घटक कार्य
आधार स्थिति रिकर्शन रोकना
रिकर्सिव कॉल स्वयं को बुलाना
पैरामीटर परिवर्तन प्रत्येक कॉल में स्थिति बदलना
स्टैक कॉल का प्रबंधन

माइंड मैप

flowchart TD A["रिकर्शन"] --> B["घटक"] A --> C["उदाहरण"] A --> D["कार्य प्रक्रिया"] A --> E["अनुप्रयोग"] B --> B1["आधार स्थिति"] B --> B2["रिकर्सिव कॉल"] C --> C1["फैक्टोरियल"] C --> C2["फिबोनाची"] C --> C3["प्राकृतिक योग"] C --> C4["घातांक"] D --> D1["स्टैक पर आधारित"] D --> D2["लौटने का क्रम"] E --> E1["ट्री ट्रैवर्सल"] E --> E2["बाइनरी सर्च"] E --> E3["मर्ज/क्विक सॉर्ट"]

महत्वपूर्ण आरेख (SVG)

आरेख 1: फैक्टोरियल की रिकर्सिव कार्यविधि

factorial(4) की कार्यविधि factorial(4) factorial(3) factorial(2) factorial(1) factorial(0) आधार स्थिति पर 1 लौटता है, फिर पीछे की ओर गुणा: 4! = 4 × 3 × 2 × 1 × 1 = 24 स्वर्ण नियम: आधार स्थिति के बिना अनंत रिकर्शन

आरेख 2: फिबोनाची श्रृंखला

fibonacci(5) f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(5) = f(4) + f(3) = 3 + 2 = 5 श्रृंखला: 0 1 1 2 3 5 स्वर्ण नियम: प्रत्येक पद पिछले दो पदों का योग

सामान्य गलतियाँ

  1. आधार स्थिति न लिखना: आधार स्थिति के बिना फलन अनंत बार कॉल होता है, जिससे स्टैक ओवरफ्लो (RecursionError) होता है।
  2. गलत आधार स्थिति: गलत आधार मान (जैसे factorial में n==1 के बजाय n==0) गलत परिणाम दे सकता है।
  3. पैरामीटर में कमी न करना: रिकर्सिव कॉल में पैरामीटर का मान आधार स्थिति की ओर नहीं बढ़ना चाहिए, अन्यथा अनंत लूप होता है।
  4. लौटने के क्रम को भूलना: रिकर्सिव कॉल के परिणाम का उपयोग (जैसे n * factorial(n-1)) करना आवश्यक है; केवल कॉल करना पर्याप्त नहीं।
  5. फिबोनाची में अति-दोहराव: fibonacci(n-1) + fibonacci(n-2) में समान गणना बार-बार होती है, जिससे प्रदर्शन धीमा होता है।
  6. रिकर्शन बनाम लूप में गलत चुनाव: सरल समस्याओं में लूप अधिक कुशल है; रिकर्शन का अनावश्यक उपयोग मेमोरी खर्च बढ़ाता है।

परीक्षा युक्तियाँ

  1. रिकर्सिव फलन का आउटपुट लिखने के लिए प्रत्येक कॉल की गणना को चरणबद्ध (step-by-step) लिखें।
  2. आधार स्थिति की पहचान हमेशा पहले करें - यही रिकर्शन को रोकती है।
  3. फैक्टोरियल, फिबोनाची और योग के रिकर्सिव कोड शब्दशः लिखने का अभ्यास करें।
  4. रिकर्शन और इटरेशन के अंतर की तालिका तैयार रखें।
  5. दिए गए कोड में रिकर्सिव कॉल की संख्या गिनने के प्रश्न हल करें।
  6. रिकर्सन के अनुप्रयोगों (ट्री ट्रैवर्सल, बाइनरी सर्च, मर्ज सॉर्ट) के नाम याद रखें।

निष्कर्ष

रिकर्शन एक शक्तिशाली तकनीक है जिसमें फलन स्वयं को कॉल करता है। आधार स्थिति रिकर्शन को रोकती है, जबकि रिकर्सिव कॉल समस्या को छोटे भागों में विभाजित करती है। फैक्टोरियल, फिबोनाची, प्राकृतिक योग और घातांक रिकर्शन के उत्कृष्ट उदाहरण हैं। रिकर्शन स्टैक पर आधारित होता है, इसलिए आधार स्थिति के बिना स्टैक ओवरफ्लो होता है। ट्री ट्रैवर्सल, बाइनरी सर्च और सॉर्टिंग एल्गोरिथ्मों में रिकर्शन का महत्वपूर्ण योगदान है। सरल समस्याओं में लूप अधिक कुशल होता है, परंतु कई जटिल समस्याओं के लिए रिकर्शन स्वाभाविक और संक्षिप्त हल प्रदान करता है।