ভূমিকা
টেইল কল রিকার্শন
একটি ফাংশন টেইল-রিকার্সিভ হয় যদি ফাংশনটি যে কাজটি সবশেষে সম্পাদন করে তা হয় নিজেকে কল করা।
প্রতিবারই কোনো ফাংশন কল করা হলে তার লোকাল ভ্যারিয়েবল ও আর্গুমেন্টসহ একটি স্ট্যাক ফ্রেম ফাংশন কল স্ট্যাকের উপরে রাখা হয়। কোনো ফাংশন রিটার্ন করলে স্ট্যাক ফ্রেমটি স্ট্যাক থেকে সরিয়ে ফেলা হয়।
টেইল-রিকার্সিভ ফাংশন টেইল কল অপটিমাইজেশন (বা টেইল কল এলিমিনেশন) সম্ভব করে। এটি এমন একটি অপটিমাইজেশন, যা আগের ফাংশনের আর স্ট্যাক ফ্রেমটির প্রয়োজন নেই নিশ্চিত হলে পরের ফাংশন কলের জন্য সেই শেষ স্ট্যাক ফ্রেমটি পুনরায় ব্যবহার করার সুযোগ দেয়। এতে ফাংশন কল স্ট্যাক ওভারফ্লো হওয়ার আশঙ্কা কমে, অর্থাৎ এমন পরিস্থিতি যেখানে ফাংশন কল স্ট্যাকে এত বেশি ফ্রেম থাকে যে আরেকটি তৈরি করার মতো মেমরি আর অবশিষ্ট থাকে না।
Elm-এ টেইল কল অপটিমাইজেশন
কিছু নির্দিষ্ট শর্তে Elm কম্পাইলার JavaScript-এ কম্পাইল করার সময় স্বয়ংক্রিয়ভাবে একটি টেইল কল অপটিমাইজেশন করে দিতে পারে।
একটি রিকার্সিভ ফাংশনের ক্ষেত্রে অপটিমাইজেশনটি হতে পারে, যখন একটি ব্রাঞ্চের শেষ কাজটি হয় ফাংশনটিকে নিজেকে একটি সাধারণ ফাংশন অ্যাপ্লিকেশনে কল করা। চলুন কিছু উদাহরণ দেখি:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
উপরের ইমপ্লিমেন্টেশনটি টেইল রিকার্সিভ নয়, কারণ else ব্রাঞ্চের শেষ কাজটি একটি গুণ, n *।
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
উপরের ইমপ্লিমেন্টেশনটি টেইল রিকার্সিভ এবং এটিকে অপটিমাইজ করা হবে, কারণ else ব্রাঞ্চের শেষ কাজটি factorialHelper-এর নিজেকে কল করা। Int -> Int টাইপ সিগনেচারযুক্ত কোনো ফাংশনের জন্য এটি সম্ভব হতো না, আর বাস্তবে হেল্পার ফাংশন ডিফাইন করে প্রায়ই টেইল কল অপটিমাইজেশন অর্জন করা হয়।
নির্দেশনা
পাইপার একজন উৎসাহী পাই বেকার।
কেউ জানে না, তিনি তাঁর নামের কারণে পাই বেক করা বেছে নিয়েছিলেন, নাকি শখের সাথে মিলিয়ে নিজের নাম বদলেছিলেন।
এক নজরে দেখলে পরেরটা খুব একটা সম্ভাবনাময় মনে হয় না, কিন্তু আসলে দেখুন, পাইপার পাই-এর প্রতি একেবারে মুগ্ধ।
তিনি সবসময় রান্নাঘরে ছোটখাটো পরীক্ষা-নিরীক্ষা করেন, রেসিপিতে হেরফের করেন, নিজের হাতযশ বাড়ান, আর তাতে তাঁর বন্ধুরা দারুণ খুশি হয়।
সর্বশেষে তাঁর আগ্রহ কী নিয়ে?
যতটা সম্ভব গোলাকার পাই বেক করা, গাণিতিক নিখুঁততার মাত্রা পর্যন্ত, তাঁর প্রিয় সংখ্যাটির সাহায্যে, আপনি ঠিকই ধরেছেন: π।
ধাপে ধাপে π হিসাব করার একটি চমৎকার সূত্র পাইপার খুঁজে পেয়েছেন, নিউটন/অয়লার কনভার্জেন্স ট্রান্সফরমেশন:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
π হিসাব করে পাইপারকে তাঁর গাণিতিকভাবে নিখুঁত পাই বেক করতে সাহায্য করুন।
1. ফ্যাক্টোরিয়াল
চলুন প্রথমে একটু গা গরম করে নেওয়া যাক।
ফ্যাক্টোরিয়াল অপারেটর, যাকে সাধারণত ! দিয়ে লেখা হয়, এভাবে সংজ্ঞায়িত করা হয়
0! = 1
n! = 1 * 2 * 3 * ... * n
factorial ফাংশনটি ডিফাইন করুন, যা টেইল রিকার্সিভ পদ্ধতিতে ফ্যাক্টোরিয়াল হিসাব করবে।
factorial 4
-- 24
2. ডাবল ফ্যাক্টোরিয়াল
ডাবল ফ্যাক্টোরিয়াল অপারেটর, যাকে সাধারণত !! দিয়ে লেখা হয়, এভাবে সংজ্ঞায়িত করা হয়
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
doubleFactorial ফাংশনটি ডিফাইন করুন, যা টেইল রিকার্সিভ পদ্ধতিতে ফ্যাক্টোরিয়াল হিসাব করবে।
factorial 5
-- 15
factorial 6
-- 48
3. নিউটন/অয়লার কনভার্জেন্স ট্রান্সফরমেশন
pipersPi ফাংশনটি ডিফাইন করুন, যা নিউটন/অয়লার কনভার্জেন্স ট্রান্সফরমেশন সূত্রের নির্দিষ্ট সংখ্যক টার্ম ব্যবহার করে টেইল রিকার্সিভ পদ্ধতিতে π-এর আসন্ন মান বের করবে।
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
চলুন একসাথে প্রথম টার্মটি হিসাব করি।
অসীমের বদলে 0 কে ঊর্ধ্বসীমা ধরে নিলে আমরা পাই:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
প্রতিটি অতিরিক্ত টার্ম আসন্ন মানটিকে আরও উন্নত করবে।
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
লার্নিং অনুশীলনী
