রিকার্সিভ কল

আমরা অনেক প্রোগ্রামের প্রয়োজনে বিভিন্ন সময় রিকার্শন ব্যবহার করে থাকি যেমন – কোন নাম্বারের ফ্যাক্টোরিয়াল বের করা, ফিবোনাচ্চি/ফিবোনাক্কি নাম্বার বের করা, GCD নাম্বার বের করা, ইত্যাদি। কিন্তু রিকার্শনের মাধ্যমে একটা নাম্বারের জন্য কোন রেজাল্ট পাওয়ার জন্য আমাদের লেখা ফাংশনটা মোট কয়বার কল হচ্ছে সেটা বের করি না, কিংবা বের করার দরকার হয় না। কিন্তু মাঝে মাঝে কিছু প্রোগ্রামিং কনটেস্ট অথবা অনলাইন জাজগুলোতে এইরকম প্রবলেম দেখা যায়। কিছুদিন আগে URI Online Judge এ একটা প্রবলেম সলভ করার সময় আমি এই সমস্যায় পড়েছিলাম। ঐই প্রবলেমে দুইটা কাজ ছিলঃ ১। একটা ইনপুট নাম্বারের ফিবোনাচ্চি নাম্বার বের করা এবং ২। ঐই নাম্বারের ফিবোনাচ্চি বের করার জন্য মোট কতবার ফাংশনটা কল হয়েছে সেটা বের করা । এই পোষ্টটা লেখার প্রধান উদ্দেশ্য হল ফিবোনাচ্চি নাম্বার বের করার সময় একটা ফাংশন মোট কতবার কল হয় সেটা দেখা এবং C/C++ এবং Java তে কিভাবে ইম্পিমেন্ট করতে হত সেটা শিখা।
ফিবোনাচ্চি নাম্বার বের করার সূত্র হলঃ

উপরের ছবি থেকে আমরা দেখছি যখন নাম্বারটা 0 (শূন্য) এবং 1 তখন আমরা সরাসরি রেজাল্ট পাচ্ছি এবং ফাংশনটা একবারও রিকার্সিভ কল হচ্ছে না। তাই আমরা আমাদের ফাংশনে (যেটা দিয়ে আমরা রিকার্সিভ কলের সংখ্যাটা গুনব) 0 এবং 1 এর জন্য 0 রিটার্ন করতে পারি।

ছবিটি URI Online Judge থেকে নেওয়া হয়েছে

যখন নাম্বারটা 1 থেকে বড় তখন আমাদেরকে গুনতে হবে মোট কয়বার ফাংশনটা কল হচ্ছে। উপরের ছবিতে আমরা দেখতে পারছি মোট ৮ বার কল হয়েছে। কিভাবে?

১। ইনপুট ৪ কল দিয়েছে F(৩) এবং F(২) কেঃ এই ধাপে কল হল ২টা
২। এরপর F(৩) কল দিয়েছে F(২) এবং F(২) কে, আবার F(২) [যেটা ৪ এর কলে পেয়েছি] কল করছে F(১) এবং F(০) কে, এই ধাপে কল হল ৪ টা।
৩। F(২) [যেটা F(৩) এর কলে পেয়েছি] সেটা কল করছে F(১) এবং F(০) কে, এই ধাপে কল হল ২ টা।
সর্বমোট কলঃ ২ + ৪ + ২ = ৮।

উপরের ছবি থেকে আমরা দেখতে পাই একটা নাম্বার সমসময় এর পূর্বের দুইটা নাম্বারকে কল করছে। এই থেকে আমরা বলতে পারি একটা নাম্বারের জন্য একটা ফাংশনকে কল করার সংখ্যা এর পূর্বের দুইটা নাম্বারের কলের সংখ্যা + ২।
উদাহরনঃ

call(0) = 0
call(1) = 0
call(2) = call(0) + call(1) + 2 = 0 + 0 + 2 = 2
call(3) = call(2) + call(1) + 2 = 0 + 2 + 2 = 4
call(4) = call(3) + call(2) + 2 = 4 + 2 + 2 = 8
call(5) = call(4) + call(3) + 2 = 8 + 4 + 2 = 14

তাহলে আমরা লিখতে পারিঃ

call(n) = call(n-1) + call(n-2) + 2

সম্পূর্ন ফাংশনঃ

int call(int n)
{
    if(n == 0 || n == 1)
    {
        return 0;
    }
    else
    {
        return call(n-1)+call(n-2)+2;
    }
}

C/C++:

#include <bits/stdc++.h>
using namespace std;

int call(int n)
{
    if(n == 0 || n == 1)
    {
        return 0;
    }
    else
    {
        return call(n-1)+call(n-2)+2;
    }
}

int main()
{
    int n;
    while(scanf("%d", &n) == 1)
    {
        printf("Total calls = %d\n", call(n));
    }
    return 0;
}

Java:

import java.util.Scanner;

public class Main
{
	static int call(int n)
	{
		if(n == 0 || n == 1)
		{
			return 0;
		}
		else
		{
			return call(n-1) + call(n-2) + 2;
		}
	}

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int n;
		while(sc.hasNext())
		{
			n = sc.nextInt();
			System.out.println("Total calls: " + call(n));
		}
	}
}

এই সম্পর্কিত প্রোগ্রামিং সমস্যাঃ
1. Fibonacci, How Many Calls? [URI – 1029]

আশাকরি আজকের পোষ্টটা বুঝতে আপনাদের কোন সমস্যা হয়নি।

মান অদলবদল করা

কম্পিউটার প্রোগ্রামিং এ সোয়াপ (swap) বলতে দুইটা ভ্যারিয়েবল নিজেদের মান অদলবদল করাকে বুঝায়। কিছু কিছু প্রোগ্রাম আছে যেগুলোতে ভ্যারিয়েবলের মান অদলবদল করার প্রয়োজন হয়। এই পোষ্টে আমরা ভ্যারিয়েবলের মান অদলবদল করার কয়েকটা পদ্ধতি শিখবঃ

কখন মান পরিবর্তন করার প্রয়োজন হয়?
ধরুন আমরা নিচের কোডটা লিখলামঃ

int a, b, sum = 0;
cin>>a>>b;
for(int i = a; i <= b; i++)
{
	sum += i;
}
cout<<sum<<endl;

আমাদের কোডের for লুপ কাজ করার জন্য অবশ্যই a এর মান b থেকে ছোট হতে হবে। a এর মান যদি b থেকে বড় হয় তাহলে আমাদের for লুপটা কাজ করবে না। যেহেতু a এবং b এর মান ইনপুটের উপর নির্ভর করে সেহেতু আমাদেরকে এমনভাবে কোড লিখতে হবে যেন আমাদের কোডটা সবসময় কাজ করে। এই কাজটা আমরা a এবং b এর মান অদলবদল করার মাধ্যমে করতে পারি।
আজকে আমরা ভ্যারিয়েবলের মান অদলবদল করার কয়েকটা পদ্ধতি শিখবঃ
১ম পদ্ধতি – ৩টা ভ্যারিয়েবল ব্যবহার করেঃ
এটি হল ভ্যারিয়েবলের মান অদলবদল করার সবচাইতে সহজ বহুল ব্যবহৃত পদ্ধতি। সেক্ষেত্রে আমাদের ৩টা ভ্যারিয়েবল ব্যবহার করতে হবে। ধরুন a,b,c ভ্যারিয়েবল ব্যবহার করছি।a এবং b ভ্যারিয়েবল দিয়ে আমরা ইনপুট নিব। এরপর সোয়াপের ১ম ধাপে আমরা a এর মান c তে রাখব। ২য় ধাপে b এর মান a তে রাখব এবং ৩য় ধাপে c এর মান b তে রাখব।
উদাহরনঃ
ধরুনঃ a = 20 এবং b = 10
তাহলে a এর মান c তে রাখলে c = 20 হবে। এরপর b এর মান a তে রাখলে a = 10 হবে এবং c এর মান b তে রাখলে b = 20 হবে।
কোডঃ

int a, b, c;
cin>>a>>b;
cout<<"Before Swap: ";
cout<<a<<"\t"<<b<<endl;
c = a;
a = b;
b = c;
cout<<"After Swap: ";
cout<<a<<"\t"<<b<<endl;

২য় পদ্ধতি – ২টা ভ্যারিয়েবল ব্যবহার করেঃ
২টা ভ্যারিয়েবল ব্যবহার করে ভ্যারিয়েবলের মান অদলবদল করার দুইটা উপায় আছেঃ
১ সাধারন যোগ-বিয়োগ করেঃ
২ বিটওয়াইজ অপারেশন করেঃ

সাধারন যোগ-বিয়োগ করেঃ
ধরুন a, b আমাদের দুইটা ভ্যারিয়েবল। সোয়াপের ১ম ধাপে আমরা a থেকে b বিয়োগ করব এবং রেজাল্টটা a তে রাখব। ২য় ধাপে b এর সাথে a যোগ করব এবং রেজাল্ট b তে রাখব। ৩য় ধাপে a থেকে b বিয়োগ করব এবং রেজাল্ট a তে রাখব।
উদাহরনঃ
ধরুনঃ a = 20 এবং b = 10
১ম ধাপঃ a = a – b = 20 – 10 = 10
২য় ধাপঃ b = a + b = 10 + 10 = 20
৩য় ধাপঃ a = b – a = 20 – 10 = 10
কোডঃ

int a, b;
cin>>a>>b;
cout<<"Before Swap: ";
cout<<a<<"\t"<<b<<endl;
a = a – b;
b = b + a;
a = b – a;
cout<<"After Swap: ";
cout<<a<<"\t"<<b<<endl;

বিটওয়াইজ অপারেশন করেঃ
ধরুন a, b আমাদের দুইটা ভ্যারিয়েবল। সোয়াপের ১ম ধাপে আমরা a থেকে b XOR করব এবং রেজাল্টটা a তে রাখব। ২য় ধাপে b থেকে a XOR করব এবং রেজাল্ট b তে রাখব। ৩য় ধাপে a থেকে আবার b বিয়োগ করব এবং রেজাল্ট a তে রাখব।
উদাহরনঃ
ধরুনঃ a = 20 এবং b = 10
সেক্ষেত্রে বাইনারী তে a = 10100 এবং b = 1010
১ম ধাপঃ a XOR b = 10100 ^ 1010 = 11110 [11110 = 30]
২য় ধাপঃ b XOR a = 1010 ^ 11110 = 10100 [10100 = 20]
৩য় ধাপঃ a XOR b = 11110 ^ 10100 = 1010 [1010 = 10]
^ দিয়ে XOR operation বুঝায়।

কোডঃ

int a, b;
cin>>a>>b;
cout<<"Before Swap: ";
cout<<a<<"\t"<<b<<endl;
a ^= b;
b ^= a;
a ^= b;
cout<<"After Swap: ";
cout<<a<<"\t"<<b<<endl;

৩য় পদ্ধতি –swap() ফাংশন ব্যবহার করেঃ
আপনারা যারা C++ কোডার তারা চাইলে উপরের পদ্ধতিগুলো ব্যবহার না করে STL Algorithm ব্যবহার করেও ভ্যারিয়েবলের মান অদলবদল করতে পারবেন। সেক্ষেত্রে আপনাদের কোডটা এইরকম লিখতে হবেঃ

#include <algorithm>
int a, b;
cin>>a>>b;
cout<<"Before Swap: ";
cout<<a<<"\t"<<b<<endl;
swap(a,b);
cout<<"After Swap: ";
cout<<a<<"\t"<<b<<endl;

তাহলে আমরা প্রথম প্রোগ্রামটা একটু পরিবর্তন করে এইভাবে লিখতে পারিঃ

int a, b, sum = 0;
cin>>a>>b;
if(a > b)
{
	//Your code for swap
}
for(int i = a; i <= b; i++)
{
	sum += i;
}
cout<<sum<<endl;

আশাকরি আপনারা ভ্যারিয়েবলেন মান অদল-বদল করার পদ্ধতিগুলো বুঝতে পেরেছেন।