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

مثال زیر را ببینید.

توجه فرمایید که تابع فوق را با فقط با کامپایلرهایی که از تابع بازگشتی پشتیبانی می کنند می توانید کمپایل کنید. فرترن 90 به بعد از توابع بازگشتی پشتیبانی می کنند اما فرترنهای قبلی مانند فرترن 77 اینطور نیستند! در این مثال (مثال بالا) تابع فاکتوریل را می بینید، اگر عدد ورودی به این تابع (N) مساوی یک باشد تابع مقدار یک را باز می گرداند و دیگر خودش را فراخوانی نخواهد نمود (همان راه خروج از تابع که صحبت شد) . اما اگر عدد ورودی به این تابع (N) عددی غیر از یک باشد، تابع خودش را به صورت factorial(N-1)*N دوباره فراخوانی میکند. این فراخوانی در حین اجرای تابع اول و قبل از پایان آن است. در این فراخوانی مقدار تابع تابع اول برابر فاکتوریل N-1، ضربدر N قرار می گیرد. پس برای محاسبه پاسخ تابع لازم است تابع فاکتوریل با مقدار N-1 محاسبه شود و حاصلش در N ضرب گردد. فراخوانی تابع فاکتوریل با مقدار N-1 به عنوان ورودی (اگر N-1 مساوی یک نباشد) باعث رسیدن به دستور factorial(N-1)*N خواهد شد و می دانیم که ورودی مقدار N-1 است پس به جای N در این دستور مقدار ورودی یعنی N-1 را قرار می دهیم و عملاً مقدار این دستور برابر factorial((N-1)-1)*(N-1) خواهد شد. یعنی دوباره مقدار این تابع بستگی به نتیجه factorial(N-2) دارد (مجدد تابع فاکتوریل با مقداری جدید فراخوانی خواهد شد و به همین ترتیب تا جایی که تابع فاکتوریل با مقدار 1 فراخوانی شود. در این حالت نتیجه تابع فاکتوریل مساوی یک است. فرض کنید با این تابع فاکتوریل 4 را محاسبه نماییم:

  1. محاسبه تابع فاکتوریل 4 باعث اجرای تابع فاکتوریل شده و چون 4 برابر یک نیست پس مقدار تابع فاکتوریل 4 برابر مقدار فاکتوریل 3 ضربدر 4 است، یعنی تابع فاکتوریل با مقدار 3 فراخوانی می شود.
  2. مقدار تابع فاکتوریل 3 برابر مقدار تابع فاکتوریل 2 ضربدر 3 است. یعنی باعث فراخوانی تابع فاکتوریل  2 خواهد شد.
  3. مقدار تابع فاکتوریل 2 برابر مقدار فاکتوریل 1 ضربدر 1 است. که باعث فراخوانی تابع فاکتوریل 1 خواهد شد.
  4. مقدار فاکتوریل 1 مساوی یک است.
  5. حال که فاکتوریل 1 محاسبه شد این مقدار به تابع فراخوانی کننده آن یعنی فاکتوریل 2 ارسال می گردد و آن تابع مقدار 1 را در 2 ضرب کرده و نتیجه را باز می گرداند.
  6. این نتیجه (نتیجه تابع فاکتوریل 2) به تابع فراخوانی کننده یعنی فاکتوریل 3 ارسال می گردد و آن تابع مقدار 2 را در 3 ضرب می کند و نتیجه تابع فاکتوریل 3 یعنی 6 به دست آمده و به تابع فراخواننده یعنی فاکتوریل 4 ارسال می گردد.
  7. تابع فاکتوریل 4 مقدار به دست آمده برای تابع فاکتوریل 3 (نتیجه مرحله قبل) را در 4 ضرب می کند و نتیجه برابر 24 به دست می آید.

factorial(4) —> factorial(3) * 4

factorial(3) —> factorial(2) * 3

factorial(2) —> factorial(1) * 2

factorial(1) = 1

factorial(2) = 1 * 2 = 2

factorial(3) = 2 * 3 = 6

factorial(4) = 6 * 4 = 24

 

فراخوانی تابع فاکتوریل 4 باعث فراخوانی تابع فاکتوریل 3 خواهد شد، فراخوانی تابع فاکتوریل 3 باعث فراخوانی تابع فاکتوریل 2 خواهد شد، فراخوانی تابع فاکتوریل 2 باعث فراخوانی تابع فاکتوریل یک خواهد شد، در این مرحله فاکتوریل یک محاسبه شده برابر یک خواهد شد، حال حاصل فاکتوریل 2 با داشتن فاکتوریل 1 قابل محاسبه است (1 مرحله قبل *2)، حال فاکتوریل 3 قابل محاسبه است (2 مرحله قبل *3) و بعد از آن فاکتوریل 4 قابل محاسبه است (6 مرحله قبل *4)). یک مثال دیگر تابع فیبوناچی به صورت بازگشتی است. این تابع را نیز می توانید به روش ساده تری نوشت اما هدف یادگیری تابع بازگشتی است!

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

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

  1. هر بار فقط می توانید یک قرص را جابجا نمایید
  2. همیشه بایستی قرص کوچکتر روی قرص بزرگتر قرار گیرد و برعکس آن مجاز نیست!

آیا می تونید با سه قرص مسئله را حل کنید؟ با چهار قرص چطور؟ هر چه تعداد قرصها بیشتر شود مسئله سخت تر خواهد شد!!؟ برای حل از میله کمکی نیز استفاده نمایید.
برای نوشتن یک برنامه کامپیوتری که همین مسئله را حل کند از تابع بازگشتی استفاده خواهیم کرد. بیان تابع بسیار ساده است. تابع حرکت بسیار ساده است، ساختار این تابع به شکل زیر است:

  1. اگر قرص شماره یک است
    1. قرص را از میله مبدا به میله مقصد جابجا کن
  2. اگر قرص شماره یک نیست
    1. ابتدا تمام قرص های روی قرص مورد نظر را با کمک میله مقصد به میله کمکی ببر
    2. قرص اصلی (که الان هیچ قرصی رویش نیست) را از میله مبدا به میله مقصد ببر
    3. همه قرصهای موجود در میله کمکی را با کمک میله مبدا (که الان خالی است) به میله مقصد ببر

برای درک بهتر فرایند حرکت قرصها اجازه دهید همین فرایند را برای سه قرص برسی کنیم!

حرکت سه قرص از میله مبدا به مقصد تبدیل به فرایند زیر تبدیل خواهد شد:

  1. حرکت دو قرص روی قرص سه از میله مبدا به میله کمکی با استفاده از میله کمکی
  2. حرکت قرص سه از میله مبدا به مقصد
  3. حرکت دو قرص موجود در میله کمکی به میله مقصد با استفاده از میله مبدا

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

  1. حرکت قرص یک از میله مبدا به میله مقصد
  2. حرکت قرص دو از میله مبدا به میله کمکی
  3. حرکت قرص یک از میله مقصد به میله کمکی

در فرایند جابجایی سه قرص دستور سوم یعنی حرکت دو قرص از میله کمکی به میله مقصد با استفاده از میله کمکی به فرایند زیر تبدیل خواهد شد:

  1. حرکت قرص یک از میله کمکی به میله مبدا
  2. حرکت قرص دو از میله کمکی به میله مقصد
  3. حرکت قرص یک از میله مبدا به میله مقصد

حال کل فرایند را به ترتیب بر اساس جابجایی هر یک از قرصها خواهیم نوشت:

  1. حرکت قرص یک از میله مبدا به میله مقصد
  2. حرکت قرص دو از میله مبدا به میله کمکی
  3. حرکت قرص یک از میله مقصد به میله کمکی
  4. حرکت قرص سه از میله مبدا به مقصد
  5. حرکت قرص یک از میله کمکی به میله مبدا
  6. حرکت قرص دو از میله کمکی به میله مقصد
  7. حرکت قرص یک از میله مبدا به میله مقصد

حال که مراحل را درک کرده اید برای چهار قرص مراحل را امتحان کنید.

برنامه کامپیوتر این حرکت برای هر تعداد قرص به شکل زیر خواهد بود:

برنامه برج هانوی (Tower of Hanoi) به زبانهای مختلفی نوشته شده است و می توانید آنها را با جستجو در اینترنت بیابید، یک برنامه بسیار قویتر را می توانید از سایت زیر دریافت کنید.

TowerOfHanoi

به عنوان تمرین یک برنامه بنویسید که هشت وزیر را در خانه شطرنج بگذارد بدون این که یکدیگر را بزنند! البته اصلا تمرین ساده ای نیست