====== توابع بازگشتی ======
===== تعریف =====
به تابعی بازگشتی می گوییم که در روند اجرا خودش را فراخوانی کند . شاید به نظر برسد که در چنین حالتی برنامه هیچوقت به پابان نمیرسد ولی همیشه اینطور نیست اگر تابع ما شرایط خاصی داشته باشد و حالت پایه برای آن تعریف شده باشد روند اجرای آن به پایان میرسد و نتیجه مورد نظر بدست می آید.
  * باید برای مسئله حداقل یک **//حالت پایه//** تعریف کرده و مقدار تابع را در آن حالت بدانیم.
  * روند فراخوانی ها باید به حالت(های) پایه ختم شود و به دور منجر نشود.
===== مثال اول =====
میخواهیم تابعی بازگشتی برای محاسبه تابع $F(n)=n!$ بنویسیم. 

<code cpp fac.cpp>
int fac(int n){
	if(n<=0)
		return 1;
	return n*fac(n-1);
}
</code>
حال روند محاسبه $fac(3)$ را بررسی میکنیم .  $fac(3)$ صدا میشود و سپس $fac(2)$ را صدا میکند و سپس $fac(1)$ صدا میشود و خروجی $1$ را برمیگرداند در تابع $fac(2)$ این مقدار در $2$ ضرب شده و مقدار $2$ به عنوان خروجی $fac(2)$ به تابع $fac(3)$ فرستاده میشود و این مقدار در $3$ ضرب میشود و مقدار $6$ به عنوان خروجی برگردانده میشود.
===== مثال دوم =====
میخواهیم تابعی بنویسیم که مقدار جمله $n$ ام فیبوناچی را محاسبه کند.
<code cpp fibo.cpp>
int fibo(int n){
	if(n<=1)
		return 1;
	return fibo(n-1)+fibo(n-2);
}
</code>
روند محاسبه $fibo(5)$ به این شکل است : 
{{ fib.gif?nolink |}}

===== مثال سوم =====
تابعی بازگشتی بنویسید که مقدار  $p$ $mod$ $n^k$  را در $O(lgk)$ محاسبه کند.
<پاسخ>
<code cpp modPow.cpp>
int modPow(int n,int k,int p){
	if(k==0)
		return n%p;
	int ret=modPow(n,k/2,p);
	ret=(temp*temp)%p;
	if(k%2==1)
		temp=(temp*n)%p;
	return temp;
}
</code>
</پاسخ>