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

تابع يا زيربرنامه بخش جداگانه ای از کد برنامه است که می تواند توسط يک نام صدا زده شود. به هر زيربرنامه ممکن است پارامترهايی ارسال شود و هر تابع می تواند يک مقدار را برگرداند. وقتی تابعی فراخوانی می شود مقدار پارامترهای تابع در جائی بايد ذخيره شود تا تابع بتواند به آنها دسترسی پيدا کند.

Call stack

اکثر کامپايلرها برای فراخوانی و برگشت از زيربرنامه call stack را پياده سازی می کنند. Call stack يا run-time stack يک پشته است که اطلاعاتی درباره زيربرنامه فعال يک برنامه را نگهداری می کند. زيربرنامه فعال زيربرنامه ای است که فراخوانی شده است اما هنوز اجرايش تمام نشده است.

وقتی زير برنامه ای فراخوانی می شود، قبل از اينکه کنترل اجرای برنامه به آدرس زيربرنامه پرش کند آدرس دستورالعمل بعدی (دستورالعملی که درحافظه بعد از دستور فراخوانی قرار دارد) درجائی بايد ذخيره شود که هنگام برگشت از زيربرنامه از آن استفاده می شود. اين آدرس را آدرس برگشتی (return addresses) می نامند.

معماری که بر اساس پشته است آدرس برگشتی را به عنوان نقطه برگشت در پشته اضافه می شود. هر بار که زيربرنامه ای فراخوانی می شود آدرس برگشتی در پشته push می شود. هنگام برگشت از زيربرنامه آدرس برگشتی از پشته pop شده و کنترل برنامه به آن آدرس پرش می کند و اجرای برنامه از بعد از دستور فراخوانی ادامه پيدا می کند.

به دليل استفاده از پشته يک زيربرنامه می تواند خودش يا زيربرنامه های ديگر را صدا بزند.

در زبان های سطح بالا call stack معمولا از برنامه نويس مخفی است. درمقابل در زبان اسمبلی نياز است خود برنامه نويس با پشته درگير شود.

نمونه هائی از توابع بازگشتی:

مثال(C). تابع بازگشتي ضرب.

int Mul (int a , int b)
{
  if (b == 1)
    return a;
  else
    return a+Mul (a,b-1);
}

مثال(Pascal). تابع بازگشتی فيبوناچی.

Function Fibonacci ( n: Integer ):Integer;
Begin
  If (n=1) or (n=2) Then Fib:=1
  Else Fibonacci:= Fibonacci (n-2)+ Fibonacci (n-1);
End;

مثال(Pascal). تابع بازگشتي اکرمن (Ackermann's function) تابعی است که مقدار آن به سرعت رشد می کند.

Function Ackerman ( a,b: Integer ):Integer;
Begin
  If (a<0) and (b<0) Then Ackerman:=0
  Else If a=0 Then Ackerman:=b+1
  Else If b=0 Then Ackerman:= Ackerman (b-1,1)
  Else Ackerman:= Ackerman (a-1,Ack(a,b-1));
End;

جمع دو عدد با تابع بازگشتی(++C):

#include <iostream.h> 
#include <conio.h> 
int sum(int x,int y) 
{ int sum=0; 
while(x<=y) 
{if(x%2==0) 
sum+=x; 
x++; 
}//End Of While 
return sum; 
} 
void main() 
{int x,y; 
cin>>x>>y; 
cout<<sum(x,y); 
getch(); 
}

stcomputer.ir + softafzar.net