تماس درباره   صفحه اصلی
  ساختمان داده > بازگشتی  
 
 

بازگشتی


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

Call stack
عملکردهای call stack
ساختار call stack
بازگشتی
بازگشتی در مقايسه با غير بازگشتی
سرريزی پشته
نمونه هائی از توابع بازگشتی


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

Call stack

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

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

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

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

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


عملکردهای call stack

هدف اصلی يک call stack نگهداشتن آدرس برگشتی هر زيربرنامه فعال است. اما بسته به زبان، سيستم عامل و محيط سخت افزاری ممکن است عملکردهای اضافی ديگری هم داشته باشد نظير:

ذخيره آدرس های برگشتی

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

ذخيره متغيرهای محلی

متغيرهائی که درون زيربرنامه تعريف می شوند متغيرهای محلی ناميده می شوند. متغيرهای محلی تنها درون زيربرنامه فعال شناخته شده هستند و بعد از اتمام زيربرنامه مقدار آنها در حافظه باقی نمی ماند. اغلب مناسب است که فضائی در پشته به آنها اختصاص داده شود که سريع تر از تخصيص فضای آزاد heap به آنها است. هر زيربرنامه فعال فضای جداگانه خودش را در پشته برای داده های محلی دارد.

ارسال پارامتر

مقادير پارامترهای موردنياز زيربرنامه ها هنگام فراخوانی به آنها داده می شوند. معمولا فضای از call stack برای ذخيره مقدار اين پارامترها اختصاص داده می شود. هر فراخوانی به زيربرنامه مقادير مختلفی از پارامترها را خواهد داشت و فضای جداگانه ای در پشته به آنها داده می شود.


ساختار call stack

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


مثال. فرض کنيد تابع function2 اکنون در حال اجرا است و توسط function1 فراخوانی شده است. وضعيت پشته می تواند به شکل زير باشد.

Call stack example

فريمی که در بالای پشته است مربوط به زيربرنامه ای است که اکنون در حال اجرا است. هر فريم ممکن است دربرگيرنده متغيرهای محلی، آدرس برگشتی و مقدار پارامترهای زيربرنامه باشد. فريم های پشته هم اندازه نبوده و زيربرنامه های مختلف فريم های متفاوتی دارند.

پشته توسط ثبات stack pointer دسترسی می شود که بالای پشته را مشخص می کند.


بازگشتی

بازگشتی اجازه بيان راه حل يک مسئله را به طور مختصر و مفيد می دهد. مسئله ای که به صورت بازگشتی حل می شود بايد بتواند به مسائل کوچک تر تقسيم بشود و حل مسائل کوچک به همان روش مسئله بزرگ قابل انجام باشد. مسئله کوچک تر به مسئله کوچک تری شکسته می شود تا سرانجام یه کوچک ترين اندازه مسئله برسد که base case ناميده می شود که می تواند بدون استفاده از بازگشتی حل شود.


يک مثال متعارف الگوريتم بازشگتی ضابطه تابع فاکتوريل f(n) است:

recursive Factorial function

مقدار تابع برای f(3) به صورت زير محاسبه می شود:

f(3) = 3 * f(3 − 1)
= 3 * f(2)
= 3 * 2 * f(2 − 1)
= 3 * 2 * f(1)
= 3 * 2 * 1 * f(1 − 1)
= 3 * 2 * 1 * f(0)
= 3 * 2 * 1 * 1
= 6


يک الگوريتم بازگشتی توسط تابع بازگشتی پياده سازی می شود. تابع بازگشتی (recursive function) تابعی است که خودش را فراخوانی می کند.

تابع بازگشتی مشابه توابع ديگر کار می کند. برای هر فراخوانی بازگشتی يک فريم جديد از تابع در پشته ايجاد می شود.


مثال(C). تابع بازگشتی محاسبه فاکتوريل يک عدد صحيح.

int Factorial (int x)
{
  if (x<= 1)
    return 1;
    return x * Factorial (x-1);
}

همان تابع به صورت غير بازگشتی به صورت زير نوشته می شود. توجه کنيد که به د و متغير موقت نياز دارد.

int Factorial (int x)
{
  int i, temp;
  for ( i=1; i<=x; i++)
    temp*=i;
  return temp;
}


مثال(C). تابع ديگر که زيبائی بازگشتی را بيشتر نشان می دهد الگوريتم اقليدسی برای محاسبه بزرگترين مقسوم عليه مشترک (greatest common divisor) دو عدد صحيح است. الگوريتم بازگشتی آن در زبان C به صورت زير است:

int GCD (int x, int y)
{
  if (y == 0)
    return x;
  else
    return GCD (y, x % y);
}

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

int GCD(int x, int y)
{
  while (y != 0) {
    int r = x % y;
    x = y;
    y = r;
  return x;
}


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


بازگشتی در مقايسه با غير بازگشتی

برای اينکه بازگشتی موفق باشد مسئله نياز است يک زيرساختار بازگشتی داشته باشد. راه حل بعضی از مسائل به طور ذاتی بازگشتی است چون احتياج به نگداری حالت قبلی دارند. الگوريتم پيمايش درخت(tree traversal)، تابع اکرمن(Ackermann) و الگوريتم های تقسيم و غلبه مانند مرتب سازی سريع(Quicksort) همگی به صورت بازگشتی هستند. همه اين الگوريتم ها می توانند به صورت غيربازگشتی با کمک پشته هم پياده شوند اما نياز به پشته مزيت راه حل غير بازگشتی را از بين می برد.

تابع غير بازگشتی احتمالا در عمل کمی سريعتر از نسخه بازگشتی آن اجرا می شود چون تابع غير بازگشتی سربار فراخوانی تابع (function-call) را به اندازه تابع بازگشتی ندارد و اين سربار در بعضی زبان ها نسبتا بالا است.

يک دليل ديگر برای ترجيح غيربازگشتی به بازگشتی اين است که فضای پشته قابل دسترس کمتر از فضای قابل دسترس در حافظه آزاد heap است. و الگوريتم های بازگشتی تمايل به فضای پشته بيشتری نسبت به غير بازگشتی دارند.

سرريزی پشته

وقتی اشاره گر پشته به انتهای پشته می رسد پشته سرريز می شود. دليل معمول سرريزی پشته فراخوانی مکرر يا تعداد زياد متغيرهای محلی توابع بازگشتی است. اگر يک تابع بی نهايت بار خودش را صدا بزند در هر فراخوانی يک فريم پشته اضافه می شود و در يک نقطه پشته ديگر جا ندارد و سرريز می شود و خطای stack overflow رخ می دهد.


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

مثال(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;


تمرينات توابع بازگشتی

سوالات چند گزينه ای درباره توابع بازگشتی


 


 


صفحه اصلی| PDF| درباره| تماس