त्वरित प्रकार को पूंछ रिकर्सिव एल्गोरिदम क्यों कहा जाता है?

Question

मुझे पता है कि एक पूंछ रिकर्सिव एल्गोरिदम written out in this SO answer के रूप में क्या है। हालांकि मैं इस video of quick sort algorithm from MIT और 18:30 सेकंड में जा रहा हूं, प्रोफेसर का कहना है कि यह पूंछ रिकर्सिव एल्गोरिदम है। मैं कनेक्ट करने में असफल रहा कि यह कैसे पूंछ रिकर्सिव है। हम रिकर्सन के किसी भी चरण में गणना नहीं कर रहे हैं या हम हैं? क्या आप समझा सकते हैं कि इसे पूंछ रिकर्सिव एल्गोरिदम के उदाहरण के रूप में क्यों उद्धृत किया गया है। कृपया आधार पर अपना उत्तर आधार दें कि मुझे पता है कि एक रिकर्सिव एल्गोरिदम क्या है। वह हिस्सा जो मुझे स्पष्ट नहीं है, उसे पूंछ रिकर्सिव क्यों कहा जाता है?

Answer 1

रिकर्सिव फ़ंक्शन का पहला चरण विभाजन है। और फिर, अंतिम चरण के रूप में, आप दो विभाजनों पर रिकर्सिव फ़ंक्शन को कॉल करते हैं।

विकिपीडिया से

:

कंप्यूटर विज्ञान में, एक पूंछ कॉल एक सबरूटीन कॉल कि अपनी अंतिम कार्रवाई के रूप में एक और प्रक्रिया के अंदर होता है; यह वैल्यू का उत्पादन कर सकता है जिसे तुरंत कॉलिंग प्रक्रिया द्वारा वापस कर दिया जाता है।

Answer 2

पूंछ रिकर्सन चरणों में गणना करने के बारे में नहीं है। यह "कॉल स्टैक के निर्माण के बिना रिकर्सन का मूल्यांकन किया जा सकता है।" What is tail recursion? द्वारा दिया गया उदाहरण यह एक विशेष मामला है। आप और अधिक गहराई से उदाहरण देखें, तो क्या आप पा सकते हैं कि

def recsum(x): 
if x==1: 
    return x 
else: 
    return x+recsum(x-1) 

1) उपरोक्त कोड को सफलतापूर्वक चलाने के लिए, आप कॉल स्टैक का निर्माण करने की जरूरत है। लेकिन,

def tailrecsum(x,running_total=0): 
    if x==0: 
    return running_total 
    else: 
    return tailrecsum(x-1,running_total+x) 

2) उपरोक्त कोड को चलाने के लिए, आप running_total की वजह से कॉल स्टैक का निर्माण करने की जरूरत नहीं है। बस "मूल कॉल" के लिए कॉल स्टैक बनाएं और रिकर्सन के लिए, कॉल स्टैक बनाने की कोई आवश्यकता नहीं है, क्योंकि इस फ़ंक्शन का मूल्यांकन करने के लिए आवश्यक स्थिति run_total में संग्रहीत है।

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

Answer 3

Quicksort की विकि पृष्ठ पर एक नजर डालें। पुनरावर्ती

function quicksort(array, 'left', 'right') 

    // If the list has 2 or more items 
    if 'left' < 'right' 

     // See "Choice of pivot" section below for possible choices 
     choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right' 

     // Get lists of bigger and smaller items and final position of pivot 
     'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex') 

     // Recursively sort elements smaller than the pivot 
     quicksort(array, 'left', 'pivotNewIndex' - 1) 

     // Recursively sort elements at least as big as the pivot 
     quicksort(array, 'pivotNewIndex' + 1, 'right') 

Tail recursion की परिभाषा के अनुसार पूंछ का एक संस्करण है, quicksort के अंतिम विधि कॉल ही है कि पूंछ प्रत्यावर्तन है,। लेकिन कुछ अन्य कार्यान्वयन पूंछ रिकर्सिव नहीं हैं।

quicksort(left) + pivot + quicksort(right) 

क्योंकि quicksort में अंतिम कार्रवाई है sorted_left + pivot + sorted_right है कि अपने पिछले प्रश्न से विकिपीडिया लेख