রিকার্সন

প্রথম অংশঃ

আমার প্রথম স্কুলে ভর্তি পরীক্ষা , ১৯৯৬ সালের ডিসেম্বর মাস । বেবী ক্লাস এ ভর্তির মৌখিক পরীক্ষা । স্পষ্ট মনে আছে আমাকে একটি যোগ করতে দেওয়া হয়েছিলো, যার দুটি সংখ্যাই ছিলো তিন অঙ্কবিশিষ্ট । অবশ্য সংখ্যা দুইটি আমি মনে রাখতে পারি নি ।

যোগ দিয়ে আমি আজকে একটা বড় বিষয় বুঝানোর চেষ্টা করব।

 

 

কিভাবে করলাম ?

প্রথমে ৭+১ = ৮ , লিখলাম ৮ হাতে শূন্য

তারপর ৫+৮ = ১৩, লিখলাম ৩ হাতে ১

এরপর ৭ এর সাথে হাতের এক ৭+১ = ৮

সবশেষে ১+৮ = ৯, লিখলাম ৯

 

এখানে আমাদের কাজটা হলো শেষ অঙ্ক গুলোর সাথে হাতে যা নিয়েছি তা যোগ করা । আর পরেরবার তার আগের অঙ্কটি হবে শেষ অঙ্ক ।

 

সংখ্যা শেষ অঙ্ক হাতে আছে যোগফল লিখতে হবে হাতে থাকবে

১৫৭

৭৮১

১৫

           ০

১৩

৭৮

এখন আমি একটা ফাংশন তৈরি করে ফেলি যার কাজ হলো তিনটি সংখ্যা ইনপুট এ নিবে ও তাদের প্রথম দুইটির শেষ অঙ্কের সাথে তৃতীয় সংখাটি যোগ করে যোগফলের শেষ অংকটি প্রিন্ট করবে ।এখানে ৩য় সংখাটি হলো হাতে রাখা সংখাটি । তাহলে ফাংশনটা হবে এরকম ।

সি কোডঃ

void add (int a, int b, int c)
{
    int x = a%10;
    int y = b%10;
    int sum = x+y+c;
    printf("%d",sum%10);
}

পাইথন কোডঃ

def add (a,b,c):
    x = a%10
    y = b%10
    sum = x+y+c
    print(sum%10, end='')

আমাদের মাথার মধ্যেও এইরকম একটা ফাংশন কাজ করে । কিন্তু এই ফাংশনটা শেষ হয়ে গেলে কিন্তু আমরা পুরাপুরি যোগফল পাব না । আমরা করি কি এই ফাংশন শেষ করার আগে আবার এই ফাংশন কল করি । ব্যাপারটা অনেকটা অদ্ভুদ, জটিলও বটে ।

আর একটু সহজ করে দেই ।

১৫৭ ও ৭৮১ যোগ করতে গেলে আমাদেরকে একটি ফাংশন তিনবার কল করতে হবে ।

সি কোডঃ

add (157,781,0);
add (15,78,0);
add (1,7,1);

পাইথন কোডঃ

add (157,781,0)
add (15,78,0)
add (1,7,1)

যদি ১০ অঙ্কবিশিষ্ট সংখ্যা হয় তবে ১০ বার কল করতে হবে । আমরা লুপ ঘুরায় এই কাজটা করতে পারি কিন্তু তা আমি এখানে করব না ।

এখানে ফাংশনটা যখন শেষ হয়ে যাবে তার আগ মুহূর্তে আমি আবার নতুন মান দিয়ে ফাংশনটা কল করব । নতুন মান বলতে পরবর্তী ধাপের মান । কোডটা হবে এরকম ।

সি কোডঃ

void add (int a, int b, int c)
{
	int x = a%10;
	int y = b%10;
	int sum = x+y+c;
	printf("%d",sum%10);
	add (a/10, b/10 ,sum/10);
}

পাইথন কোডঃ

def add (a,b,c):
	x = a%10
	y = b%10
	sum = x+y+c
	print(sum%10, end='')
	add (a//10, b//10 ,sum//10);

এভাবে এক ফাংশন এর ভিতর সেই ফাংশনকে কল করাকে বলা হয় রিকার্সন । আর ফাংশনটিকে বলা হয় রিকার্সিভ ফাংশন ।

এখানে এই কোড রান করলে থামার সম্ভাবনা নাই । কারন কতক্ষন ফাংশন কল করবে আমরা তার কোনো শর্ত দেইনি।

যখন a ও b এর মান ০ হয়ে যাবে তখন আর কোনো ফাংশন কল করবে না । মানে কোন কাজ করবে না ।

তাহলে সংশোধিত কোড হল

সি কোডঃ

void add (int a, int b, int c)
{
    int x,y,sum;
    if(a!=0 || b!=0)
    {
        x = a%10;
        y = b%10;
        sum = x+y+c;
        printf("%d",sum%10);
        add (a/10, b/10 ,sum/10);
    }
}

পাইথন কোডঃ

def add (a,b,c):
	if a or b: # same as if a != 0 or b != 0
		x = a%10
		y = b%10
		sum = x+y+c
		print(sum%10, end='')
		add (a//10, b//10 ,sum//10);

মজার ব্যাপার হল আউটপুট উলটা আসতেছে । তারপর আবার সব ক্ষেত্রে ঠিকও আসতেছে না (৫৫৫+৫৫৫) । আউটপুট ঠিক করার দায়িত্ব আপনাদের ।

এবার মনে হতে পারে আমরা লুপ দিয়েই তো এই কাজ করতে পারি । আসলেই তাই । লুপ দিয়ে যা করা যায় রিকার্সন দিয়েও তাই করা যায় । কিন্তু রিকার্সনের আসল মজা কি তা আমি একটু পরে আলোচনা করব । তার আগে আপনাদের কিছু কাজ করতে হবে । প্রথমে ঠিক করতে হবে ফাংশনটার কোথায় পরিবরতন করলে আউটপুট উল্টোদিক থেকে সঠিক আসবে । এখন আউটপুট আসতেছে ০১১ ঠিক করলে আউটপুট আসবে ০১১১ । তারপরের কাজ হল লুপ দিয়ে আপনাকে এর আউটপুট ঠিক আনতে হবে । মানে আপনি রিকার্সন দিয়ে না করে লুপ দিয়ে করে দেখবেন ।

কাজটি শেষ করে তারপর পরবর্তি অংশ পড়া শুরু করুন ।

দ্বিতীয় অংশঃ

[প্রথমে একটি বিষয় পরিষ্কার করে ফেলি , ১২৩ একটি সংখ্যা হলে এর ১ম অঙ্ক হলো ১ আর একক স্থানীয় অঙ্ক হলো ৩ ।]

১ম অংশে আমি আপনাদেরকে দুটো কাজ করতে বলেছিলাম প্রথমটি হলো (৫৫৫+৫৫৫) এর জন্য আউটপুট ০১১ আসছিলো, আসলে আসার কথা ০১১১ । এটা ঠিক করার কথা বলা হয়েছিলো । আর ২য় কাজটি হলো লুপ দিয়ে আউটপুট সঠিক নিয়ে আসা । সেক্ষেত্রে (৫৫৫+৫৫৫) এর আউটপুট আসবে ১১১০ । আসাকরি কাজদুটো করে এই পর্ব পরা শুরু করেছেন ।

 

প্রথমে ১ম প্রবলেমটা নিয়ে একটু আলোচনা করি । ১ম প্রবলেমটা সমাধান করার জন্য খুব বেশি পরিবর্তন করতে হবে না । 4 (পাইথনে 2) নং লাইন এ (a!=0 && b!=0) এর পরিবরতে (a+b+c !=0) করে দিলেই সথিক আউটপুট পাওয়া যাবে । একটু চিন্তা করলেই আপনারা এর কারন বুঝতে পারবেন ।

এবার ২য় সমস্যার পুরাপুরি সমাধান । তার আগে আমরা প্রবলেমটা নিয়ে একটু চিন্তা করি । আমরা যখন খাতায় লিখি তখন বাম বা ডান যে কোনো এক দিক দিয়েই লিখতে পারি । কিন্তু প্রোগ্রাম করে আমরা শুধুমাত্র বামপাশ থেকে লিখতে পারি । তাই আমাদের আউটপুট এমন আসছে । কারন আমরা প্রথমে যে অঙ্কটা হিসাব করে বের করি প্রকৃতপক্ষে তা হলো আমাদের যোগফলের শেষ অঙ্ক । এর ফলে আমরা যোগফলের শেষ অঙ্ক প্রথমে প্রিন্ট করছি । কিন্তু আমাদেরকে সবার শেষে হিসাব করা অঙ্ক সবার আগে প্রিন্ট করতে হবে । এক্ষেত্রে প্রথমে আমাদেরকে সম্পূর্ণ কাজ করে সবগুলো মান স্টোর করে রাখতে হবে । তারপর শেষ দিক দিয়ে প্রিন্ট দিতে হবে । লুপ দিয়ে করলে আপনাদের কোড অনেকটা এরকম হওয়া উচিত ।

সি কোডঃ

      a = 555;

      b = 555;

      c = 0;

      while(a+b+c != 0){

          x = a%10;

          y = b%10;

          arr[i]=(x+y+c) %10;

          c = (x+y+c)/10;

          a/=10;

          b/=10;

          i++;

      }

      while(i!=0){

          printf("%d",arr[i-1]);

          i--;

       }

পাইথন কোডঃ

a = 555
b = 555
c = 0
i = 0
arr = []
while a+b+c != 0:
    x = a%10
    y = b%10
    arr  += [(x+y+c) %10]
    c = (x+y+c)//10
    a//=10
    b//=10
    i+=1


while i:
    print(arr[i-1], end='')
    i-=1

দেখা যাচ্ছে যে শেষের ফাংশনটার প্রিন্ট করার কাজ আগে হচ্ছে । আর আমরা দেখতে পাচ্ছি যে শেষের ফাংশনটা যোগফলের ১ম ডিজিট প্রিন্ট করে , আর আমরা এইটাই চাই । ব্যাপারটা আপনারা বুঝে থাকলে রিকার্সন দিয়ে কোডটা করে ফেলুন । দেখবেন লুপের চেয়ে অনেক সোজা । যদি না পারেন তবে দেখে নিন (যেটা আমি চাই না) । আর পারলে মিলিয়ে নিন ।

সি কোডঃ

 void add (int a, int b, int c)

  {

      int x,y,sum;

      if(a+b+c!=0)

      {

          x = a%10;

          y = b%10;

         sum = x+y+c;

          add (a/10, b/10 ,sum/10);

          printf("%d",sum%10);

      }

  }

পাইথন কোডঃ

def add (a,b,c):
	if a+b+c: # same as if a+b+c != 0
		x = a%10
		y = b%10
		sum = x+y+c
		add (a//10, b//10 ,sum//10);
                print(sum%10, end='')

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

 

শেষ অংশঃ

গত দুই পর্বে আমি রিকার্সন এর সাহায্যে একটি প্রবলেম সল্ভ করেছি । আজকের পর্বে আমি রিকার্সন এর বেসিক কিছু বিষয় নিয়ে আলোচনা করব ।

যদি একটি ফাংশন f() যা নিজেই নিজের একটি কল স্টেটমেন্ট অথবা দ্বিতীয় কোন ফাংশনের একটি কল স্টেটমেন্ট দ্বারা f() এ ফিরে আসে তখন f() কে রিকার্সিভ ফাংশন বলে । ফাংশনটি যাতে অনির্দিষ্ট সময় ধরে না চলে তার জন্য কিছু বিষয় মেনে চলা হয় ।

  • এমন কিছু বৈশিষ্ট্য যার জন্য ফাংশনটি আর নিজেকে কল করে না । অর্থাৎ ফাংশনের কিছু আর্গুমেন্ট থাকবে যার জন্য ফাংশনটি আর নিজেকে কল করবে না । একে বেস ভ্যালু বলে ।
  • প্রত্যেক সময়ে যখন ফাংশনটি নিজেকে কল করে তখন ফাংশনের আর্গুমেন্ট বেস ভ্যেলুর নিকটবর্তী হতে থাকবে ।

 

অর্থাৎ রিকার্সন এর ক্ষেত্রে একটি শর্ত লাগবে যার জন্য ফাংশনটি কোন এক সময় টারমিনেট করবে এবং প্রতিবার সেই শর্তের দিকে ফাংশনটি আগাবে ।

মাথা তো পুরোপুরি নষ্ট করে দিলাম মনে হয় । আমরা ফেক্টরিয়াল হিসাবের ফাংশনটি লক্ষ করি ।
সি কোডঃ

 int fact (int n)

  {
      if(n==1)  return 1;

       return n*fact(n-1);

  }

পাইথন কোডঃ

def fact(n):
    if n == 1:
        return 1
    return n * fact(n-1)

fact(5) এর মান প্রিন্ট করা হইলে প্রিন্ট করবে ১২০ ।

এখানে if(n==1)  return 1; এটা হল টার্মিনেট করার শর্ত , যাকে বলে বেস ভ্যালু । এখন এর ভিতর যে ফাংশনটি কল করা হয়েছে তা হল fact(n-1) । অর্থাৎ

fact(5) ফাংশনটি কল করবে fact(4) ফাংশনটিকে

fact(4) ফাংশনটি কল করবে fact(3) ফাংশনটিকে

fact(3) ফাংশনটি কল করবে fact(2) ফাংশনটিকে

fact(2) ফাংশনটি কল করবে fact(1) ফাংশনটিকে

যখন fact(1) ফাংশনটির কাজ শুরু হবে  n==1 এই শর্তটা সত্য হওয়ার জন্য ফাংশনটি 1 রিটার্ন করবে । এই রিটার্ন না করলে অনির্দিষ্ট সময় ধরে প্রোগ্রামটি চলতো । তারপর এই

fact(1),  1 রিটার্ন করবে fact(2) কে

fact(২),  2*fact(1) = 2*1 = 2 রিটার্ন করবে fact(3) কে

fact(3),  3*fact(2) = 3*2= 6  রিটার্ন করবে fact(4) কে

fact(4),  4*fact(3) = 4*6 = 24  রিটার্ন করবে fact(5) কে

আর তাই fact(5) এর মান হবে  5*fact(4) = 5*24 = 120 ।

 

এবার আপনারা বেশি বেশি করে রিকার্সন প্রাকটিস করুন । আর নিচের প্রবলেমগুলো সল্ভ করার চেষ্টা করুন রিকার্সন দিয়ে ।

uva:

  • 10931 – Parity
  • 10035 – Primary Arithmetic
  • 369 – Combinations
  • 10696 – f91

 

মন্তব্য করুন

আপনার ই-মেইল এ্যাড্রেস প্রকাশিত হবে না। * চিহ্নিত বিষয়গুলো আবশ্যক।