প্রথম প্রথম যখন রিকার্শন (recursion) শিখলাম তখন সবচেয়ে বড় যে সমস্যায় পরেছি তা হলো রানটাইম এরর বা RTE (Run Time Error). পরে জানতে পারলাম Stack size overflow হওয়ার জন্য RTE হয়।
আজ ইন্টারনেট সার্ফিং করতে করতে একটা আর্টিকেল পেলাম এই বিষয়ে। আর্টিকেলটার নাম টেইল কল রিকার্শন অপটিমাইজেশন (Tail call recursion optimization)। । এখন আসা যাক টেইল কল রিকার্শন অপটিমাইজেশন কি ?
Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function. The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.
SOURCE: Stackoverflow
প্রথমে জানা দরকার টেইল-কল (Tail call) জিনিসটা কি?
সহজভাবে বলতে গেলে, টেইল-কল হলো একটা ফাংশনের শেষ লাইন। অর্থাৎ যে কাজটি করার পর ফাংশনের আর কোনো কাজ থাকে না সেটাই টেইল-কল। উদাহরণ হিসেবে নিচের কোডটা দেখি:
| 1 2 3 4 5 6 | int fact(int n){ int ans=1; for(int i=1;i<=n;i++) ans=ans*i; return ans; } |
এটা ফ্যাক্টরিয়াল বের করার ফাংশন। এই ফাংশনে return ans; এর পর ফাংশনটির আর কোনো কাজ নেই। এটাই হলো টেইল-কল।
একটা রিকার্সিভ ফাংশন কে তখনই রিকার্সিভ বলা হবে যখন রিকার্সিভ কলটাই ঐ ফাংশনের শেষ কাজ হয়। উদাহরণ হিসেবে নিচের কোডটা দেখা যাক
| 1 2 3 4 5 | int mod=INT_MAX; int fact(int n){ if(n==0) return 1; return (n*fact(n-1))%mod; } |
NOTE: এখানে mod করা হয়েছে overflow aviod জন্য। আরও পরুন
এখন এই রিকার্সিভ ফাংশনটা কি টেইল কল?
উত্তর হলো না। কারন এখানে এটা পরিস্কার যে রিকার্সিভ কলের পরেও আরও কাজ আছে। কাজটা হলো রিকার্সিভ কলের পরে যে ভ্যালুগুলো পাওয়া যাবে তা গুন করা।
ফাংশনটি প্রথমে fact(n−1) এর মান রিকার্সিভলি বের করে আনবে, এরপর সেটাকে n দিয়ে গুণ করবে। আমরা চাইলে নিচের মতো করে লিখতে পারি:
| 1 2 3 4 5 6 | int mod=INT_MAX; int fact(int n){ if(n==0) return 1; int value = fact(n-1); return (value*n)%mod; } |
এখানে শুধু আগের কোডের শেষ লাইনটা ভেঙে লেখা হয়েছে। এখন বুঝা যাচ্ছে যে আগের কোডের রিকার্সিভ কলটাই ঐ ফাংশনের শেষ কাজ ছিলো না। বরং এখানে আগের লাইনে ভ্যালু বের করে এনে পরে লাইনে তা ক্যালকুলেট করা হয়েছে।
এখন যদি আমরা মেমোরি না বাড়িয়ে fact(1000000) বের করি তাহলে কি হবে? উত্তর হলো প্রোগ্রাম ক্রাশ করবে আর segmentation fault দেখাবে। কারন প্রোগ্রামটি বেশি মেমোরি ব্যবহার করেছে।
আমরা জানি প্রত্যেকটা প্রোগ্রাম একটা মেমোরি স্পেসে রান করে। যদি ফাংশনটাকে আমরা আবার রিকার্সিভ কল করি তবে ফাংশনটা আবার একই মেমোরি স্পেসে নতুন প্যারামিটার ব্যবহার করে রান হয় এবং ফিরে আসার পরে পুরানো প্যারামিটার ব্যবহার করে বাকি কাজ শেষ করে।
এখন এটা প্রশ্ন হতে পারে যে কিভাবে পুরানো প্যারামিটার সেভ করে রাখা হয়। এটা বুঝতে নিচের চিত্রটি দেখতে পারি।
প্রথমে যখন fact(3) কে কল করা হয়, তখন n=3 কে স্ট্যাকে সেভ করা হয় এবং fact(2) কল হয়। fact(2) কল করা হলে একই ভাবে n=2 কে স্ট্যাকে সেভ করা হয় এবং fact(1) কল হয়। এভাবে সেভকরে রাখার ফলে স্ট্যাকের উপরে আগের ফাংশন এর সেভ করা প্যারামিটার গুলো সহজেই খুজে পাওয়া যায়।
এখানে আমরা যখন fact(n) কল করছি তখন n টি কপি আমাদের stack এ সেভ করে রাখতে হচ্ছে। C++ এ রিকার্শন কি পরিমান মেমোরি ব্যবহার করতে পারবে তার একটা লিমিট আছে ।
যখন মেমোরি ব্যবহার লিমিট এর বাইরে চলে যাচ্ছে তখনই প্রোগ্রামটা ক্রাশ করছে। আমরা যদি এই মেমরি ব্যবহার কোনোভাবে কমাতে পারি তাহলে কোড ক্র্যাশ করবে না। বর্তমানের কম্পাইলারগুলো যদি দেখে যে অতিরিক্ত মেমরি ব্যবহার দরকার নেই তাহলে সে এমনভাবে অপটিমাইজড মেশিন কোড জেনারেট করে যাতে মেমরি ব্যবহার কম হয়। আমরা সেই বুদ্ধিটাই কাজে লাগাবো।
একটা Tail call recursion optimesed কোড এর উদাহরণ দেয়া যাক:
| 1 2 3 4 5 | int mod=INT_MAX; int fact(int n,int ans=1){ if(n==0) return ans; return fact(n-1,(n*ans)%mod); } |
উপরের উদাহরনটাতে আমরা দেখতে পাচ্ছি, আমরা আমাদের অংশিক উত্তরটা সাথে সাথে হিসাব করে ans প্যারামিটার এর মাধ্যমে পাস করে দিচ্ছি। সুতরাং এই লাইনটাই উপরের ফাংশনের টেইলকল বা শেষ লাইন। একদম শেষে গিয়ে ঐ প্যরামিটারেই আমরা উত্তর পেয়ে যাবো।
| 1 2 3 4 5 6 | fact(4, 1) = fact(3, 4 * 1) = fact(2, 4 * 3) = fact(1, 4 * 3 * 2) = fact(0, 4 * 3 * 2 * 1) = fact(0, 24) |
এই কোড যখন কম্পাইল করা হবে তখন কম্পাইলার দেখবে স্ট্যাক ব্যবহার করে পুরানো মান সেভ করে রাখার কোনো দরকার নেই। তাই এই কোডে ততটুকুই মেমরি লাগবে যতখানি লাগতো সাধারণ লুপ ব্যবহার করলে!
আধুনিক যেকোন ল্যাংগুয়েজের কম্পাইলার এই অপটিমাইজেশনটা করতে পারে। তুমি যদি সি/সি++ ব্যবহার করো তাহলে প্রোগ্রাম রান করার আগে তুমি দেখো -O2 কম্পাইলার অপটিমাইজেশন চালু করা আছে নাকি, না থাকলে আগে চালু করে দাও, তুমি যে কোড এডিটর ব্যবহার করছো সেখানে চালু করার অপশন থাকবে। অথবা তুমি সরাসরি টার্মিনাল থেকেও কম্পাইল করতে পারো -O2 অপশন ব্যবহার করে। কিভাবে করতে হয় গুগলে সার্চ দিয়ে দেখে নাও। (প্রোগ্রামিং কনটেস্টে জাজ মেশিনে সাধারণত এই অপটিমাইজেশন চালু করা থাকে)
এখন আমরা যদি fact(1000000,1) রান করাই তবে দেখবো সুন্দর আউটপুট দিচ্ছে।
If you have any kind of problem, please comment down below.
প্রাইম কাহিনি – প্রাইম নাম্বার এর অ্যালগরিদম গুলো
Time complexity; ও বিগ O নোটেশন
For further reading:
