در این مقاله قصد داریم تا با مفهوم Recursion و فانکشن‌های ریکرسیو با ذکر مثالی در زبان برنامه‌نویسی جاوا آشنا شویم. اساساً Recursion یک تکنیک در برنامه‌نویسی است که در آن یک متد خاص برای حل مسئله خود را فراخوانی می‌کند به طوری که می‌توان گفت متدهای بازگشتی طی یک روند تودرتو خود را فراخوانی می‌کنند و با هر بار فراخوانیِ خود مسئله را به یک یا چند مسئلۀ ساده‌تر تقسیم می‌کنند.
Recursion دارای سه فاز اصلی است که در اولین فاز آن متد مذکور خود را فراخوانی می‌کند و با هر بار فراخوانی دامنۀ خود را کوچک‌تر می‌کند و مجموعۀ جوابِ خود را ساده‌تر می‌کند (به عبارت دیگر، به سمت ساده‌تر شدن حرکت می‌کند.) و این فراخوانی‌ها تا جایی ادامه پیدا می‌کنند که نتیجۀ متد به قدری ساده شود که جواب آن بدیهی گردد و به طور کلی اتمام این فراخوانی‌ها را با شرطی می‌سنجیم که به آن شرط خاتمه می‌گویند که فاز دوم است. وقتی شرط خاتمه برقرار شد، متد نتیجه‌ای بدیهی را برمی‌گرداند که از آن به بعد فاز سوم شروع می‌شود که اصطلاحاً فاز بازگشت نامیده می‌شود که در این فاز متد با کمک نتیجۀ به دست آمده در فاز دوم به فراخوانی‌های قبلی‌اش بازمی‌گردد و نتایج را یک‌به‌یک تکمیل می‌سازد.
کاربرد تابع بازگشتی در محاسبهٔ فاکتوریل
برای روشن شدن بیشتر مفهوم توابع بازگشتی، مثال کلاسیک فاکتوریل را بررسی می‌کنیم. فرض کنیم که قصد داریم تا فاکتوریل !n یا به عبارتی نتیجه ضرب اعداد 1 تا n را به دست آوریم به طوری که داریم:
n! = 1 * 2 * 3 * 4 ... * nاگر به دیدِ بازگشتی به این مسئله نگاه کنیم، فاکتوریل n برابر است با ضرب عدد n در فاکتوریل n - 1 به طوری که خواهیم داشت:
n! = (n - 1) * nاز همین روی، به منظور محاسبهٔ !n باید ابتدا n - 1 را محاسبه کنیم اما برای محاسبهٔ این مقدار نیاز است تا ابتدا n - 2 را حساب کنیم و به همین ترتیب ادامه می‌دهیم تا اینکه 1 = 1! گردد.
پیش از این گفتیم که شرط خاتمه شرطی است که به ازای برقرار شدن آن شرط متد به یک مقدار قطعی می‌رسد و دیگر خود را فراخوانی نمی‌کند بلکه با کمک این مقدار بازمی‌گردد و به ساختن سایر نتایج می‌پردازد و نیاز به توضیح نیست که بدون هیچ‌گونه شرط خاتمه‌ای، متد تا ابد خود را فراخوانی خواهد کرد! در مثال فوق n == 1 شرط خاتمۀ این متد است زیرا می‌دانیم وقتی n = 1 باشد مقدار !n برابر با 1 می‌شود و این به معنی آن است که به مقدارِ نتیجۀ بدیهی (قطعی) رسیده‌ایم. به همین ترتیب روند اجرای برنامه به فراخوانی‌های قبلی بازمی‌گردد تا به n برسد و آن را محاسبه کند.
به منظور درک سازوکار فاکتوریل، در ادامه و با استفاده از زبان برنامه‌نویسی جاوا کلاسی تحت عنوان Factorial نوشته و عملکرد فاکتوریل را در آن شبیه‌سازی می‌کنیم به طوری که خواهیم داشت:
class Factorial {
static int factorial(int n) {
if (n != 1)
return n * factorial(n - 1); // recursive call
else
return 1;
}
public static void main(String[] args) {
int number = 4, result;
result = factorial(number);
System.out.println("factorial of " + number + " is " + result);
}
}در کد بالا ابتدا متد ()factorial در متد ()main با آرگومان number = 4 فراخوانی می‌شود به طوری که داخل متد ()factorial ابتدا مقدار n برابر ۴ است و در فراخوانی بعدی مقدار n که مساوی با ۳ است به متد ()factorial فرستاده می‌شود و این روند تا زمانی ادامه می‌یابد که n برابر با ۱ شود که در این نقطه شرط if (شرط خاتمه) نادرست می‌شود و بخش else اجرا می‌شود و مقدار ۱ را ریترن می‌کند و نتیجۀ نهایی به متد ()main فرستاده می‌شود تا نمایش داده شود به طوری که به عنوان خروجی خواهیم داشت:
factorial of 4 is 24 جهت درک بهتر نحوهٔ عملکرد بلوک فوق، می‌توانید به آموزش ساخت اولین پروژه در زبان برنامه‌نویسی جاوا مراجعه نمایید.
مقایسهٔ راه‌حل بازگشتی و استفاده از حلقه
پاسخ به این پرسش که «آیا تمام متدهای بازگشتی تبدیل‌پذیر به حلقه هستند؟» آری است. طبق نظریهٔ Church Turing اثبات می‌شود که تمامی متدهای بازگشتی را می‌توان به صورت حلقه‌های تودرتو نوشت و بالعکس اما این نظریه بیان نمی‌کند که چه‌طور می‌توان این کار را کرد!
در واقع، عمدتاً تبدیل یک متد بازگشتی به حلقه و برعکس آن بسیار دشوار است و فهم آن زمان‌بر و نیازمند تجربه است. تک‌تک اِلمان‌های حلقه قابل‌نگاشت به اِلمان‌های متد بازگشتی است به طوری که در حلقه یک عمل تکرار می‌شود و این تکرار مقدار متغیری را تغییر می‌دهد تا جایی که شرط حلقه دیگر صادق نباشد و در متد بازگشتی نیز فراخوانیِ متد تکرار می‌شود و با هر تکرار مقدار آرگومان ورودی متد تغییر می‌کند تا جایی که شرط پایان صدق کند. همچنین نیاز به یادآوری است که در حلقه با هر بار اجرای حلقه محاسبه‌ای انجام می‌شود که این محاسبه در راه‌حل بازگشتی در فاز بازگشت به صورت پایین به بالا یا اصطلاحاً Bottom-Up انجام می‌گیرد که به منظور درک تفاوت میان این دو رویکرد، مثال فاکتوریل فوق با استفاده از یک حلقه را می‌توان به صورت زیر نوشت:
class Factorial {
public static void main(String[] args) {
int num = 4;
int fact = 1;
for (int i = 1; i <= num; i++) {
fact = fact * i;
}
System.out.println("factorial of " + num + " is " + fact);
}
}همان‌طور که در کد بالا مشاهده می‌کنید، ()main متد اصلی برنامه است که داخل آن متغیرهای num و fact تعریف شده‌اند به طوری که مقدار اولیهٔ ۱ برای متغیر fact در نظر گرفته شده است و متغیر num نیز مقدار مورد نظر ما را برای محاسبۀ فاکتوریل در خود نگاه خواهد داشت و در هر بار اجرای حلقه نیز متغیر i که در ابتدا مقدار ۱ را دارا است در متغیر fact ضرب می‌شود و نتیجه در fact ذخیره می‌گردد. به عبارتی، با هر بار اجرای حلقه فاکتوریل i محاسبه می‌شود و در fact ذخیره می‌شود و این حلقه تا زمانی که i برابر با num شود ادامه یافته و در انتها مقدار فاکتوریل num در متغیر fact ذخیره می‌گردد.
مقایسهٔ مصرف حافظه در تابع بازگشتی و حلقه
زمانی که از یک حلقه استفاده می‌کنیم، متغیر fact یک خانه از مموری را اِشغال کرده است و با هر بار اجرای حلقه مقدارش به‌روزرسانی می‌شود و در انتهای کار محتویات همین یک خانه از مموری که در طول اجرای حلقه دست‌خوش تغییر شده نمایش داده می‌شود اما در تابع بازگشتی در مثال فوق در فراخوانی اول مقدار فاکتوریل ۴ را نمی‌دانیم و از همین روی برنامه آن را در روی اِستک قرار می‌دهد سپس مقدار فاکتوریل ۳ روی استک قرار می‌گیرد و به همین ترتیب تا به فاکتوریل عدد ۱ برسیم و در این نقطه از اجرای برنامه می‌دانیم که فاکتوریل ۱ برابر با ۱ است و بالتبع شرط خاتمه صدق می‌کند و سیستم آن را روی اِستک نمی‌گذارد بلکه آخرین فراخوانی را که فاکتوریل ۲ است از روی اِستک برداشته و در ۱ ضرب می‌کند و برنامه به همین ترتیب به کار خود ادامه می‌دهد و در هر بار اجرا، فراخوانی ماقبل خودش را از روی اِستک برداشته و در متغیر به دست آمده ضرب می‌کند تا جایی که اِستک خالی شود؛ به عبارتی، آخرین محتوای اِستک که در اولین مرحله وارد آن شده است (یعنی فاکتوریل عدد ۴) را برمی‌دارد و نتیجهٔ نهایی را به دست آورده و چاپ می‌کند.
با مقایسۀ دو راه‌حل می‌بینیم که با استفاده از حلقه فقط متغیر fact در مموری ذخیره شد ولی در راه‌حل بازگشتی هر یک از فراخوانی‌ها در اِستک (مموری) ذخیره می‌شود. با این تفاسیر، می‌توان گفت در مواقعی که تعداد فراخوانی‌ها بسیار زیاد است این میزان از اختصاص مموری ممکن است برنامه را با کمبود منابع مواجه سازد. به طور مثال، اگر حجم مموری اختصاص‌یافته به اِستک کم باشد و از همین روی اِستک پُر شود، در چنین شرایطی اِستک سرریز می‌کند و مجبور می‌شود متغیر را در حافظۀ غیرمجاز ثبت کند که این باعث کِرَش کردن برنامه می‌شود از طرفی دسترسی به حافظه که یک عمل Input Output یا به اختصار IO است در راه‌حل بازگشتی بیشتر بوده و می‌دانیم که عملیاتی از این دست در زمان اجرا بیش از عملیات محاسبه زمان‌بر هستند و این خود باعث کندتر شدن اجرای برنامه می‌شود.
چرا از تابع بازگشتی استفاده کنیم/نکنیم؟
تابع بازگشتی کد را واضح‌تر می‌کند و (گاهی) نوشتن و دیباگ کردن آن در زمان کمتری انجام می‌شود (این لزوماً بدان معنا نیست که در زمان کمتری اجرا می‌شود یا مموری کمتری را اِشغال می‌کند.) مضاف بر اینکه توابع بازگشتی پیچیدگی زمانی کمتری دارند و به دلیل استفاده از ساختار درختی، یک تابع بازگشتی در حل مسائل پیچیده‌ای همچون برج‌های هانوی بهتر عمل می‌کند. در مقابل، با توجه به اینکه فهم روند اجرای برنامه در فانکشن‌های ریکرسیو دشوار است و از طرفی به دلیل سربار استفاده از استک کندتر اجرا می‌شوند و بالتبع به دلیل استفاده از اِستک معمولاً فضای حافظۀ بیشتری استفاده می‌کنند، بهتر است از این دست توابع استفاده نشود که در این رابطه و به منظور درک بهتر مفهوم تابع بازگشتی و کاربردهای آن در سایر زبان‌های برنامه‌نویسی، توصیه می‌کنیم به مقالات زیر مراجعه نمایید:
- آشنایی با مفهوم Recursive Function و نحوۀ پیاده‌سازی آن در زبان برنامه‌نویسی پایتون
- Recursive Function چیست و چگونه یک تابع بازگشتی با استفاده از JS پیاده‌سازی کنیم؟
- تابع بازگشتی چیست و چگونه آن را در زبان PHP پیاده‌سازی کنیم؟
جمع‌بندی
به طور کلی متدهای بازگشتی از ساختمان دادهٔ Stack (پُشته) برای اختصاص فضا به متغیرها و پارامترهای‌شان استفاده می‌کنند که به صورت Last In First Out یا به اختصار LIFO عمل می‌کند. در واقع، هنگامی که یک فراخوانی بازگشتی صورت می‌گیرد، فضایی روی اِستک به متغیرهای متد اختصاص داده می‌شود و با هر بازگشت به فراخوانی قبلی، متغیرها و پارامترهای مرحلهٔ قبل از روی اِستک برداشته می‌شوند که این باعث می‌شود تا متدهای بازگشتی کندتر باشند و مموری بیشتری مصرف کنند و پرفورمنس به میزان چشم‌گیری کاهش یابد مضاف بر اینکه ممکن است سرریز پُشته (Stack OverFlow) رخ دهد که باعث کِرَش کردن برنامه می‌شود که از قضا یک روش #هک نیز می‌باشد.