برنامه نویسی بازگشتی 1

یکی از روش جالب برنامه نویسی ، برنامه سازی ریکرسیو ( recursive ) یا همون بازگشتیه .

در برنامه نویسی ، ما میتونیم در یک تابع ، توابع دیگه رو صدا بزنیم. در این حالت ، برنامه در این تابع متوقف میشه تا زمانی که مقدار تابع دوم محاسبه بشه و سپس ادامه پیدا میکنه. به مثال زیر توجه کنید : 

int sum2(int a ,int b)
{
	return a + b;
}
int sum3(int a,int b,int c)
{
	int temp = sum2(a, b);
	return sum2(temp , c);
}

در این جا ، اگر ما سه عدد را به تابع sum3 بدیم ، تابع در خط اول خودش متوقف میشه تا مقدار sum2 محاسبه بشه. بعد به خط دوم خودش میره و باز هم متوقف میشه تا باز هم مقدار این تابع محاسبه بشه.

با توجه به این حالت ، به نظر میرسد که مشکلی وجود نداره که تابعی را در خودش صدا بزنیم چون تابع قبلی متوقف میشه و تابع با مقادیر جدید اجرا میشه و بعد از محاسبه شدن این تابع با مقدار های جدید ، محاسبه تابع قبل ادامه پیدا میکنه.

به این حالت تابع بازگشتی میگن. یعنی صدا زدن تابعی در خودش. 

*مراقب باشید که در هنگام نوشتن تابع بازگشتی ، برای حالتی که تابع دوباره صدا زده میشه ، یک شرط بگذارید تا این عمل بلاخره پس از مقداری محاسبه متوقف شود و داخل حلقه بی انتها نیوفته.

مثال : کد بازگشتی جمع کردن سه عدد : 

int sum(int a,int b,int c = 0)
{
	if(c == 0)
	{
		return a + b;
	}
	else
	{
		int temp = sum(a , b);
		return sum (temp , c);	
	}
}

الان ما مثلا تابع را با مقادیر 1,2,3 اجرا میکنیم. در ابتدا c صفر نیست پس وارد else میشه.تابع رو با مقادیر 1,2,0 اجرا میکه. این تابع دوم ، وارد if میشه و مقدار 3 رو برمیگردونه. مقدار 3 درون متغیر temp از تابع اول ریخته میشه و سپس تابع در ازای مقدار 3,3,0 اجرا میشه که جواب 6 برگردونده میشه و به عنوان خروجی کل داده میشه.

*لازم نیست نگران قاتی شدن متغیر ها باشید. ;)

حالا میریم سراغ یه مثال سخت تر. میخوایم یه برنامه بنویسیم که یه عدد رو بگیره و بگه که زوجه یا فرد. البته به صورت بازگشتی. 

دقت کنید که اگه توی تابع بازگشتی ، بخواید هی خودتونو داخل کد بکنید و ببینید دقیقا داره چی میشه ( هی بخواید مسیر تابع رو دنبال کنید) ، ممکنه گیج بشید. کافیه فقط یکم از ریاضیات استفاده کنید و تابع ها رو مثل یه جعبه سیاه ببینید. این حرف یعنی این که به این مسئله اینطوری نگاه کنید : 

اعداد یکی در میون فرد و زوج هستن. یعنی اگه عددی زوج باشه ، مثلما عدد قبلیش فرده. اگه ما بدونیم عدد قبلی چه وضعی داشته ، میتونیم بفهمیم این عدد چه وضعی داره. پس :

bool isOdd(int a)
{
	if(a == 0)
	{
		return 1;
	}
	if(a > 0)
	{
		return !isOdd(a - 1);
	}
	if(a < 0)
	{
		return !isOdd(a + 1);
	}

}

در این کد ، مقدار صفر به عنوان پایه قرار داده شده که میدونیم زوجه ، و هر عددی بر اساس عدد قبلی(منظور نزدیک تر به صفر است) مشخص میشه که فرده یا زوج. در توابع بازگشتی ، نگاهی که وجود دارد ، دقیقا مانند اثبات های استقراییه. یعنی لازم نیست برای عدد 1000 چک کنیم که دقیقا چه اتفاقی می افتد. میگیم تابع برای مقدار صفر درست کار میکند و اگر برای عدد i درست کار کنه ، برای i+1 هر درست کار میکنه پس همیشه درست کار میکند.

* لازمه که فرض کنید این تابعی که دارید مینویسیدش ، داره مقدار درست رو برمیگردونه.

مثال بعدی ،برنامه فیبوناچیه برنامه ای که عدد ان رو بگیره و جمله ان ام فیبوناچی رو خروجی بده :

int fib(int a)
{
	if(a == 1 || a == 2)
	{
		return 1;
	}
	else 
	{
		return (fib (a - 1) + fib(a - 2));
	}
}

اینجا دقیقا مطابق با تعریف بازگشتی دنباله فیبوناچی عمل میکنیم. برای مقادیر جملات اول و دوم که مقدارشون ثابته ، شرط میزاریم وگرنه بر اساس فرمول بازگشتی محاسبه میشه.

به عنوان مثال آخر هم، برنامه سرچ کردن یه عدد توی یه آرایه رو به صورت بازگشتی میبینیم : 

int BinarySearch(int nums[],int start , int end,int searchedNumber)
{
	if(start == end)
	{
		if(nums[start] == searchedNumber)
		{
			return start;
		}
		else
		{
			return -1;
		}
	}
	else
	{
		int leftAns = BinarySearch(nums,start , (end + start) / 2, searchedNumber);
		int rightAns = BinarySearch(nums, (end + start) / 2 + 1, end, searchedNumber);
		if(leftAns != -1)
		{
			return leftAns;
		}
		else if(rightAns != -1)
		{
			return rightAns;
		}
		else
		{
			return -1;
		}
	}
}

این برنامه تابعو دو قسمت میکنه و میگه اگه عدد تو هر کدوم از اینا بود، بگو هست وگرنه بگو نیست. به عنوان متوقف کننده هم میگیم اگه این تیکه ای که الان داری چکش میکنی ، فقط یه عدد داشت ، اگه اون عدد عددی بود که دنبالش بودی، بگو هست وگرنه بگو نیست.

*اینجا برای این که گیجتون نکنم ، ننوشتم ولی برای قسمت آخر، اگه بدونیم توی آرایمون عدد تکراری نداریم ، جای اون سه تا if و else if و else ها ، یع خط کوچیک کافی بود. یه ذره فقط تحلیل ریاضی میخواد : 

return (leftAns + rightAns + 1);

در مورد این که چرا این درسته ، ما میدونیم که آرایمون عدد تکراری نداره پس میدونیم توی این نصف کردن ها ، عددی که دنبالشیم یا توی سمت نصفه سمت چپه ، یا نصفه سمت راست یا تو هیچ کدوم ( توی جفتش نیست) پس حد اقل یکی از دو متغیر جواب راست و جواب چپ ، برابر -1 هست. حالا اگه اون یکی یک عدد عادی باشه ، جای عدد مورد نظر توی آرایست وگرنه منفی یکه و جواب کل هم باید -1 بشه. اولین -1 با اون +1 که گذاشتیم میره و اون یکی عدد به عنوان جواب نهایی خروجی داده میشه.

* این نوع از جست و جو ، برای آرایه های مرتب شده پر کاربرده. اگه آرایه مرتب باشه ، میایم عنصر وسط رو نگاه میکنیم و با مقایسه اون با عددی که دنبالشیم ، میتونی یکی از دو طرف رو حذف کنیم ( مثلا اگه صعودی باشه و ما دنبالی عددی باشیم که از عنصر وسط بزرگتر باشه ، مطمئنان اون عدد توی قسمت سمت راستی نیست چون قسمت سمت راست کوچیک تر از عدد وسطه).