Recursion in JavaScript

রিকারশন জাভাস্ক্রিপ্ট এর একটি সহজ কন্সেপ্ট। যদি কোনো ফাংশন তার নিজের বডিতে নিজেকে কল করে থাকে তাকে রিকারশন বলে। মোটামোটি সব ল্যাঙ্গুয়েজে রিকারশন আছে। চলুন সিম্পল একটা উদাহরণ দিয়ে বোঝা যাক।

// Recursion in javascript
let myFunc = function () {
  myFunc();
};

এখানে একটি ফাংশন কে ফাংশন এক্সপ্রেশন আকারে লেখা হলো এবং তার বডিতে তাকে কল করা হলো। এখানে myFunc গ্লোবাল এ আছে তাই ফাংশন গ্লোবাল এর ডাটা অ্যাক্সেস পাবে তাই আমরা তার বডিতে তাকে কল করতে পারছি। এটা হচ্ছে রিকারশন এর সহজ বিশ্লেষন।

চলুন একটা ব্যবহার দেখিঃ-

আমাদের কে একটা যোগ করতে হবে যেমন 1+2+3+.......+ n পর্যন্ত। তাহলে আমরা ইজিলি এখানে লুপ চালিয়ে করে নিতে পারি। চলুন for loop দিয়ে কাজটা করে ফেলি।

let total = 0;
let n = 3;
for (let i = 0; i <= n; i++) {
  total += i;
}
console.log(total); // total - 6

এখন রিকারশন হলো ফাংশন এর মধ্যে ফাংশন কে কল করা। এই জন্য এই for loop মেথড্‌ থেকে রিকারশন এ পরিবর্তন করতে হলে আমাদেরকে ফাংশনাল ওয়েতে চিন্তা করতে হবে। এখন এখানে লুপ এর প্রতিটি স্টেপে কি হচ্ছে তা আমাদের দেখতে হবে তাহলে আমরা পুরা বেপার টি কে ফাংশনাল ওয়েতে চিন্তা করতে পারব।

0 + 0 = 0                  total = 0 (let)
        0 + 1 = 1
                1 + 2 = 3
                        3 + 3 = 6

এখানে খেয়াল করুন আমরা কিন্তু প্রথমে একটা টোটাল ধরে নিচ্ছি 0। তারপর ১ম স্টেপ এ তার সাথে আমাদের i এর 0 যোগ করছি তারপর ফলাফল হলো 0, তারপর ফলাফল এর সাথে আমাদের i এর মান 1 যোগ করছি তার ফলাফল হলো 1, তারপর ফলাফল এর সাথে আমাদের i এর মান 2 যোগ করছি তার ফলাফল হলো 3, তারপর ফলাফল এর সাথে আমাদের i এর মান 3 যোগ করছি তার ফলাফল হলো 6 । এখানে একটি পেটার্ন তৈরি হয়েছে। এখানে প্রথম মানটি হচ্ছে পূর্বের স্টেট এর টোটাল মান আর দ্বিতীয় স্টেটটি হচ্ছে আমাদের i এর মান। এখানে প্রতিটি স্টেপ হবে একেকটি ফাংশন। এখন এই পেটার্ন অনুযায়ী আমাদেরকে ফাংশন তৈরি করতে হবে।

0 + 0 = 0                  total = 0 (let)
        0 + 1 = 1 >> f(1) i=1
                1 + 2 = 3 >> f(2) i=2
                        3 + 3 = 6 >> f(3) i=3

এখন এখানে যদি প্রতি স্টেপ কে এভাবে ফাংশন দিয়ে বোঝায়, তাহলে এখানে ফলাফল গুলো তো f() দিয়ে প্রকাশ করছি আর দ্বিতীয় এলিমেন্ট কে আমরা দেখতেই পাচ্ছি প্রত্যেকটি i এর মান। আর প্রথমটি হচ্ছে পূর্বের টোটাল তাহলে পূর্বের টোটালকেও ত আমরা f() দিয়ে প্রকাশ করছি। অর্থাৎ যদি একটি ফাংশন এর টোটাল কে এভাবে প্রকাশ করি f(3) তাহলে তার পূর্বের টোটাল ফাংশন কে f(3-1) এভাবে করতে পারি। অথবা f(2) এটাইতো একই তো হলো। সুতরাং আমাদের সর্বশেষ ফর্মুলাটি হবে।

f(i-1) + i = f(i)

এবার চলুন এই ফর্মুলা কাজে লাগিয়ে আমরা ফাংশন তৈরি করি।

function sum(n) {
  return sum(n - 1) + n;
}

কিন্তু এখানে যে sum() ফাংশন রিটার্ন এ আবার নিজেকে কল করছে এখানে তাহলে এটা ইনফিনিটি হয়ে যাবে শুধু ফাংশন কল হতেই থাকবে হতেই থাকবে। একে হ্যান্ডেল করতে হবে।

function sum(n) {
  if (n === 0) {
    return 0;
  } else {
    return sum(n - 1) + n;
  }
}

এবার দেখুন যখন প্রথম বার কল হবে ধরে নিই প্রথম বার ২ দিয়ে কল করলাম তার পর রিটার্ন এ ১ কমে আবার ১ দিয়ে কল হবে তার পর আবার ১ দিয়ে কল হলে রিটার্ন এ ০ দিয়ে কল হবে, কিন্তু তারপর আর আমাদের দরকার নাই তাই আমরা কন্ডিশন দিয়ে দিলাম এখানে n এর মান ০ হলে রিটার্ন করে বের হয়ে আসবে।

এখন যদি আমরা কল করি তাহলে আগের মতো আমরা সেইম আউটপুট পাবো।

console.log(sum(3)); //output - 6

তাহলে আমাদের রিকারশন ফাংশন তৈরি হয়ে গেলো, যে নিজেকেই নিজে কল করছে।

চলুন দেখি এটি কিভাবে রান করছে। এখানে আমরা শুরু করেছিলাম sum(3) দিয়ে।

sum(3)
👉 sum(3-2) + 3
👉 sum(2-1) + 2 + 3
👉 sum(1-1) + 1 + 2 + 3
👉 0 + 1 + 2 + 3 => 6

এখানে যে একটার পর একটি ফাংশন কল হচ্ছে তা কিন্তু ব্রাউজারে কল স্টেক এ একটার উপর একটা বসে যায় এখন এই কল স্টেক এর কিন্তু একটা মেমোরি লিমিট আছে সে কিন্তু তার লিমিট এর বাহিরে গিয়ে ফাংশন কল করতে পারবে না। আপনার যারা কলস্টেক এক্সিকিউশন নিজে জানেন না আমার লেখা আর্টিকেল টি পরে আসতে পারেন।

এখন যদি আমরা একটি ভিজ্যুয়ালাইজ করি আমাদের তৈরি করা রিকারশন ফাংশন টা কি ব্যবহার করে কলস্টেক এ গিয়ে তাহলে বুঝতে পারবেন।

        sum(0) execution context
                  |
                  |
                  |
        sum(n-2) execution context
        sum(n-1) execution context
        sum(n) execution context
        Global execution context
____________________________________________

এভাবে একটার উপর একটা থাকবে যতখন সে লাস্ট ভ্যালু টা পাচ্ছে। কারন আমরা তো প্রতিটি স্টেপ এ এভাবে ফাংশন কে কল করছি। এখন কল স্টেক হোক আর যাই হোক সে তো একটি মেমোরি ব্যবহার করে কাজটি করে থাকে। তাই আমরা এই রিকারশন নিয়ে কাজ করতে গেলে যদি n এর মান অনেক বড় দিয়ে দেই তাহলে কিন্তু একটা সময় পর আমরা এরর পাবো। Uncaught RangeError: Maximum call stack size exceeded যে মেক্সিমাম লিমিট ক্রস। তাই বেশির ভাগ সময় এর রিকারশন কে এরিয়ে চলা হয়। এটি তেমন ব্যবহারও করা হয় না। এটি কোনো পারফোমেন্স অপ্টিমাইজ কোডও নয়।

এখন আমাদের যদি এখন অনেক বড় সংখ্যক সংখ্যা যোগ করতে হয় তখন কি করব।

এখানে একটু ম্যাথমেটিক্‌স ব্যবহার করতে হবে আমার কিন্তু বিভিন্ন সিরিজ এবং ক্যাল্কুলাস এ পড়েছি কিভাবে n সংখ্যক সংখ্যার যোগফল বের করতে হয়।

এখানে যে ফর্মুলাটি অ্যাপ্লাই করতে হবে তা হলো।

//formula: n(n + 1) / 2;
let n = 100000000;
let total = (n * (n + 1)) / 2;
console.log(total); // output - 5000000050000000

একদম চোক্ষের নিমিশেই পেয়ে যাবো। কারন কাজটি আমাদের সিপিইউ ব্যবহার করে কাজটি করবে, এখানে আমরা এই কাজটি for loop দিয়েও করতে পারতাম। কিন্তু তাতে অর অপ্টিমাইজ হতো না আমাদের কে একটি সিঙ্ক্রোনাস বিহেভিয়ার মধ্যে ফেলে অনেক ক্ষন পরে আউটপুট আসতো।

এটিও হলো ফাংশন রিকারশন কন্সেপ্ট। আশা করি ভালো লেগেছে।❤❤