Recursion ও backtracking সহজ উদাহরণে

Recursion মানে একটি function সমস্যার ছোট সংস্করণে নিজেকে ডাকে, যতক্ষণ না সরাসরি উত্তর দেওয়ার মতো সহজ ক্ষেত্রে পৌঁছায়। Backtracking এর ওপর গড়া: একটি পছন্দ করে দেখুন, অনুসন্ধান করুন, এবং পরের পছন্দ চেষ্টা করতে সেটি ফিরিয়ে নিন। দুটিই interview-এ এবং tree, folder ও graph হাঁটা আসল কোডে বারবার আসে।

প্রতিটি recursive function-এর দুটি অংশ

১. Base case: সরলতম ইনপুট, সরাসরি উত্তর। এটি recursion থামায়। ২. Recursive case: সমস্যা ছোট করুন, নিজেকে ডাকুন এবং ফল মিলান।

function factorial(n) {
  if (n <= 1) return 1;            // base case
  return n * factorial(n - 1);     // ছোট সমস্যা
}

Base case না থাকলে বা সমস্যা ছোট না হলে function কখনো শেষ হয় না এবং stack overflow হয়।

Call stack

প্রতিটি কল call stack-এ নিজের variable-সহ আলাদা frame পায়। Base case পর্যন্ত কল জমে, তারপর একটি একটি করে ফেরে। অর্থাৎ recursion O(গভীরতা) memory নেয়। খুব গভীর recursion (যেমন ১,০০,০০০ স্তর) crash করতে পারে, তাই লম্বা শিকলে loop বা স্পষ্ট stack ভাবুন।

Recursive ভাবনার উপায়

প্রতিটি কল মাথায় অনুসরণ করবেন না। বিশ্বাস ব্যবহার করুন:

১. যেকোনো ইনপুটে function কী ফেরত দেয় পরিষ্কার সংজ্ঞায়িত করুন। ২. ধরে নিন ছোট ইনপুটে এটি সঠিক কাজ করে ("recursive leap of faith")। ৩. সেই উত্তরগুলো দিয়ে বর্তমান ইনপুট কীভাবে সমাধান হবে লিখুন। ৪. Base case যোগ করুন।

উদাহরণ: তালিকার যোগফল। sum(list) = প্রথম element + sum(rest); base case: ফাঁকা তালিকায় 0।

পুনরাবৃত্ত কাজ ও memoization

সরল recursion কাজ পুনরাবৃত্তি করতে পারে। ক্লাসিক উদাহরণ:

function fib(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }   // O(2^n)

fib(30) একই মান বহুবার আবার হিসাব করে। Memoization ইতিমধ্যে হিসাব করা ফল জমা রাখে:

function fib(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}
// সময় O(n), space O(n)

Recursion আর memoization মিলে dynamic programming-এর মূল (পরের একটি লেখার বিষয়)।

Tree-তে recursion

Tree স্বভাবতই recursive: tree হলো ছোট tree-কে সন্তান হিসেবে রাখা একটি node।

function height(node) {
  if (node === null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

Backtracking: টেমপ্লেট

Backtracking একটি সিদ্ধান্ত-গাছে সব সম্ভাব্য পছন্দ অনুসন্ধান করে, কিন্তু কোনো পথ বৈধ উত্তরে পৌঁছাতে পারবে না বোঝামাত্র তা ছেড়ে দেয় (pruning)।

function backtrack(state, choices, results) {
  if (isComplete(state)) {
    results.push(copy(state));
    return;
  }
  for (const choice of choices) {
    if (!isValid(state, choice)) continue;   // prune
    apply(state, choice);                    // choose
    backtrack(state, nextChoices, results);  // explore
    undo(state, choice);                     // un-choose (backtrack)
  }
}

তিনটি ধাপ: choose, explore, un-choose।

উদাহরণ ১: subset

function subsets(nums) {
  const results = [], current = [];
  function go(start) {
    results.push([...current]);              // প্রতিটি পথ বৈধ subset
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);                 // choose
      go(i + 1);                             // explore
      current.pop();                         // un-choose
    }
  }
  go(0);
  return results;
}
// 2^n টি subset, তাই সময় O(n * 2^n)

উদাহরণ ২: permutation

function permutations(nums) {
  const results = [], current = [], used = new Array(nums.length).fill(false);
  function go() {
    if (current.length === nums.length) { results.push([...current]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; current.push(nums[i]);
      go();
      current.pop(); used[i] = false;
    }
  }
  go();
  return results;
}
// n! টি permutation

অন্যান্য ক্লাসিক backtracking সমস্যা

Combination, combination sum, N-Queens, Sudoku solver, grid-এ শব্দ খোঁজা, বন্ধনী তৈরি, palindrome partitioning।

ডুপ্লিকেট সামলানো

ইনপুটে পুনরাবৃত্ত মান থাকলে এবং অনন্য ফল চাইলে আগে sort করুন এবং একই স্তরে আগের মানের সমান মান এড়ান (if (i > start && nums[i] === nums[i - 1]) continue;)।

Complexity

Backtracking প্রায়ই exponential: subset O(2ⁿ), permutation O(n!)। এটি কেবল ছোট n-এ গ্রহণযোগ্য (সাধারণত subset-এ প্রায় ২০, permutation-এ ১০ পর্যন্ত)। অবৈধ শাখা আগেভাগে prune করলে ব্যবহারিক বড় পার্থক্য হয়। উপসমস্যা পুনরাবৃত্ত হলে memoization বা dynamic programming-এ যান।

সাধারণ ভুল

• Base case অনুপস্থিত বা ভুল, ফলে অসীম recursion।
• ফলে কপির বদলে একই array reference push করা।
• পছন্দ ফিরিয়ে নিতে ভুলে যাওয়া।
• Prune না করে বিশাল অকেজো শাখা অনুসন্ধান।
• সরল loop আরও স্পষ্ট ও নিরাপদ হলেও recursion ব্যবহার।

অনুশীলনের সমস্যা

Memo-সহ Fibonacci, সংখ্যার ঘাত, Linked list recursive উল্টানো, Subsets, Permutations, Combination Sum, Generate Parentheses, Word Search, N-Queens।

মূল কথা: base case ও ছোট-সমস্যা ধাপ লিখুন, recursion-কে বিশ্বাস করুন, এবং backtracking-এ choose-explore-undo ব্যবহার করুন। আগেভাগে prune করুন এবং কাজ পুনরাবৃত্ত হলে memoization যোগ করুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ১ (মূল প্যাটার্ন): 5 নম্বর (মোট 5)। আগের লেখা: Binary search: প্যাটার্ন, টেমপ্লেট ও সাধারণ ফাঁদ.