Java Language
प्रत्यावर्तन

परिचय

टिप्पणियों

पुनरावृत्ति का मूल विचार

पुनरावर्तन क्या है:

सामान्य तौर पर, पुनरावृत्ति तब होती है जब कोई फ़ंक्शन खुद को प्रत्यक्ष या अप्रत्यक्ष रूप से आमंत्रित करता है। उदाहरण के लिए:

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

किसी समस्या के लिए पुनरावर्तन लागू करने के लिए शर्तें:

एक विशेष समस्या को हल करने के लिए पुनरावर्ती कार्यों का उपयोग करने के लिए दो पूर्व शर्त हैं:

1. समस्या के लिए एक आधार स्थिति होनी चाहिए, जो पुनरावृत्ति के लिए समापन बिंदु होगी। जब एक पुनरावर्ती फ़ंक्शन आधार स्थिति तक पहुंचता है, तो यह आगे (गहरी) पुनरावर्ती कॉल नहीं करता है।

2. प्रत्येक स्तर की पुनरावृत्ति एक छोटी सी समस्या का प्रयास करना चाहिए। पुनरावर्ती कार्य इस प्रकार समस्या को छोटे और छोटे भागों में विभाजित करता है। यह मानते हुए कि समस्या परिमित है, यह सुनिश्चित करेगा कि पुनरावृत्ति समाप्त हो जाए।

जावा में एक तीसरा पूर्व शर्त है: समस्या को हल करने के लिए बहुत गहराई से पुनरावृत्ति करना आवश्यक नहीं होना चाहिए; देखें जावा में गहरी पुनरावृत्ति समस्याग्रस्त है

उदाहरण

निम्नलिखित फ़ंक्शन पुनरावृत्ति का उपयोग करके फैक्टोरियल की गणना करता है। ध्यान दें कि विधि factorial कैसे फ़ंक्शन के भीतर कॉल करता है। हर बार जब वह स्वयं कॉल करता है, तो यह पैरामीटर n को 1. से कम कर देता है। जब n 1 तक पहुंचता है (आधार स्थिति) तो फ़ंक्शन कोई गहरा पुनरावृत्ति नहीं करेगा।

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{यह जावा में फैक्टरिंग की गणना का एक व्यावहारिक तरीका नहीं है, क्योंकि यह n बड़े मूल्यों के लिए पूर्णांक अतिप्रवाह, या कॉल स्टैक ओवरफ़्लो (यानी StackOverflowError अपवाद) को नहीं लेता है।}

Nth फाइबोनैचि संख्या की गणना करना

निम्नलिखित विधि पुनरावर्तन का उपयोग करते हुए Nth फाइबोनैचि संख्या की गणना करती है।

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

विधि एक बेस केस (एन <= 2) को लागू करती है और एक पुनरावर्ती मामला (एन> 2)। यह पुनरावर्ती संबंध की गणना करने के लिए पुनरावर्तन के उपयोग का चित्रण करता है।

हालांकि, जबकि यह उदाहरण निदर्शी है, यह भी अक्षम है: विधि का प्रत्येक एकल उदाहरण दो बार फ़ंक्शन को खुद ही कॉल करेगा, जिससे फ़ंक्शन की संख्या में तेजी से वृद्धि होती है, जिसे एन वृद्धि कहा जाता है। उपरोक्त फ़ंक्शन O (2 ^N ) है, लेकिन एक समतुल्य पुनरावृत्ति समाधान में जटिलता O (N) है। इसके अलावा, एक "बंद रूप" अभिव्यक्ति है जिसका मूल्यांकन ओ (एन) फ्लोटिंग-पॉइंट गुणा में किया जा सकता है।

1 से एन तक पूर्णांकों का योग गणना

निम्नलिखित विधि पुनरावर्तन का उपयोग करके 0 से N तक पूर्णांकों की राशि की गणना करती है।

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

यह विधि O (N) है और इसे टेल-कॉल ऑप्टिमाइज़ेशन का उपयोग करके एक साधारण लूप में घटाया जा सकता है। वास्तव में एक बंद रूप अभिव्यक्ति है जो O(1) संचालन में योग की गणना करता है।

किसी संख्या की Nth शक्ति की गणना करना

निम्नलिखित विधि पुनरावर्तन का उपयोग करके exp की शक्ति के लिए उठाए गए num के मूल्य की गणना करती है:

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

यह ऊपर वर्णित सिद्धांतों को दर्शाता है: पुनरावर्ती विधि एक बेस केस (दो मामलों, n = 0 और n = 1) को लागू करता है जो पुनरावृत्ति को समाप्त करता है, और एक पुनरावर्ती मामला जो विधि को फिर से कहता है। यह विधि O (N) है और इसे टेल-कॉल ऑप्टिमाइज़ेशन का उपयोग करके एक साधारण लूप में घटाया जा सकता है।

रिकर्सियन का उपयोग करके एक स्ट्रिंग को उल्टा करें

नीचे एक स्ट्रिंग को रिवर्स करने के लिए एक पुनरावर्ती कोड है

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

    public static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
    
        return reverse(s.substring(1)) + s.charAt(0);
    }
}

पुनरावर्तन के साथ ट्री डेटा संरचना का पता लगाना

3 सदस्य डेटा, बाएं चाइल्ड पॉइंटर और राइट चाइल्ड पॉइंटर नीचे दिए गए जैसे नोड वर्ग पर विचार करें।

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

हम नीचे की तरह कई नोड वर्ग की वस्तु को जोड़कर निर्मित पेड़ को पार कर सकते हैं, ट्रैवर्सल को पेड़ के इन-ऑर्डर ट्रैवर्सल कहा जाता है।

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

जैसा कि ऊपर दिखाया गया है, पुनरावृत्ति का उपयोग करके हम पेड़ डेटा संरचना को किसी अन्य डेटा संरचना का उपयोग किए बिना पार कर सकते हैं जो पुनरावृत्ति दृष्टिकोण के साथ संभव नहीं है।

रिकर्सन के प्रकार

रिकर्सन को हेड रिकर्सन या टेल रिसर्शन के रूप में वर्गीकृत किया जा सकता है, यह इस बात पर निर्भर करता है कि पुनरावर्ती विधि कॉल कहां रखी गई है।

सिर की पुनरावृत्ति में , पुनरावर्ती कॉल, जब ऐसा होता है, तो फ़ंक्शन में अन्य प्रसंस्करण से पहले आता है (यह सोचें कि यह शीर्ष पर हो रहा है, या फ़ंक्शन का शीर्ष)।

पूंछ पुनरावृत्ति में , यह विपरीत है - पुनरावर्ती कॉल से पहले प्रसंस्करण होता है। दो पुनरावर्ती शैलियों के बीच चयन करना मनमाना लग सकता है, लेकिन पसंद सभी अंतर ला सकती है।

पथ की शुरुआत में एक एकल पुनरावर्ती कॉल के साथ एक पथ का उपयोग करता है जिसे हेड रिकर्सशन कहा जाता है। पिछले प्रदर्शन की फैक्टोरियल फंक्शन हेड रिकरशन का उपयोग करता है। एक बार यह निर्धारित करने के बाद पहली बात यह है कि पुनरावृत्ति की आवश्यकता है अपने आप को डीक्रेटेड पैरामीटर के साथ कॉल करना है। एक पथ के अंत में एकल पुनरावर्ती कॉल के साथ एक फ़ंक्शन पूंछ पुनरावृत्ति का उपयोग कर रहा है।

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

यदि एक विधि के अंत में पुनरावर्ती कॉल होता है, तो इसे tail recursion कहा जाता है। पूंछ की पुनरावृत्ति similar to a loop । method executes all the statements before jumping into the next recursive call ।

यदि beginning of a method, it is called a head recursion की beginning of a method, it is called a head recursion पुनरावर्ती कॉल होता है beginning of a method, it is called a head recursion । method saves the state before jumping into the next recursive call ।

संदर्भ: सिर और पूंछ पुनरावृत्ति के बीच का अंतर

StackOverflowError और लूप के लिए पुनरावृत्ति

यदि एक पुनरावर्ती कॉल "बहुत गहरा" जाता है, तो इसका परिणाम StackOverflowError । जावा अपने थ्रेड स्टैक पर हर विधि कॉल के लिए एक नया फ्रेम आवंटित करता है। हालांकि, प्रत्येक थ्रेड के स्टैक का स्थान सीमित है। स्टैक पर बहुत सारे फ्रेम स्टैक ओवरफ्लो (SO) की ओर ले जाते हैं।

उदाहरण

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

इस पद्धति को बड़े मापदंडों के साथ कॉल करना (जैसे recursion(50000) शायद एक ढेर अतिप्रवाह में परिणाम होगा। सटीक मूल्य थ्रेड स्टैक आकार पर निर्भर करता है, जो बदले में थ्रेड निर्माण, कमांड लाइन मापदंडों जैसे -Xss , या पर निर्भर करता है। JVM के लिए डिफ़ॉल्ट आकार।

वैकल्पिक हल

डेटा संरचना में प्रत्येक पुनरावर्ती कॉल के लिए डेटा संग्रहीत करके एक पुनरावृत्ति को लूप में परिवर्तित किया जा सकता है। यह डेटा संरचना थ्रेड स्टैक के बजाय ढेर पर संग्रहीत की जा सकती है।

सामान्य तौर पर एक विधि आह्वान की स्थिति को बहाल करने के लिए आवश्यक डेटा को एक स्टैक में संग्रहीत किया जा सकता है और थोड़ी देर के लूप का उपयोग पुनरावर्ती कॉल को "अनुकरण" करने के लिए किया जा सकता है। आवश्यक डेटा में शामिल हो सकते हैं:

• ऑब्जेक्ट विधि के लिए बुलाया गया था (उदाहरण के तरीके केवल)
• विधि मापदंडों
• स्थानीय चर
• निष्पादन या विधि में वर्तमान स्थिति

उदाहरण

निम्न वर्ग एक पेड़ की संरचना को एक निर्दिष्ट गहराई तक मुद्रण के पुनरावर्ती की अनुमति देता है।

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

जैसे

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

प्रिंटों

(((...)20(...))10((...)30))

इसे निम्नलिखित लूप में बदला जा सकता है:

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}

List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

नोट: यह सामान्य दृष्टिकोण का एक उदाहरण है। अक्सर आप फ़्रेम को दर्शाने और / या फ़्रेम डेटा को संग्रहीत करने के लिए बहुत बेहतर तरीके से आ सकते हैं।

जावा में गहरी पुनरावृत्ति समस्याग्रस्त है

पुनरावर्तन का उपयोग करते हुए दो सकारात्मक संख्याओं को जोड़ने के लिए निम्न भोली विधि पर विचार करें:

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

यह एल्गोरिदम सही है, लेकिन इसकी एक बड़ी समस्या है। यदि आप बड़े a साथ add कहते add , तो यह StackOverflowError , Java के किसी भी संस्करण (कम से कम) Java 9 पर क्रैश हो जाएगा।

एक ठेठ कार्यात्मक प्रोग्रामिंग भाषा (और कई अन्य भाषाओं) में कंपाइलर पूंछ पुनरावृत्ति का अनुकूलन करता है। संकलक ध्यान देगा कि add लिए कॉल (टैग की गई रेखा पर) एक पूंछ कॉल है , और लूप के रूप में पुनरावर्ती को प्रभावी ढंग से फिर से लिखेगा। इस परिवर्तन को टेल-कॉल एलिमिनेशन कहा जाता है।

हालांकि, वर्तमान पीढ़ी के जावा कंपाइलर टेल कॉल एलिमिनेशन नहीं करते हैं। इसके बजाय, में से प्रत्येक पुनरावर्ती कॉल; (नीचे देखें यह एक सरल निरीक्षण नहीं है इस के लिए पर्याप्त तकनीकी कारणों से कर रहे हैं।।) add का कारण बनता है एक नया फ्रेम धागा के ढेर पर आवंटित किया जाना है। उदाहरण के लिए, यदि आप add(1000, 1) कहते हैं, तो उत्तर 1001 पर आने के लिए 1000 पुनरावर्ती कॉल लगेंगे।

समस्या यह है कि धागा बनाते समय जावा थ्रेड स्टैक का आकार तय होता है। (इसमें एकल-थ्रेडेड प्रोग्राम में "मुख्य" धागा शामिल है।) यदि बहुत सारे स्टैक फ्रेम आवंटित किए गए हैं तो स्टैक ओवरफ्लो हो जाएगा। JVM इसका पता लगाएगा और एक StackOverflowError फेंक देगा।

इससे निपटने के लिए एक दृष्टिकोण केवल एक बड़े स्टैक का उपयोग करना है। जेवीएम विकल्प हैं जो स्टैक के डिफ़ॉल्ट आकार को नियंत्रित करते हैं, और आप स्टैक आकार को Thread कंस्ट्रक्टर पैरामीटर के रूप में भी निर्दिष्ट कर सकते हैं। दुर्भाग्य से, यह केवल स्टैक ओवरफ्लो को "बंद" करता है। यदि आपको एक संगणना करने की आवश्यकता है जिसमें एक भी बड़े स्टैक की आवश्यकता होती है, तो StackOverflowError वापस आती है।

वास्तविक समाधान पुनरावर्ती एल्गोरिदम की पहचान करना है जहां गहरी पुनरावृत्ति की संभावना है, और मैन्युअल रूप से स्रोत कोड स्तर पर टेल-कॉल ऑप्टिमाइज़ेशन करते हैं। उदाहरण के लिए, हमारे add मेथड को इस प्रकार फिर से लिखा जा सकता है:

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

(स्पष्ट रूप से, दो पूर्णांकों को जोड़ने के बेहतर तरीके हैं। उपरोक्त केवल टेल टेल एलिमिनेशन के प्रभाव को दर्शाने के लिए है।)

जावा (अभी तक) में टेल-कॉल उन्मूलन क्यों लागू नहीं किया गया है

कई कारण हैं कि जावा में टेल कॉल एलिमिनेशन को जोड़ना आसान नहीं है। उदाहरण के लिए:

• कुछ कोड StackOverflowError पर (उदाहरण के लिए) एक कम्प्यूटेशनल समस्या के आकार पर एक बाध्य जगह पर भरोसा कर सकते हैं।
• सैंडबॉक्स सुरक्षा प्रबंधक अक्सर कॉल स्टैक का विश्लेषण करने पर भरोसा करते हैं, जब यह तय करते हैं कि विशेषाधिकार प्राप्त कार्रवाई करने के लिए गैर-विशेषाधिकार प्राप्त कोड को अनुमति दी जाए या नहीं।

जैसा कि जॉन रोज़ "वीएम में टेल कॉल" में बताते हैं:

"कॉलर के स्टैक फ्रेम को हटाने के प्रभाव कुछ एपीआई को दिखाई देते हैं, विशेष रूप से अभिगम नियंत्रण जांच और स्टैक ट्रेसिंग। यह ऐसा है जैसे कि कॉलर के कॉलर को सीधे कॉलली कहा जाता था। नियंत्रण द्वारा स्थानांतरित किए जाने के बाद कॉलर के पास मौजूद किसी भी विशेषाधिकार को छोड़ दिया जाता है। कैली। हालांकि, नियंत्रण के हस्तांतरण से पहले कैली विधि का संबंध और पहुंच की गणना की जाती है, और टेल-कॉलिंग कॉलर को ध्यान में रखा जाता है। "

दूसरे शब्दों में, टेल-कॉल एलिमिनेशन एक्सेस कंट्रोल मेथड को गलत तरीके से सोचने का कारण बना सकता है कि विश्वसनीय कोड के लिए सुरक्षा संवेदनशील एपीआई कहा जा रहा था।