بازگشت
یک تابع زمانی «بازگشتی» است که خود را فراخوانی کند.
یکی از تفاوت‌های اصلی میان فراخوانی تابع و حلقه این است که فراخوانی یک تابع، آدرس بازگشت را روی پشته می‌گذارد.
این یعنی یک تابع بازگشتی معمولاً فضای پشته‌ی بیشتری از یک حلقه‌ی معادل می‌طلبد.
در نتیجه، تابعی که مدام خود را فراخوانی می‌کند ممکن است در نهایت تمام فضای پشته را مصرف کند.
به این وضعیت «سرریز پشته» می‌گویند.
به همین دلیل، هر تابع بازگشتی باید دست‌کم یک «حالت پایه» داشته باشد؛ حالت پایه وضعیتی است که در آن تابع بدون فراخوانی خودش بازمی‌گردد.
هر فراخوانی بازگشتی باید در نهایت به یک حالت پایه برسد.
برای مثال، تابع فاکتوریل 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 * (n-1)! را محاسبه کند.
همچنین توجه کنید که استفاده از یک ثبات حفظ‌شده توسط فراخوانی‌شده این مشکل را حل نمی‌کند.
با اینکه یک تابع بازگشتی فراخوانی‌کننده‌ی بالقوه‌ی خودش است، خودش هم فراخوانی‌شده‌ی تابع دیگری است.
یعنی تابع باید ثبات‌های حفظ‌شده توسط فراخوانی‌شده را نیز پیش از استفاده نگه دارد و پس از استفاده مقدارشان را بازگرداند.
این کار معمولاً با دنباله‌ای از push/pop انجام می‌شود، همان‌طور که در یک مفهوم قبلی دیدیم.
چون هر «قاب» از یک تابع بازگشتی، به‌جز حالت پایه، خودش هم فراخوانی‌کننده‌ای است که باید متغیرهای محلی خودش را حفظ کند، این دنباله‌ی push/pop باید برای هر قاب تکرار شود.
حتی ذخیره‌ی مستقیم متغیر در پشته، بدون استفاده از ثبات‌ها، باز هم همان 8 بایت را به‌ازای هر قاب هزینه دارد.
این یعنی هر فراخوانی بازگشتی 8 بایت برای آدرس بازگشتی که call روی پشته می‌گذارد به پشته اضافه می‌کند، به‌علاوه‌ی 8 بایت برای هر متغیر محلی که باید ذخیره کند.
تابع در هر قاب همچنان این بایت‌ها را به پشته اضافه می‌کند تا به حالت پایه برسد.
تنها در این هنگام است که به ترتیب معکوس باز می‌شود؛ هر فراخوانی بازگشتی به تعداد لازم pop می‌زند و سپس یک ret.
برای مثال، اگر factorial با آرگومان 10 فراخوانی شود، پیش از رسیدن به حالت پایه‌ی 1، نُه بار خود را فراخوانی می‌کند.
در آن نقطه، 144 بایت برای ذخیره‌ی n (8 بایت) و آدرس بازگشت (8 بایت) در هر قاب پیشین مصرف شده بود.
فراخوانی دنباله
در برخی موقعیت‌ها، تابع پس از فراخوانی تابعی دیگر و پیش از بازگشت، کار دیگری انجام نمی‌دهد.
برای مثال، این را در نظر بگیرید:
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 داده شده است.
توجه کنید که در triple_of_square پس از فراخوانی times_three هیچ کاری انجام نمی‌شود و تابع به‌سادگی بازمی‌گردد.
در چنین موقعیتی، تابع به‌جای استفاده از 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 که پیش‌تر دیدیم دنباله‌بازگشتی نیست.
پس از فراخوانی بازگشتی، هنوز باید نتیجه را با n جاری ضرب کند، با استفاده از imul rax, rdi.
در چنین موقعیت‌هایی، گاهی می‌توان از یک «انباشته‌گر» استفاده کرد که محاسبات جزئی را جمع می‌کند و در پایان بازگردانده می‌شود.
برای مثال، می‌توانیم یک 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.
به این ترتیب، می‌توان یک تابع دنباله‌بازگشتی را اساساً همانند یک حلقه در نظر گرفت که در آن فراخوانی بازگشتی به بالای حلقه می‌پرد و حالت پایه شرطی است که حلقه را پایان می‌دهد.
تمرین یادگیری
