C भाषा में रिकर्सिव फंक्शन को प्रोग्राम के साथ समझाएं

रिकर्सिव फंक्शन्स किसी चीज को स्वयं के संदर्भ में परिभाषित करने की प्रक्रिया है। यह एक फंक्शन है जो अपने बॉडी में स्वयं को फिर से कॉल करता है।

एक फंक्शन fact(), जो पूर्णांक 'N' का फैक्टोरियल गणना करता है, जो 1 से N तक सभी पूर्णांकों का गुणनफल है।

जब fact() को 1 (या 0) आर्गुमेंट के साथ कॉल किया जाता है, तो फंक्शन 1 लौटाता है। अन्यथा, यह n * fact(n-1) का गुणनफल लौटाता है, यह तब तक होता है जब तक 'n' 1 के बराबर नहीं हो जाता।

Fact(5) = 5 * fact(4)
        = 5 * 4 * fact(3)
        = 5 * 4 * 3 * fact(2)
        = 5 * 4 * 3 * 2 * fact(1)
        = 5 * 4 * 3 * 2 * 1
        = 120

उदाहरण प्रोग्राम

#include <stdio.h> 

int fact(int n);  // प्रोटोटाइप

int main() {
    int n, f;
    printf("Enter a number: ");
    scanf("%d", &n);
    f = fact(n);
    printf("Factorial value = %d", f);
    return 0;
}

int fact(int n) {
    if(n == 1 || n == 0)
        return 1;
    else
        return n * fact(n - 1);
}

आउटपुट

Enter a number: 5
Factorial value = 120

रिकर्सन के घटक

1. बेस केस (Base Case): रिकर्सन रोकने की शर्त (उदाहरण: n <= 1)।
2. रिकर्सिव केस (Recursive Case): समस्या को छोटे उपसमस्या में तोड़ना (n * fact(n-1))।
3. प्रगति: प्रत्येक कॉल बेस केस की ओर बढ़नी चाहिए।

अन्य रिकर्सन उदाहरण

1. फिबोनाची श्रृंखला

int fib(int n) {
    if(n <= 1) return n;
    return fib(n-1) + fib(n-2);
}
// नोट: घातीय समय जटिलता, मेमोइजेशन के साथ O(n) संभव

2. टावर ऑफ हनोई

void hanoi(int n, char from, char to, char aux) {
    if(n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n-1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n-1, aux, to, from);
}

3. बाइनरी सर्च (रिकर्सिव)

int binarySearch(int arr[], int low, int high, int target) {
    if(low > high) return -1;
    int mid = low + (high - low) / 2;
    if(arr[mid] == target) return mid;
    if(arr[mid] > target) return binarySearch(arr, low, mid-1, target);
    return binarySearch(arr, mid+1, high, target);
}

रिकर्सन vs इटरेशन

टेल रिकर्सन ऑप्टिमाइजेशन

कुछ कंपाइलर्स (GCC -O2/-O3) टेल रिकर्सन को इटरेशन में ऑप्टिमाइज़ करते हैं:

// टेल रिकर्सिव (ऑप्टिमाइज़ेबल)
int factTail(int n, int acc) {
    if(n <= 1) return acc;
    return factTail(n-1, n*acc);
}
// कॉल: factTail(5, 1)

सर्वोत्तम अभ्यास

• हमेशा बेस केस परिभाषित करें।
• सुनिश्चित करें कि रिकर्सन बेस केस की ओर प्रगति करता है।
• गहरी रिकर्सन के लिए इटरेटिव विकल्प पर विचार करें।
• ओवरलैपिंग सबप्रॉब्लम्स के लिए मेमोइजेशन/डायनामिक प्रोग्रामिंग उपयोग करें।