آشنایی با زیربرنامه های بازگشتی ( Recursion ) در ساختمان داده ها

بعضی از مسائل طبیعتی بازگشتی دارند شاید برای شما نامفهوم باشد که بازگشتی بودن یعنی چی . زیربرنامه های بازگشتی همیشه دارای دوشرط هستند : ۱- برنامه خودش را صدا می زند( معمولا با آرگومان کمتر)  ۲- شرطی برای پایان دادن به صدا زدن ها باید باشد.

برای مثال فرمول محاسبه فاکتوریل یک عدد برابر است با : n*(n-1)!  تا زمانی که عدد به یک برسد. برای مثال فاکتوریل عدد ۴ به صورت زیر محاسبه می شود :

تابع زیر را درنظر بگیرید برای محاسبه فاکتوریل هر عدد می بایست عدد را به عنوان ورودی به تابع بدهیم پس برای محاسبه فاکتوریل عدد چهار، fact(4) را صدا می زنیم.

مرحله ۱ : ابتدا بررسی می شود آیا عدد ۴ کوچکتر مساوی ۱ است که شرط نادرست بوده و بخش else اجرا می شود. اما قبل از برگرداندن خروجی بخش else ، باید فاکتوریل عدد ۳  محاسبه شود یعنی تابع باید دوباره فراخوانی شود اما با یک آرگومان کمتر. پس به مرحله دوم می رویم —>

مرحله ۲ :  تابع fact با عدد سه فراخوانی می شود : fact(3) :  بررسی می شود آیا عدد ۳ کوچکتر یا مساوی عدد یک است که شرط نادرست بوده و بخش else اجرا می شود. اما قبل از آن باید فاکتوریل عدد ۲ محاسبه شود .پس به مرحله سوم می رویم –>

مرحله ۳ : تابع fact با عدد دو فراخوانی می شود : fact(2)  :  بررسی می شود آیا عدد ۲ کوچکتر یا مساوی عدد یک است که شرط نادرست بوده و بخش else اجرا می شود اما قبل از آن باید فاکتوریل عدد ۱ را محاسبه کنیم : پس به مرحله چهارم می رویم –>

مرحله ۴ : تابع fact با عدد یک فراخوانی می شود : fact(1) : بررسی می شود آیا عدد یک کوچکتر مساوی یک است که شرط درست بوده و یک را به عنوان خروجی برمی گرداند. پس برنامه بالاخره به نقطه پایان خود رسید حال همانطور که مرحله به مرحله پیش رفتیم باید مرحله مرحله راه آمده را بازگردیم :

مرحله ۳ : ۲*۱

مرحله ۲ : ۳*۲*۱

مرحله ۱ : ۴*۳*۲*۱

 

برای درک بهتر می توانید به شکل زیر نیز توجه نمائید :

مثال بعدی : فاکتوریل عدد ۵ :

همچنین برای درک بهتر زیربرنامه بازگشتی ، گیفی از تابع فاکتوریل قرار دادیم :

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *