একটি recursive algorithm-এ প্রতিবার ফাংশন নিজেকে কল করলে একটি নতুন ফাংশন কল স্ট্যাক ফ্রেমে যুক্ত হয়, যা অতিরিক্ত মেমরি ব্যবহার করে। এই কারণেই recursion-এর space complexity প্রধানত function call-এর সংখ্যা ও গভীরতার (depth) ওপর নির্ভর করে।

বিস্তারিতভাবে:

• প্রতিটি function call স্ট্যাকে একটি নতুন stack frame তৈরি করে।

• এই ফ্রেমে থাকে local variables, parameters, এবং return address, যেগুলোর জন্য নির্দিষ্ট পরিমাণ মেমরি বরাদ্দ হয়।

• মোট ব্যবহৃত মেমরি recursion-এর সর্বাধিক গভীরতা (maximum recursion depth) অনুসারে বৃদ্ধি পায়।

• ফলে recursive function-এর space complexity সরাসরি function calls-এর সংখ্যা ও স্তর দ্বারা নির্ধারিত হয়।

ভুল বিকল্পগুলো:

• Input size: এটি মূলত time complexity-কে প্রভাবিত করে, stack space-কে নয়।

• Output size: শুধুমাত্র তখনই space প্রভাবিত করে যদি ফলাফলগুলো স্পষ্টভাবে সংরক্ষণ করা হয়।

• Variables inside loops: এগুলো একই stack frame-এ থাকে, তাই recursion-এর মতো অতিরিক্ত stack space ব্যবহার করে না।

অতএব, recursion-এ space complexity-এর প্রধান উৎস হলো function calls।

Greedy Algorithm হলো এমন একটি কৌশল যা প্রতিটি ধাপে স্থানীয়ভাবে সর্বোত্তম (locally optimal) পছন্দ গ্রহণ করে, আশা করা হয় এই ধারাবাহিক নির্বাচনের মাধ্যমে সামগ্রিকভাবে সর্বোত্তম (globally optimal) সমাধানে পৌঁছানো যাবে।

মূল তথ্যসমূহ:

• কার্যপদ্ধতি: Greedy অ্যালগরিদম প্রতিটি ধাপে এমন সিদ্ধান্ত নেয় যা সেই মুহূর্তে সবচেয়ে ভালো মনে হয়, এবং পূর্ববর্তী সিদ্ধান্ত পরিবর্তন না করেই পরবর্তী ধাপ এগিয়ে চলে।

• সর্বোত্তম সমাধান নিশ্চিতে দুটি মূল বৈশিষ্ট্য প্রয়োজন:

  1. Optimal Substructure: একটি সমস্যার সর্বোত্তম সমাধান তার সাবপ্রবলেমগুলোর সর্বোত্তম সমাধান থেকে গঠিত হতে পারে।

     • উদাহরণ: Shortest path problem, যেখানে ছোট ছোট পথে সর্বোত্তম সিদ্ধান্ত নিয়ে পুরো পথের সর্বনিম্ন মান পাওয়া যায়।

  2. Greedy Choice Property: প্রতিটি ধাপে স্থানীয়ভাবে সেরা পছন্দ (locally optimal choice) করলে সেটি শেষ পর্যন্ত গ্লোবাল অপ্টিমাম সমাধানে পৌঁছায়।

ভুল বিকল্পসমূহ:

• ক) Overlapping subproblems: এটি Dynamic Programming-এর বৈশিষ্ট্য, Greedy নয়।

• গ) Divide and Conquer: এটি সমস্যাকে স্বাধীন অংশে ভাগ করে, Greedy এই পদ্ধতি অনুসরণ করে না।

• ঘ) Independent subproblems: এটি DP বা Divide and Conquer-এর জন্য উপযুক্ত, Greedy নয়।

অতএব, Greedy অ্যালগরিদমের কার্যকারিতা নিশ্চিত করতে সমস্যায় থাকতে হবে Optimal Substructure এবং Greedy Choice Property, তাই সঠিক উত্তর খ)।