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 না করে খাতা থেকে পড়ে নেওয়া যায়।
n = 5 দিয়ে run করুন, তারপর 7 দিয়ে। call-এর সংখ্যা কত দ্রুত বাড়ে?n দিয়ে memoization-এ যান। কোন node-গুলো বেগুনি হয়, আর সেগুলোর কোনো child নেই কেন?সাধারণ fib: প্রায় O(2n) time complexity, কারণ call tree-র প্রতিটা level-এ call মোটামুটি দ্বিগুণ হয়। Memoized: O(n) time complexity, কারণ প্রতিটা মান একবারই হিসাব হয়, আর memo map ও call stack-এর জন্য O(n) space complexity।