Recursive Functions (রিকার্সিভ ফাংশন)

রিকার্সিভ ফাংশন হল এমন একটি ফাংশন যা নিজেই নিজের ডিফিনিশন বা কল (call) করতে থাকে। অর্থাৎ, রিকার্সিভ ফাংশন কোনো নির্দিষ্ট শর্ত পূর্ণ না হওয়া পর্যন্ত নিজের দিকে রিকল (recursive call) করে এবং একটি শর্ত পূর্ণ হলে ফলাফল প্রদান করে এবং ধাপে ধাপে আগের কলগুলোকে রিটার্ন করে।

রিকার্সন (recursion) মূলত সমস্যাগুলোকে ছোট ছোট উপ-সমস্যায় ভাগ করার একটি পদ্ধতি। এটি সাধারণত ডেটা স্ট্রাকচার যেমন ট্রি বা গ্রাফে, অথবা গাণিতিক সমস্যায় যেমন ফ্যাক্টোরিয়াল, ফিবোনাচ্চি সিরিজ ইত্যাদিতে ব্যবহৃত হয়।

রিকার্সিভ ফাংশনের মৌলিক কাঠামো

রিকার্সিভ ফাংশন সাধারণত দুটি গুরুত্বপূর্ণ অংশের সমন্বয়ে গঠিত:

1. বেস কেস (Base Case): রিকার্সন থামানোর শর্ত। যদি বেস কেস না থাকে, তাহলে ফাংশন অনন্তকাল ধরে নিজেকে কল করবে (অথবা ইনফিনিট লুপে চলে যাবে)।
2. রিকল কেস (Recursive Case): এটি সেই অংশ যা ফাংশনকে নিজেকে পুনরায় কল করতে নির্দেশ দেয়, যতক্ষণ না বেস কেস পূর্ণ হয়।

রিকার্সিভ ফাংশনের উদাহরণ

১. ফ্যাক্টোরিয়াল (Factorial)

ফ্যাক্টোরিয়াল একটি সাধারণ রিকার্সিভ সমস্যা। ফ্যাক্টোরিয়াল হল একটি সংখ্যার সমস্ত পূর্ণসংখ্যা গুণফল। যেমন, 5! (ফ্যাক্টোরিয়াল) হল 5 × 4 × 3 × 2 × 1।

ফ্যাক্টোরিয়াল ফাংশনের রিকার্সিভ পদ্ধতি:

সিনট্যাক্স:

program Factorial;
function Fact(n: Integer): Integer;
begin
  if n = 0 then
    Fact := 1  { বেস কেস: 0! = 1 }
  else
    Fact := n * Fact(n - 1);  { রিকল কেস: n! = n * (n-1)! }
end;
var
  num: Integer;
begin
  num := 5;
  writeln('ফ্যাক্টোরিয়াল: ', Fact(num));
end.

এই প্রোগ্রামে:

• বেস কেস: যখন n = 0, তখন Fact := 1।
• রিকল কেস: Fact := n * Fact(n - 1) — এটি ফাংশনটিকে নিজেকে কল করতে বলে, যতক্ষণ না বেস কেস পৌঁছায়।

আউটপুট:

ফ্যাক্টোরিয়াল: 120

২. ফিবোনাচ্চি সিরিজ (Fibonacci Series)

ফিবোনাচ্চি সিরিজে প্রতিটি সংখ্যা আগের দুটি সংখ্যার যোগফল। উদাহরণস্বরূপ, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

ফিবোনাচ্চি সিরিজের রিকার্সিভ পদ্ধতি:

সিনট্যাক্স:

program Fibonacci;
function Fibonacci(n: Integer): Integer;
begin
  if n <= 1 then
    Fibonacci := n  { বেস কেস: Fibonacci(0) = 0, Fibonacci(1) = 1 }
  else
    Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2);  { রিকল কেস }
end;
var
  num: Integer;
begin
  num := 6;
  writeln('ফিবোনাচ্চি সিরিজের ', num, ' তম সংখ্যা: ', Fibonacci(num));
end.

এখানে:

• বেস কেস: Fibonacci(0) = 0, Fibonacci(1) = 1
• রিকল কেস: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

আউটপুট:

ফিবোনাচ্চি সিরিজের 6 তম সংখ্যা: 8

রিকার্সিভ ফাংশনের কার্যপ্রণালী

রিকার্সিভ ফাংশনের কাজ বোঝার জন্য একটি উদাহরণ দেখা যাক:

ধরা যাক, Factorial(3) কল করা হচ্ছে।

1. প্রথমে ফাংশন কল হবে: Factorial(3)
   • 3 * Factorial(2)
2. তারপর Factorial(2) কল হবে:
   • 2 * Factorial(1)
3. তারপর Factorial(1) কল হবে:
   • 1 * Factorial(0)
4. Factorial(0) বেস কেসে পৌঁছাবে এবং 1 রিটার্ন করবে।
5. এবার, রিকার্সিভ কলগুলো একে একে রিটার্ন করবে:
   • Factorial(1) = 1 * 1 = 1
   • Factorial(2) = 2 * 1 = 2
   • Factorial(3) = 3 * 2 = 6

ফলে, আউটপুট হবে 6, যা 3! এর মান।

রিকার্সন এর সুবিধা ও সীমাবদ্ধতা

সুবিধা:

• সরলীকৃত সমাধান: কিছু সমস্যার ক্ষেত্রে রিকার্সন সোজা এবং সহজ সমাধান প্রদান করে, যেমন ট্রি বা গ্রাফ ট্রাভার্সাল।
• ডিভাইড অ্যান্ড কনকুয়ার (Divide and Conquer): বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় ভাগ করে সমাধান করা যায়।

সীমাবদ্ধতা:

• স্ট্যাকের সমস্যা: রিকার্সন খুব গভীর হলে স্ট্যাক ওভারফ্লো হতে পারে, কারণ প্রতিটি রিকার্সিভ কলের জন্য স্ট্যাক ফ্রেম তৈরি হয়।
• কার্যকারিতা: কিছু রিকার্সিভ ফাংশন খুব ধীরগতিতে কাজ করতে পারে, বিশেষ করে যদি পুনরাবৃত্ত কলগুলো খুব বেশি হয় (যেমন, ফিবোনাচ্চি সিরিজের সাধারণ রিকার্সিভ পদ্ধতি)।

সারাংশ

রিকার্সিভ ফাংশন এমন একটি ফাংশন যা নিজেই নিজের কল করে। এটি সমস্যাগুলোকে ছোট ছোট উপ-সমস্যায় ভাগ করার জন্য ব্যবহৃত হয়। ফ্যাক্টোরিয়াল, ফিবোনাচ্চি সিরিজ ইত্যাদি উদাহরণে রিকার্সন কার্যকরভাবে ব্যবহার করা হয়। তবে, রিকার্সনের সঠিক ব্যবহার নিশ্চিত করার জন্য বেস কেস এবং রিকল কেস ঠিকভাবে সংজ্ঞায়িত করা জরুরি।

রিকর্শন (Recursion) হল একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেকে কল (call) করে, এবং এটি সাধারণত সমস্যা সমাধানে ছোট উপ-সমস্যা গুলিকে পুনরাবৃত্তি (repeatedly) সমাধান করার জন্য ব্যবহৃত হয়। রিকার্শন একটি সমস্যার সমাধানকে একই ধরনের ছোট উপ-সমস্যায় ভেঙে দিয়ে সমাধান করে।

রিকার্শনের মৌলিক ধারণা

রিকর্ষনের মূল ধারণা হল, যখন একটি ফাংশন নিজেকে কল করে, তখন সে নিজে থেকে সমস্যাটি সহজভাবে সমাধান করার চেষ্টা করে। এটি বিশেষভাবে তখন ব্যবহারী হয়, যখন কোনো সমস্যা পুনরাবৃত্তি (repeated) গঠনে থাকে বা উপ-সমস্যাগুলিতে একই ধরনের পদক্ষেপ গ্রহণ করা যায়।

রিকর্ষনের একটি গুরুত্বপূর্ণ দিক হল বেস কেস (base case) এবং **রিকার্শন কেস (recursive case)**।

• বেস কেস: এটি সেই শর্ত যেখানে রিকার্শন থামে। যদি বেস কেস না থাকে, তবে রিকার্শন আনলিমিটেড (infinite) হতে পারে।
• রিকার্শন কেস: এটি সেই শর্ত যেখানে ফাংশন নিজেকে পুনরায় কল করে।

রিকার্শন এর ব্যবহার

রিকার্শন এমন কিছু সমস্যায় কার্যকরী হয়, যেগুলির সমাধানে একই ধরণের সমস্যা বার বার উৎপন্ন হয়। কিছু সাধারণ ব্যবহারিক ক্ষেত্রে রিকার্শন ব্যবহৃত হয়:

1. ফ্যাক্টোরিয়াল (Factorial) গণনা:
   ফ্যাক্টোরিয়াল হল একটি সংখ্যার সব পূর্ণসংখ্যা গুণফল। এটি রিকার্শনের মাধ্যমে খুব সহজে গণনা করা যেতে পারে।

   উদাহরণ:

   • ফ্যাক্টোরিয়াল: \( n! = n \times (n-1) \times (n-2) \times \dots \times 1 \)
   • ফ্যাক্টোরিয়াল রিকার্শন ফাংশন: \( n! = n \times (n-1)! \)

program FactorialExample;
function Factorial(n: Integer): Integer;
begin
  if n = 0 then
    Factorial := 1  // বেস কেস: 0! = 1
  else
    Factorial := n * Factorial(n - 1);  // রিকার্শন কেস
end;

begin
  writeln('Factorial of 5 is ', Factorial(5));  // আউটপুট: 120
end.

এখানে:

• বেস কেস: যদি \( n = 0 \), তখন ফ্যাক্টোরিয়াল ১ ফেরত দেয়া হয়।
• রিকার্শন কেস: যদি \( n > 0 \), তবে ফাংশন নিজেকে কল করে এবং \( n \times (n-1)! \) হিসাব করে।

2. ফিবোনাচ্চি (Fibonacci) সিরিজ:
   ফিবোনাচ্চি সিরিজের প্রতিটি সংখ্যা পূর্ববর্তী দুইটি সংখ্যার যোগফল। এটি রিকার্শনের মাধ্যমে সমাধান করা যায়।

   উদাহরণ:

   • ফিবোনাচ্চি সিরিজের সূত্র: \( F(n) = F(n-1) + F(n-2) \)
   • বেস কেস: \( F(0) = 0, F(1) = 1 \)

program FibonacciExample;
function Fibonacci(n: Integer): Integer;
begin
  if n = 0 then
    Fibonacci := 0  // বেস কেস
  else if n = 1 then
    Fibonacci := 1  // বেস কেস
  else
    Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2);  // রিকার্শন কেস
end;

begin
  writeln('Fibonacci of 6 is ', Fibonacci(6));  // আউটপুট: 8
end.

এখানে:

• বেস কেস: \( F(0) = 0 \) এবং \( F(1) = 1 \)
• রিকার্শন কেস: \( F(n) = F(n-1) + F(n-2) \)

3. লিঙ্কড লিস্ট (Linked List) Traversal:
   একটি লিঙ্কড লিস্টের উপাদানগুলোকে রিকার্শনের মাধ্যমে পর্যায়ক্রমে দেখা বা প্রক্রিয়া করা যায়।

program LinkedListTraversal;
type
  NodePtr = ^Node;
  Node = record
    data: Integer;
    next: NodePtr;
  end;

var
  head: NodePtr;

procedure PrintList(node: NodePtr);
begin
  if node <> nil then
  begin
    writeln(node^.data);  // নোডের মান প্রিন্ট করা
    PrintList(node^.next);  // রিকার্শন: পরবর্তী নোডে কল করা
  end;
end;

begin
  { এখানে লিঙ্কড লিস্টের প্রাথমিক নোডগুলি তৈরি করা হয় }
  new(head);
  head^.data := 1;
  new(head^.next);
  head^.next^.data := 2;
  new(head^.next^.next);
  head^.next^.next^.data := 3;
  head^.next^.next^.next := nil;
  
  PrintList(head);  // আউটপুট: 1, 2, 3
end.

এখানে:

• বেস কেস: যদি নোডের পরবর্তী অংশ nil হয়, তখন রিকার্শন থেমে যায়।
• রিকার্শন কেস: যদি নোডের পরবর্তী অংশ nil না হয়, তাহলে পরবর্তী নোডে রিকার্শন কল করা হয়।

রিকার্শন এর সুবিধা

1. সহজ কোড: অনেক জটিল সমস্যা সহজেই রিকার্শন দিয়ে সমাধান করা যায়। উদাহরণস্বরূপ, ফ্যাক্টোরিয়াল বা ফিবোনাচ্চি সিরিজ।
2. প্রাকৃতিক উপস্থাপনা: অনেক সমস্যা যেমন গাছ (Tree) বা গ্রাফ (Graph) কাঠামো, রিকার্শন দিয়ে খুব প্রাকৃতিকভাবে উপস্থাপন করা যায়।
3. ডাটা স্ট্রাকচারগুলির জন্য উপকারী: যেমন লিঙ্কড লিস্ট, ট্রি ইত্যাদি ডাটা স্ট্রাকচার গুলির জন্য রিকার্শন খুবই উপকারী।

রিকার্শন এর সীমাবদ্ধতা

1. স্ট্যাক ওভারফ্লো: যদি রিকার্শন সঠিকভাবে থামানো না হয়, তাহলে এটি স্ট্যাকের সীমা পার করতে পারে, যা প্রোগ্রামের ক্র্যাশ বা স্ট্যাক ওভারফ্লো ঘটাতে পারে।
2. অতিরিক্ত মেমরি ব্যবহার: প্রতিটি রিকার্শন কলের জন্য মেমরির প্রয়োজন হয়, যা অনেক রিকার্শন কলের ফলে মেমরি বেশি খরচ হতে পারে।

সারাংশ

রিকার্শন হল একটি শক্তিশালী প্রোগ্রামিং কৌশল যা একটি ফাংশনকে নিজেকে কল করতে দেয়। এটি সমস্যা সমাধানের একটি কার্যকরী উপায়, বিশেষ করে সেইসব সমস্যা যেখানে সমস্যা এবং তার উপ-সমস্যাগুলি একই ধরনের। তবে, এটি ব্যবহার করার সময় বেস কেস ঠিকভাবে নির্ধারণ করা এবং স্ট্যাক ওভারফ্লো এড়াতে সতর্ক থাকা প্রয়োজন।

Recursive Functions (পুনরাবৃত্তি ফাংশন) হল এমন ফাংশন যা নিজেকে কল করে। এটি সমস্যার সমাধানকে ছোট ছোট সাব-সমস্যায় বিভক্ত করে এবং এগুলি একে একে সমাধান করে। সাধারণত পুনরাবৃত্তি ব্যবহৃত হয় এমন সমস্যাগুলিতে যেখানে সমস্যাটি আরও ছোট আকারে একই ধরণের সমস্যায় বিভক্ত করা যায়।

এখানে, আমরা Recursion এবং Recursive Function এর ব্যবহার দেখব, কিছু সমস্যা সমাধানের উদাহরণ সহ।

Recursion এর মৌলিক কাঠামো

একটি রিকর্সিভ ফাংশনের সাধারণ কাঠামো হলো:

1. Base Case: এটি হলো ফাংশনটির সেরা বা শেষ অবস্থা, যেখানে পুনরাবৃত্তি থামবে। যদি base case না থাকে, তবে রিকর্সন অবিরাম চলে যাবে।
2. Recursive Case: এখানে ফাংশনটি নিজেকে কল করে, সাধারণত সমস্যাটি আরও ছোট আকারে সমাধান করা হয়।

প্যাসক্যালের একটি রিকর্সিভ ফাংশনের উদাহরণ

ফ্যাক্টোরিয়াল (Factorial) হিসাব করা

ফ্যাক্টোরিয়াল হল এমন একটি সংখ্যা যা ১ থেকে ঐ সংখ্যাটি পর্যন্ত সব সংখ্যার গুণফল। উদাহরণস্বরূপ, 5 এর ফ্যাক্টোরিয়াল হলো:

5! = 5 × 4 × 3 × 2 × 1 = 120

এই সমস্যাটি রিকর্সিভভাবে সমাধান করা যায়:

• Base case: n = 0 হলে, ফ্যাক্টোরিয়াল হবে 1।
• Recursive case: n! = n × (n-1)!

ফ্যাক্টোরিয়াল ফাংশন প্যাসক্যালের মাধ্যমে

program FactorialExample;
function Factorial(n: Integer): Integer;
begin
  if n = 0 then
    Factorial := 1  { Base case: 0! = 1 }
  else
    Factorial := n * Factorial(n - 1);  { Recursive case: n! = n * (n-1)! }
end;

var
  number: Integer;
begin
  writeln('Enter a number: ');
  readln(number);
  writeln('Factorial of ', number, ' is: ', Factorial(number));
end.

এখানে, Factorial ফাংশনটি নিজেকে কল করে এবং ধীরে ধীরে n এর মান কমায় যতক্ষণ না n = 0 হয়ে যায়। এটি তখন 1 রিটার্ন করে, এবং তারপরে রিকর্সিভভাবে ফ্যাক্টোরিয়াল হিসাব করা হয়।

ফিবোনাচ্চি সিরিজ (Fibonacci Sequence)

ফিবোনাচ্চি সিরিজে পরবর্তী সংখ্যা হলো পূর্ববর্তী দুটি সংখ্যার যোগফল। প্রথম দুটি সংখ্যা হলো 0 এবং 1, তারপর পরবর্তী সংখ্যা হবে 0 + 1 = 1, তারপর 1 + 1 = 2, তারপর 1 + 2 = 3, ইত্যাদি।

এটি রিকর্সিভভাবে হিসাব করা যায়:

• Base case: Fib(0) = 0, Fib(1) = 1
• Recursive case: Fib(n) = Fib(n-1) + Fib(n-2)

ফিবোনাচ্চি ফাংশন প্যাসক্যালের মাধ্যমে

program FibonacciExample;
function Fibonacci(n: Integer): Integer;
begin
  if n = 0 then
    Fibonacci := 0  { Base case: Fib(0) = 0 }
  else if n = 1 then
    Fibonacci := 1  { Base case: Fib(1) = 1 }
  else
    Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2);  { Recursive case }
end;

var
  number: Integer;
begin
  writeln('Enter a number: ');
  readln(number);
  writeln('Fibonacci of ', number, ' is: ', Fibonacci(number));
end.

এই ফাংশনটি Fibonacci ফাংশনটিকে রিকর্সিভভাবে কল করে এবং Fibonacci সিরিজের মান বের করে।

রিকর্সিভ ফাংশন এবং সমস্যা সমাধান

রিকর্সিভ ফাংশন সাধারণত এমন সমস্যাগুলির সমাধানে ব্যবহৃত হয় যেখানে:

• সমস্যা ছোট ছোট সাব-সমস্যায় বিভক্ত হতে পারে।
• সমস্যার সমাধান একটি সাধারণ রুল বা সূত্র দিয়ে করা যায় (যেমন ফ্যাক্টোরিয়াল, Fibonacci, গাছ বা গ্রাফ ট্রাভার্সাল)।

এগুলো কিছু উদাহরণ যেখানে রিকর্সিভ সমাধান প্রযোজ্য হতে পারে:

• হ্যানি-কম্বিনেটরি সমস্যা (Recursion in combinatorial problems): যেমন পাসক্যাল ট্রায়াঙ্গল (Pascal's Triangle), রূপান্তর (permutation), বা সমন্বয় (combination) গণনা করা।
• বিনারি গাছ বা ট্রি ট্রাভার্সাল (Binary tree or tree traversal): গাছের সব নোডের উপর পুনরাবৃত্তি করা।
• ডিভাইড অ্যান্ড কনকার (Divide and Conquer): যেমন Merge Sort বা Quick Sort অ্যালগরিদমগুলি রিকর্সিভ পদ্ধতিতে কাজ করে।

সীমাবদ্ধতা ও কার্যকারিতা

1. স্ট্যাক ওভারফ্লো: যেহেতু রিকর্সন অনেক বার ফাংশন কল করতে পারে, তাই এটি স্ট্যাক ওভারফ্লো ঘটাতে পারে যদি প্রোগ্রামের গভীরতা খুব বেশি হয়।
2. কার্যকারিতা: কিছু ক্ষেত্রে রিকর্সিভ সমাধান ইটারেটিভ সমাধানের তুলনায় কম কার্যকরী হতে পারে, কারণ অনেক সময় রিকর্সিভ ফাংশনগুলো পুনরায় একই গণনা করে (যেমন ফিবোনাচ্চি)। এ ধরনের সমস্যা এড়ানোর জন্য মেমোইজেশন (memoization) বা ডাইনামিক প্রোগ্রামিং ব্যবহার করা যেতে পারে।

সারাংশ

রিকর্সন একটি শক্তিশালী টুল যা প্রোগ্রামিংয়ে সমস্যাগুলির সমাধানকে ছোট ছোট অংশে বিভক্ত করে। রিকর্সিভ ফাংশনগুলি সাধারণত সোজা ও সংক্ষিপ্ত কোড লিখতে সাহায্য করে, তবে এগুলোর সীমাবদ্ধতা যেমন স্ট্যাক ওভারফ্লো এবং কার্যকারিতা নিয়ে চিন্তা করা প্রয়োজন। ফ্যাক্টোরিয়াল এবং ফিবোনাচ্চি সিরিজের মত উদাহরণগুলিতে রিকর্সন ব্যবহার করা অত্যন্ত সহজ এবং কার্যকর।

এখানে প্যাসক্যাল প্রোগ্রামে Factorial, Fibonacci এবং Tower of Hanoi সমস্যার সমাধানের উদাহরণ দেওয়া হল। এগুলি সাধারণ রিকার্সিভ সমস্যা, যেখানে একই ফাংশন নিজেই নিজেকে পুনরায় কল করে।

1. Factorial উদাহরণ

Factorial একটি সংখ্যার গুণফল, যা 1 থেকে ঐ সংখ্যা পর্যন্ত সব সংখ্যা গুণ করে পাওয়া যায়। উদাহরণস্বরূপ, 5 এর ফ্যাক্টোরিয়াল হলো 5 × 4 × 3 × 2 × 1 = 120।

Factorial রিকার্সিভ ফাংশন:

program FactorialExample;
var
  num: Integer;
  
function Factorial(n: Integer): Integer;
begin
  if n = 0 then
    Factorial := 1  { 0 এর ফ্যাক্টোরিয়াল ১ }
  else
    Factorial := n * Factorial(n - 1);  { রিকার্সিভ কল }
end;

begin
  writeln('Enter a number: ');
  readln(num);
  writeln('Factorial of ', num, ' is ', Factorial(num));
end.

ব্যাখ্যা: এই প্রোগ্রামে, Factorial ফাংশনটি রিকার্সিভভাবে নিজেকে কল করে, যতক্ষণ না n শূন্য হয়। তখন এটি 1 ফেরত দেয়।

2. Fibonacci উদাহরণ

Fibonacci সিরিজ এমন একটি সংখ্যা সিরিজ যেখানে প্রতিটি সংখ্যাটি তার পূর্ববর্তী দুটি সংখ্যার যোগফল। Fibonacci সিরিজের প্রথম দুইটি সংখ্যা 0 এবং 1। উদাহরণস্বরূপ, Fibonacci সিরিজ হলো: 0, 1, 1, 2, 3, 5, 8, 13, ...

Fibonacci রিকার্সিভ ফাংশন:

program FibonacciExample;
var
  n, i: Integer;

function Fibonacci(n: Integer): Integer;
begin
  if n <= 1 then
    Fibonacci := n  { 0 এবং 1 এর জন্য Fibonacci সিরিজ }
  else
    Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2);  { রিকার্সিভ কল }
end;

begin
  writeln('Enter a number: ');
  readln(n);
  writeln('Fibonacci series up to ', n, 'th term:');
  for i := 0 to n - 1 do
    writeln(Fibonacci(i));
end.

ব্যাখ্যা: এই প্রোগ্রামে, Fibonacci ফাংশনটি রিকার্সিভভাবে Fibonacci সিরিজের নির্দিষ্ট অবস্থান পর্যন্ত গননা করে।

3. Tower of Hanoi উদাহরণ

Tower of Hanoi একটি ক্লাসিক পাজল যেখানে তিনটি খুঁটি এবং বিভিন্ন আকারের ডিস্ক দেওয়া থাকে। উদ্দেশ্য হলো ডিস্কগুলো একটি খুঁটিতে স্থানান্তর করা, তবে এটি করতে হলে কয়েকটি শর্ত পালন করতে হবে:

• একবারে শুধু একটি ডিস্ক সরানো যাবে।
• বড় ডিস্ক ছোট ডিস্কের উপর রাখা যাবে না।
• ডিস্কগুলো স্থানান্তর করার জন্য তিনটি খুঁটি ব্যবহার করতে হবে।

Tower of Hanoi রিকার্সিভ ফাংশন:

program TowerOfHanoi;
  
procedure MoveDisks(n: Integer; fromPeg, toPeg, auxPeg: Char);
begin
  if n = 1 then
    writeln('Move disk 1 from ', fromPeg, ' to ', toPeg)
  else
  begin
    MoveDisks(n - 1, fromPeg, auxPeg, toPeg);  { Step 1: Move n-1 disks from source to auxiliary peg }
    writeln('Move disk ', n, ' from ', fromPeg, ' to ', toPeg);  { Step 2: Move the nth disk to target peg }
    MoveDisks(n - 1, auxPeg, toPeg, fromPeg);  { Step 3: Move n-1 disks from auxiliary peg to target peg }
  end;
end;

var
  n: Integer;

begin
  writeln('Enter the number of disks: ');
  readln(n);
  writeln('The moves involved are: ');
  MoveDisks(n, 'A', 'C', 'B');  { A, C, B are the names of the source, destination, and auxiliary pegs }
end.

ব্যাখ্যা: এখানে MoveDisks ফাংশনটি রিকার্সিভভাবে ডিস্কগুলো একটি খুঁটি থেকে অন্য খুঁটিতে স্থানান্তর করতে সাহায্য করে। প্রথমে, এটি n-1 ডিস্ককে সহায়ক খুঁটিতে স্থানান্তর করে, তারপর n তম ডিস্কটি লক্ষ্য খুঁটিতে স্থানান্তর করে এবং আবার n-1 ডিস্ককে সহায়ক খুঁটিতে স্থানান্তর করে।

সারাংশ

• Factorial: এটি একটি সংখ্যার গুণফল, যা রিকার্সিভভাবে গননা করা হয়।
• Fibonacci: প্রতিটি পরবর্তী সংখ্যা তার পূর্ববর্তী দুটি সংখ্যার যোগফল, যা রিকার্সিভভাবে পাওয়া যায়।
• Tower of Hanoi: তিনটি খুঁটি এবং ডিস্কগুলির মাধ্যমে একটি নির্দিষ্ট শর্ত মেনে ডিস্ক স্থানান্তর করা হয়, যা রিকার্সিভভাবে সমাধান করা হয়।

এই তিনটি সমস্যা রিকার্সিভ ধারণা ব্যবহারের উপযুক্ত উদাহরণ এবং এগুলি প্রোগ্রামিংয়ের মৌলিক ধারণা শেখানোর জন্য ভালো উদাহরণ।

Recursion এবং Iteration উভয়ই সমস্যা সমাধানে ব্যবহৃত দুটি মৌলিক কৌশল। উভয়ের মধ্যে প্রধান পার্থক্য হল যে recursion একটি সমস্যাকে ছোট অংশে বিভক্ত করে নিজেই নিজেকে কল করে এবং iteration একটি লুপের মাধ্যমে একই কাজ বারবার সম্পন্ন করে। এই দুটি পদ্ধতি বিভিন্ন পরিস্থিতিতে বিভিন্নভাবে কার্যকরী হতে পারে।

১. Recursion (পুনরাবৃত্তি)

Recursion হল একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেকে কল করে। এটি সাধারণত সমস্যাকে ছোট ছোট সাব-প্রব্লেমে ভাগ করার জন্য ব্যবহৃত হয়, যেখানে প্রতিটি সাব-প্রব্লেম নিজেই একটি পুনরাবৃত্তি হতে পারে। একটি বেস কেস বা অবসান শর্ত থাকা উচিত যাতে পুনরাবৃত্তির প্রক্রিয়া থেমে যায়।

Recursion এর উদাহরণ:

function Factorial(n: Integer): Integer;
begin
  if n = 0 then
    Factorial := 1
  else
    Factorial := n * Factorial(n - 1);
end;

এখানে, Factorial ফাংশনটি নিজেকে কল করছে n - 1 এর মাধ্যমে, যতক্ষণ না n = 0 হয়, যেখানে ফাংশনটি ১ রিটার্ন করে এবং পুনরাবৃত্তির প্রক্রিয়া থেমে যায়।

Recursion এর বৈশিষ্ট্য:

• প্রাকৃতিকভাবে পুনরাবৃত্তি: যখন একটি সমস্যা প্রকৃতপক্ষে পুনরাবৃত্তির মাধ্যমে সমাধান করা যায়।
• স্ট্যাক ব্যবহার: প্রতিটি ফাংশন কলের জন্য স্ট্যাক ফ্রেম তৈরি হয়, যার কারণে গভীর পুনরাবৃত্তির ক্ষেত্রে স্ট্যাক ওভারফ্লো হতে পারে।
• কোডের পরিস্কারতা: কিছু সমস্যা যেমন ফ্যাক্টরিয়াল বা ফিবোনাচ্চি সিরিজ রিকার্সিভ পদ্ধতিতে সহজ এবং পরিস্কারভাবে লেখা যায়।

Recursion এর সুবিধা:

• সহজভাবে কিছু সমস্যা সমাধান করা যায় যেমন গাছের ট্রাভার্সাল, ফ্যাক্টরিয়াল হিসাব করা।
• কোড ছোট এবং প্রাকৃতিক হতে পারে।

Recursion এর অসুবিধা:

• স্ট্যাক মেমোরি সীমিত, অতিরিক্ত গভীর পুনরাবৃত্তি স্ট্যাক ওভারফ্লো ঘটাতে পারে।
• কিছু সমস্যা সমাধানে recursion কম কার্যকরী হতে পারে, কারণ এটি অনেক বেশি ফাংশন কলের কারণে অপ্রয়োজনীয়ভাবে সময় নষ্ট করে।

২. Iteration (পুনরাবৃত্তি)

Iteration হল এমন একটি পদ্ধতি যেখানে একটি কাজ একাধিকবার সম্পন্ন করার জন্য একটি লুপ ব্যবহার করা হয়। এটি সাধারণত সমস্যা সমাধান করার জন্য ফোর-লোপ, হোয়াইল-লোপ ইত্যাদি ব্যবহার করে কাজটি পুনরাবৃত্তি করতে ব্যবহৃত হয়।

Iteration এর উদাহরণ:

function Factorial(n: Integer): Integer;
var
  i, result: Integer;
begin
  result := 1;
  for i := 1 to n do
    result := result * i;
  Factorial := result;
end;

এখানে, Factorial ফাংশনটি একটি লুপ ব্যবহার করে ফ্যাক্টরিয়াল হিসাব করছে। এখানে পুনরাবৃত্তি লুপের মাধ্যমে হচ্ছে, যা প্রতিটি সংখ্যার জন্য গুণফল হিসাব করে।

Iteration এর বৈশিষ্ট্য:

• লুপ ব্যবহার: Iteration সাধারণত একটি নির্দিষ্ট সংখ্যক পুনরাবৃত্তি করার জন্য একটি লুপ ব্যবহার করে।
• মেমোরি ব্যবস্থাপনা: স্ট্যাক ব্যবহার না হওয়ার কারণে এটি বেশি মেমোরি খরচ করে না এবং সাধারণত বেশি কার্যকরী।
• তুলনামূলকভাবে বেশি দক্ষ: অধিকাংশ সময় iteration recursion এর তুলনায় দ্রুত এবং বেশি কার্যকরী হতে পারে।

Iteration এর সুবিধা:

• কম মেমোরি খরচ: স্ট্যাকের ব্যবহার না হওয়ার কারণে এটি কম মেমোরি খরচ করে।
• দ্রুত কার্যকারিতা: অধিকাংশ সময় iteration দ্রুত কাজ করে কারণ এতে পুনরাবৃত্তির জন্য অতিরিক্ত ফাংশন কল হয় না।

Iteration এর অসুবিধা:

• কিছু সমস্যায় iteration কোডটিকে জটিল এবং কম প্রাকৃতিক হতে পারে, বিশেষত যখন সমস্যা অনেক ছোট ছোট সাব-প্রব্লেমে ভাগ করা সম্ভব হয়।
• কিছু সমস্যা সমাধানে iteration কৌশলটি পড়তে এবং বোঝতে কঠিন হতে পারে।

৩. Recursion vs Iteration: তুলনা

সারাংশ

• Recursion এবং Iteration উভয়ই সমস্যা সমাধানে ব্যবহৃত পদ্ধতি, তবে তাদের মধ্যে মূল পার্থক্য হল, recursion নিজেই নিজেকে কল করে কাজ করে এবং iteration লুপের মাধ্যমে কাজ সম্পন্ন করে।
• Recursion সাধারণত সহজ এবং প্রাকৃতিকভাবে কিছু সমস্যা সমাধান করতে সাহায্য করে, তবে এটি মেমোরি এবং কার্যকারিতার দিক থেকে সীমাবদ্ধ হতে পারে।
• Iteration অধিকাংশ সময় অধিক কার্যকরী এবং কম মেমোরি ব্যবহার করে, কিন্তু কখনো কখনো কোডটি কম প্রাকৃতিক এবং বেশি জটিল হতে পারে।

আপনার সমস্যা বা কোডের প্রেক্ষিতে এই দুই পদ্ধতির যেকোনো একটিকে বেছে নিন, এবং এটি পছন্দের উপর নির্ভর করবে।