पाइपर की पाई

रिकर्सन

जब कोई फंक्शन खुद को कॉल करता है, तब वह रिकर्सिव कहलाता है।

फंक्शन कॉल और लूप में एक बड़ा अंतर यह है कि फंक्शन को कॉल करने पर स्टैक पर वह एड्रेस डाला जाता है जहाँ वापस लौटना है। इसका मतलब है कि एक रिकर्सिव फंक्शन को आम तौर पर उतना ही काम करने वाले लूप से अधिक स्टैक स्थान चाहिए।

इसका परिणाम यह है कि जो फंक्शन बार-बार खुद को कॉल करता रहता है, वह किसी समय पूरा स्टैक स्थान खत्म कर सकता है। इसे स्टैक ओवरफ्लो कहते हैं।

इसीलिए हर रिकर्सिव फंक्शन में कम से कम एक बेस केस होना चाहिए। बेस केस वह स्थिति है जब फंक्शन खुद को कॉल किए बिना लौट जाता है। हर रिकर्सिव कॉल को अंततः किसी बेस केस तक पहुँचना ही होता है।

उदाहरण के लिए, फैक्टोरियल फंक्शन n! = n * (n - 1) * ... * 1 को बेस केस के रूप में 1 लेकर रिकर्सिव तरीके से परिभाषित किया जा सकता है:

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

ध्यान दीजिए कि factorial को रिकर्सन से पहले push rdi करना ही होगा और बाद में pop rdi। ऐसा इसलिए है क्योंकि n * (n-1)! निकालने के लिए रिकर्सिव कॉल लौटने के बाद भी उसे n की ज़रूरत पड़ती है।

यह भी ध्यान दीजिए कि कैली-सेव्ड रजिस्टर इस्तेमाल करने से यह समस्या हल नहीं होगी।

रिकर्सिव फंक्शन भले ही खुद का कॉलर हो सकता है, लेकिन वह खुद किसी और फंक्शन का कैली भी है। इसका मतलब है कि फंक्शन को कैली-सेव्ड रजिस्टर इस्तेमाल करने से पहले उन्हें सुरक्षित रखना होता है और इस्तेमाल के बाद उनकी वैल्यू वापस लानी होती है। यह आम तौर पर push/pop क्रम से किया जाता है, जैसा हमने पिछले कॉन्सेप्ट में देखा था।

बेस केस को छोड़कर रिकर्सिव फंक्शन का हर फ्रेम भी एक कॉलर है जिसे अपने लोकल वेरिएबलो को सुरक्षित रखना होता है, इसलिए यह push/pop क्रम हर फ्रेम के लिए दोहराना पड़ता है। वेरिएबल को रजिस्टर इस्तेमाल किए बिना सीधे स्टैक में रखने पर भी हर फ्रेम में वही 8 बाइट खर्च होते।

इसका मतलब है कि हर रिकर्सिव कॉल call द्वारा डाले गए रिटर्न एड्रेस के लिए स्टैक में 8 बाइट जोड़ता है, और अपने हर उस लोकल वेरिएबल के लिए 8 बाइट जिसे सुरक्षित रखना है।

फंक्शन हर फ्रेम के साथ ये बाइटें स्टैक में तब तक जोड़ता रहता है जब तक कि वह अपने बेस केस तक न पहुँच जाए। इसके बाद ही स्टैक उलटे क्रम में खुलने लगता है, जिसमें हर रिकर्सिव कॉल जितने pop चाहिए उतने करता है और फिर एक ret।

उदाहरण के लिए, अगर factorial को आर्गुमेंट 10 के साथ कॉल किया जाए, तो बेस केस 1 तक पहुँचने से पहले वह खुद को नौ बार कॉल करेगा। उस समय तक हर पिछले फ्रेम के n (8 बाइट) और रिटर्न एड्रेस (8 बाइट) को रखने में 144 बाइट खर्च हो चुके होंगे।

टेल कॉल

कुछ स्थितियों में कोई फंक्शन दूसरे फंक्शन को कॉल करने के बाद और लौटने से पहले कोई और काम नहीं करता।

उदाहरण के लिए यह देखिए:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

फंक्शन triple_of_square:

• जो आर्गुमेंट पास हुआ है (rdi में) उसे खुद से गुणा करता है और उसका वर्ग निकालता है;
• फिर यह times_three को कॉल करता है, जो पास किए गए आर्गुमेंट को तीन से गुणा करके लौटाता है।

परिणामस्वरूप, triple_of_square वैल्यू 3*x² लौटाता है, जहाँ x उसका आर्गुमेंट है, जो rdi में पास होता है।

ध्यान दीजिए कि times_three को कॉल करने के बाद triple_of_square में कोई काम नहीं होता, फंक्शन बस लौट जाता है। ऐसी स्थिति में call इस्तेमाल करने के बजाय फंक्शन jmp इस्तेमाल करके निष्पादन कॉल किए गए फंक्शन को सौंप सकता है:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

इसे टेल कॉल कहते हैं।

टेल कॉल का मुख्य लाभ यह है कि इसमें call की अतिरिक्त लागत से बचा जाता है। call स्टैक पर एक रिटर्न एड्रेस डालता है, और नियंत्रण को उस जगह वापस आने के लिए एक मेल खाता ret होना ज़रूरी है।

टेल कॉल दोनों से बच जाता है: न डालने के लिए कोई रिटर्न एड्रेस होता है, न साथ जोड़ने के लिए कोई अतिरिक्त ret, बस कॉल किए गए फंक्शन का अपना ret।

टेल रिकर्सन

टेल कॉल उन रिकर्सिव फंक्शनों के लिए खास तौर पर काम का है जो लौटने से पहले खुद को कई बार कॉल कर सकते हैं।

लेकिन हर रिकर्सिव कॉल को सीधे टेल कॉल में नहीं बदला जा सकता। चूँकि jmp नियंत्रण कॉल किए गए फंक्शन को सौंप देता है, इसलिए टेल कॉल के बाद कॉलर कोई और काम नहीं कर सकता।

उदाहरण के लिए, ऊपर वाला factorial फंक्शन टेल रिकर्सिव नहीं है। रिकर्सिव कॉल के बाद भी उसे imul rax, rdi का इस्तेमाल करके परिणाम को वर्तमान n से गुणा करना पड़ता है।

ऐसी स्थितियों में कभी-कभी एक एक्युमुलेटर इस्तेमाल किया जा सकता है, जो आंशिक गणनाएँ इकट्ठा करेगा और अंत में लौटाया जाएगा। उदाहरण के लिए, हम एक factorial_helper बना सकते हैं जो ज़्यादातर काम करता है, और फिर factorial एक एक्युमुलेटर तैयार करके नियंत्रण factorial_helper को सौंप देता है:

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

चूँकि रिकर्सिव कॉल के बाद कोई और काम नहीं होता, इसलिए हमें अब rdi सुरक्षित रखने की भी ज़रूरत नहीं। यहाँ न call है न push rdi, इसलिए हर रिकर्सिव इटरेशन स्टैक में 0 बाइट जोड़ता है: कोई अतिरिक्त स्टैक स्थान इस्तेमाल नहीं होता। यह वर्शन n के कितने भी बड़े मान को स्टैक ओवरफ्लो किए बिना संभाल सकता है। यह ज़्यादा कुशल भी है और ज़्यादा सुरक्षित भी।

कुछ मामलों में फंक्शनों का क्रम बदलकर हेल्पर तक के jmp से भी बचा जा सकता है। उदाहरण के लिए, factorial और triple_of_square को इस तरह फिर से लिखा जा सकता है:

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

ऊपर के स्निपेट में factorial का निष्पादन सीधे factorial_helper में चला जाता है। यही triple_of_square और times_three के साथ भी होता है। दोनों ही मामलों में निष्पादन क्रम से आगे बढ़ता रहता है और ऐसा लगता है कि टेल फंक्शन तो "मुख्य" फंक्शन के अंदर का बस एक लोकल लेबल है।

वास्तव में किसी लोकल लेबल और किसी फंक्शन में कोई ज़रूरी अंतर नहीं होता। x86-64 असेंबली इनमें से किसी को भी खास दर्जा नहीं देती, ये तो बस एक ऐसे सेक्शन में मौजूद एड्रेस हैं जिसमें चलाने योग्य कोड होता है, जैसे section .text।

इस तरह एक टेल रिकर्सिव फंक्शन को मोटे तौर पर एक ऐसे लूप जैसा ही माना जा सकता है जिसमें रिकर्सिव कॉल वापस ऊपर कूद जाता है और बेस केस वह शर्त होती है जो लूप को खत्म करती है।