রিকার্সন
একটি ফাংশন যখন নিজেকেই কল করে, তখন তাকে রিকার্সিভ বলা হয়।
ফাংশন কল আর লুপের মধ্যে একটি গুরুত্বপূর্ণ পার্থক্য হলো এই যে, কোনো ফাংশন কল করলে যে অ্যাড্রেসে ফিরে আসতে হবে সেটি স্ট্যাকে পুশ করা হয়।
এর মানে হলো, একটি রিকার্সিভ ফাংশন সাধারণত সমতুল্য একটি লুপের চেয়ে বেশি স্ট্যাক স্পেস দাবি করে।
এর ফলাফল হিসেবে, যে ফাংশন বারবার নিজেকেই কল করে চলে, সেটি একসময় পুরো স্ট্যাক স্পেস শেষ করে ফেলতে পারে।
এটাকে বলা হয় স্ট্যাক ওভারফ্লো।
এই কারণেই প্রতিটি রিকার্সিভ ফাংশনে অন্তত একটি বেস কেস থাকতে হবে, অর্থাৎ এমন একটি অবস্থা, যেখানে ফাংশনটি নিজেকে কল না করেই রিটার্ন করে।
যেকোনো রিকার্সিভ কলকে একসময় না একসময় একটি বেস কেসে পৌঁছাতেই হবে।
উদাহরণস্বরূপ, ফ্যাক্টোরিয়াল ফাংশনটি, অর্থাৎ 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।
এই অর্থে একটি টেইল রিকার্সিভ ফাংশনকে মূলত একটি লুপের মতোই ভাবা যায়, যেখানে রিকার্সিভ কলটি আবার উপরে লাফিয়ে যায়, আর বেস কেসটিই সেই শর্ত যা লুপটি শেষ করে।
লার্নিং অনুশীলনী
