آشنایی با مفهوم Recursive Function و نحوۀ پیاده‌سازی آن در زبان برنامه‌نویسی پایتون

در این مقاله قصد داریم تا به بررسی مفهوم Recursion پرداخته و کاربرد آن در حل مسائل را تشریح کنیم و ببینیم چگونه می‌توان یک به اصطلاح Recursive Function برای حل یک مسئلۀ کاربردی در زبان برنامه‌نویسی پایتون پیاده‌سازی کرد.

Recursion به معنای حل یک مسئله با به‌کارگیری از خودش یا انجام یک پروسۀ پیچیده با تقسیم آن به چندین پروسۀ زیرشاخۀ ساده است که در ادامه حل هر یک به صورت بازگشتی صورت می‌گیرد. در توسعۀ نرم‌افزار نیز Recursive Funtion (تابع بازگشتی) به مفهومی اشاره دارد که در آن فانکشن‌ها به منظور حل یک مسئلۀ پیچیده، به صورت بازگشتی خودشان را صدا می‌زنند به طوری که با انجام یکسری تَسک زیرشاخه به صورت تکراری، در نهایت مسئلۀ مد نظر حل می‌شود.

آشنایی با کاربرد توابع بازگشتی در حل مسائل
شاید تاکنون در زندگی روزمرۀ خود با برخی مسائل پیچیده برخورد کرده باشید که حل آن‌ها در نگاه اول دشوار به نظر برسد اما این در حالی است که چنانچه هر یک از این مسائل را به چندین مسئلۀ زیرشاخۀ کوچک تقسیم کنید، می‌بینید که به سادگی قابل‌حل هستند. در واقع، این مفهوم به تفکر بازگشتی اشاره دارد که در توسعۀ نرم‌افزار نیز مورد استفاده قرار می‌گیرد به طوری که توابع بازگشتی دائماً خود را فراخوانی می‌کنند و بدین ترتیب در هر بار فراخوانی بخشی کوچک از مسئله حل شده و این پروسه به صورت بازگشتی (یا بهتر بگوییم تکراری) تا زمانِ حل کامل مسئلۀ اصلی ادامه می‌یابد.

پیش از این گفتیم که نکتۀ کلیدی در مورد توابع بازگشتی شکستن مسئله به مسائل کوچک‌تر تا جایی است که به سادگی قادر به اجرای آن باشیم که در اصطلاح برنامه‌نویسی به این حالت Base Case یا «نقطۀ شروع» گفته می‌شود که وقتی مسئلۀ اصلی را به نمونه‌های ساده‌تر از همان مسئلهٔ اصلی تقسیم می‌کنیم و با حل هر یک به صورت بازگشتی به حالت ابتدایی نزدیک می‌شویم، این مفهوم تحت عنوان Recursive Case شناخته می‌شود.

حال به منظور درک بهتر حل مسائل به صورت بازگشتی در زبان برنامه‌نویسی پایتون، در ادامه مسئله‌ای را مد نظر قرار می‌دهیم که آن را با استفاده از یک راه‌حل غیرِبازگشتی پیاده‌سازی کرده بدین صورت که هر یک از آیتم‌های داخلی یک آبجکت از جنس لیست را با هم جمع کرده و در خروجی چاپ می‌کنیم سپس به صورت بازگشتی نیز راه‌کار مذکور را پیاده‌سازی می‌کنیم (به منظور آشنایی با دیتا تایپ لیست و کاربرد آن در زبان برنامه‌نویسی پایتون می‌توانید به آشنایی با دیتا تایپ لیست در زبان برنامه‌نویسی پایتون مراجعه نمایید.)

نحوۀ پیاده‌سازی مسئله به صورت غیر بازگشتی
در این مرحله، مسئلۀ مد نظر را به منظور جمع جبری آیتم‌های داخلی یک لیست بدون استفاده از تابع بازگشتی و با یک حلقۀ for ساده پیاده‌سازی می‌کنیم که برای این منظور کدی مانند زیر خواهیم داشت:

def sum(list):
    sum = 0
    for i in range(0, len(list)):
        sum = sum + list[i]
    return sum

در کد فوق فانکشنی تحت عنوان ()sum با یک پارامتر ورودی به نام list تعریف کرده‌ایم و در آن متغیری به نام sum تعریف کرده و مقدار اولیۀ آن را برابر 0 قرار داده‌ایم که قرار است تا مجموع اعداد آیتم‌های داخلی را نگهداری کند و در ادامه یک حلقۀ for داریم که در آن دو فانکشن از پیش تعریف‌شده تحت عناوین ()range و ()len را فراخوانی کرده‌ایم که بدین ترتیب فانکشن دوم طول لیست مد نظر را ریترن کرده و به فانکشن ()range می‌دهد که در نتیجه یکسری عدد صحیح در بازۀ 0 تا طول لیست مد نظر تولید می‌شود. در واقع، این دستور بدین منظور پیاده‌سازی شده است تا کدهای داخل حلقۀ for به تعداد طول لیست ورودی تکرار شده و به عبارتی تک‌تک آیتم‌های لیست را پیمایش کند.

سپس در ادامه گفته‌ایم هر یک از آیتم‌های داخلی لیست با مقدار قبلیِ منتسب به متغیر sum جمع شده و مقدار جدیدِ حاصله مجدداً به متغیر sum منتسب شود و در نهایت آخرین مقدار نگهداری‌شده در این متغیر در خروجی ریترن شود به طوری که فراخوانی فانکشن فوق به صورت زیر خواهد بود:

print(sum([5, 7, 3, 8, 10]))

در واقع، فانکشن ()sum را با یک آرگومان ورودی از جنس لیست و متشکل از مقادیر عددی فراخوانی کرده‌ایم که حلقۀ for به ازای هر یک از آن‌ها تکرار شده و جمع مقادیر توسط فانکشن ()print در خروجی ریترن می‌شود که در نهایت خروجی حاصل از کد فوق عدد 33 خواهد بود.

نحوۀ پیاده‌سازی مسئله با به‌کارگیری مفهوم ریکرسیو
حال در ادامه قصد داریم تا مسئلۀ فوق را با به‌کارگیریِ یک تابع بازگشتی پیاده‌سازی کنیم که برای این منظور کدی مانند خواهیم داشت:

def sum(list):
    if len(list) == 1:
        return list[0]
    else:
        return list[0] + sum(list[1:])

در تفسیر کد فوق باید بگوییم که فانکشنی تحت عنوان ()sum با یک پارامتر ورودی به نام list تعریف کرده‌ایم و در ادامه یک دستور شرطی قرار داده‌ایم که در آن گفته‌ایم چنانچه طول لیست برابر با ۱ باشد و به عبارتی لیست مد نظر تنها یک عضو داشته باشد، همان یک عضو را در خروجی ریترن کند (این دستور در واقع حالت Base Case می‌باشد) و در غیر این صورت آیتم مربوط به اندیس شمارۀ 0 را از لیست برداشته و با خروجی ریترن‌شده از فانکشن ()sum جمع کند که به صورت بازگشتی با آرگومان ورودی معادل باقی آیتم‌های لیست فراخوانی شده است. در واقع، دستور [:list[1 به منظور دسترسی به برخی آیتم‌های مد نظر از لیست به کار گرفته می‌شود که در ابتدا اندیس آیتم اول سپس علامت : و در ادامه اندیس مربوط به آیتم دوم درج می‌شود و بدین ترتیب در مثال فوق قصد داریم تا به آیتم‌هایی با اندیس 1 تا آیتم انتهایی لیست دسترسی بیایم به طوری که فانکشن ()sum با آرگومان ورودی معادل آیتم منتسب به اندیس 1 از لیست تا آیتم انتهایی آن فراخوانی شود. با این توضیحات، در هر بار فراخوانی فانکشن ()sum در داخل خود این فانکشن، به حالت ابتدایی مسئله کمی نزدیک می‌شویم (این دستور حالت Recursive Case می‌باشد.)

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

print(sum([5, 7, 3, 8, 10]))

مراحل اجرا در این فانکشن بدین صورت می‌باشد:

sum([5, 7, 3, 8, 10])
5 + sum([7, 3, 8, 10])
5 + 7 + sum([3, 8, 10])
5 + 7 + 3 + sum([8, 10])
5 + 7 + 3 +  8 + sum([10])
5 + 7 + 3 +  8 + 10
5 + 7 + 3 +  18
5 + 7 + 21
5 + 28
33

در ابتدا فانکشن ()sum با لیستی از اعداد به عنوان آرگومان ورودی فراخوانی شده و در ادامه شرط if چک می‌کند که آیا لیست مد نظر تنها یک عضو دارد یا خیر که شرط برقرار نبوده و دستور else اجرا می‌شود بدین صورت که اولین عضو لیست (عدد 5) را برداشته و با خروجی حاصل از فراخوانی فانکشن ()sum جمع می‌كند كه در اين مرحله فانكشن مذكور به صورت بازگشتی با آرگومان ورودی معادل باقی اعضای لیست یا به عبارتی از اندیس 1 به بعد و به صورت [10 ,8 ,3 ,7] فراخوانی شده است. در مرحلۀ بعدی که فانکشن ()sum با آرگومان ورودیِ [10 ,8 ,3 ,7] فراخوانی و اجرا شده است شرط if چک می‌شود و طول لیست برابر با 1 نبوده و از همین روی دستورات داخل else اجرا می‌شوند و این بار آیتم مربوط به اندیس شمارۀ 0 از لیست جاری (عدد 7) از لیست خارج می‌شود تا با عدد قبلی و خروجی حاصل از فراخوانی فانکشن ()sum با آرگومان ورودی مربوط به باقی اعضای لیست از اندیس 1 به بعد و به صورت [10 ,8 ,3] جمع شود.

فرآیند فوق‌الذکر تا زمانی ادامه می‌یابد که فراخوانی فانکشن ()sum منجر به ریترن شدن یک مقدار در خروجی گردد؛ به عبارت بهتر، تا زمانی که طول لیست برابر با 1 شود و همان‌طور که می‌بینید در سطر پنجم خروجی حاصل از فانکشن (sum(10 برابر با عدد 10 شده چرا که یک آیتم بیشتر داخل این لیست وجود ندارد و از همین روی تمامی آیتم‌های لیست به صورت بازگشتی با هم جمع می‌شوند که در نهایت این تابع بازگشتی عدد 33 را در خروجی ریترن کرده و توسط فانکشن ()print چاپ می‌شود.

جمع‌بندی
در این مقاله به معرفی مفهوم Recursion و نحوۀ پیاده‌سازی فانکشن‌هایی از این جنس در قالب یک مثال کاربردی پرداختیم و نیاز به توضیح نیست که پیاده‌سازی توابع به صورت بازگشتی منجر به سادگی و تمیزی کد می‌شود و یک راه‌حل مناسب به منظور شکستن تَسک‌های پیچیده به مسائل زیرشاخۀ کوچک‌تر است. همچنین به منظور درک بهتر مفهوم تابع بازگشتی و کاربردهای آن در سایر زبان‌های برنامه‌نویسی، توصیه می‌کنیم به مقالات زیر مراجعه نمایید:

- Recursive Function چیست و چگونه یک تابع بازگشتی با استفاده از JS پیاده‌سازی کنیم؟
- تابع بازگشتی چیست و چگونه آن را در زبان PHP پیاده‌سازی کنیم؟
- Recursive Function چیست و چگونه آن را در زبان جاوا پیاده‌سازی کنیم؟

نکتۀ قابل‌توجه در مورد توابع بازگشتی این است که اجرای توابع بازگشتی خصوصاً در پروژه‌های سنگین هزینۀ بالایی از نظر اجرا و حافظه برای سیستم به دنبال دارد و ممکن است همواره بهینه‌ترین راه‌حل برای پیاده‌سازی برخی تَسک‌ها نباشد به طوری که این احتمال وجود دارد تا در یک حلقۀ بازگشتی بی‌نهایت گرفتار شده و توابع مد نظر تا بی‌نهایت خودشان را فراخوانی کنند که این امر منجر به کِرش کردن سیستم می‌شود. به طور کلی، از جمله کاربردهای توابع بازگشتی می‌توان به مسائلی همچون تغییر نام دایرکتوری‌های سیستم، پیمایش دیتا استراکچرها و انجام پردازش‌های مد نظر روی هر یک از آیتم‌های داخلی آن‌ها، ایجاد منوهای تودرتو و مواردی از این دست اشاره کرد.