Recursion Call Tree

Recursion হলো এমন function যে নিজেই নিজেকে ছোট ছোট অংশের উপর call করে একটা সমস্যার সমাধান করে।

মূল ধারণা

রাশিয়ান nesting doll-এর কথা ভাবুন: সবচেয়ে বড় doll-এর ভেতরে কী আছে জানতে আপনি সেটা খোলেন, একটা ছোট doll পান, আর একই প্রশ্ন আবার করেন। সবচেয়ে ছোট doll-এ (base case) উত্তর জানা থাকে, আর সেখান থেকে উত্তরগুলো ওপরের দিকে return হতে শুরু করে।

fib(n) = fib(n-1) + fib(n-2), যেখানে fib(0) = 0 আর fib(1) = 1। প্রতিটা call একটা call tree-র node। দেখবেন একই sub-problem (যেমন fib(3)) বারবার হিসাব হচ্ছে। Memoization মানে প্রতিটা উত্তর প্রথমবার একটা খাতায় লিখে রাখা, যাতে পরে একই call এলে আর branch না করে খাতা থেকে পড়ে নেওয়া যায়।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

সাধারণ fib: প্রায় O(2n) time complexity, কারণ call tree-র প্রতিটা level-এ call মোটামুটি দ্বিগুণ হয়। Memoized: O(n) time complexity, কারণ প্রতিটা মান একবারই হিসাব হয়, আর memo map ও call stack-এর জন্য O(n) space complexity।