تابع بازگشتی در برنامه نویسی پایتون

تابع بازگشتی در برنامه نویسی پایتون

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

بازگشت چیست؟

بازگشت (Recursion) روند تعریف چیزی از نظر خودش است.

مانند قرار دادن دو آینه موازی رو به روی هم است. هر شی در بین آنها به صورت بازگشتی منعکس می شود.

پیشنهاد ویژه : پکیج آموزش پروژه محور پایتون

تابع بازگشتی در  پایتون

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

تصویر زیر عملکرد یک تابع بازگشتی به نام recurse را نشان می دهد.

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

فاکتوریل یک عدد حاصلضرب تمام اعداد صحیح از ۱ به آن عدد است. به عنوان مثال ، فاکتوریل ۶ (با !۶ نشان داده می شود) ۷۲۰=۶*۵*۴*۳*۲*۱ است.

مثالی از یک تابع بازگشتی در پایتون

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("The factorial of", num, "is", factorial(num))

خروجی

The factorial of 3 is 6

در مثال بالا،() factorial یک تابع بازگشتی است که خود آن را فراخوانی می کند.

وقتی این تابع را با یک عدد صحیح مثبت فراخوانی می کنیم،  ضمن کاهش عدد به صورت بازگشتی فراخوانی می شود.

هر تابع فراخوانی عدد را با فاکتوریل عدد یک واحد کوچک‌تر از خودش ضرب می‌کند تا زمانی که برابر با یک شود.  فراخوانی بازگشتی را می توان در مراحل زیر بهتر توضیح داد.

factorial(3)          # 1st call with 3
۳ * factorial(2)      # 2nd call with 2
۳ * ۲ * factorial(1)  # 3rd call with 1
۳ * ۲ * ۱             # return from 3rd call as number=1
۳ * ۲                 # return from 2nd call
۶                     # return from 1st call

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

بازگشت هنگامی پایان می یابد که تعداد به ۱ کاهش یابد. به این شرط پایه می گویند.

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

مفسر پایتون برای جلوگیری از بازگشت های بی نهایت و در نتیجه سرریز شدن پشته (stack overflow)، عمق بازگشت را محدود می کند.

به طور پیش فرض، حداکثر عمق بازگشت ۱۰۰۰ است. اگر از این حد عبور کنید ، منجر به RecursionError می شود. بیایید به یکی از این شرایط نگاهی بیاندازیم.

def recursor():
    recursor()
recursor()

خروجی

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

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

• توابع بازگشتی کد را تمیز و زیبا نشان می دهد.
• یک مسئله پیچیده را می توان با استفاده از تابع بازگشتی به زیرمسئله های کوچک تر و ساده تری تقسیم کرد.
• تولید توالی با تابع بازگشتی آسان تر از استفاده از تکرار تو در تو است.

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

• بعضی اوقات به سختی می توان منطق پشت تابع بازگشتی را فهمید.
• فراخوانی بازگشتی پرهزینه (ناکارآمد) هستند زیرا حافظه و زمان زیادی را اشغال می کنند.
• دیباگ کردن یا عیب یابی از توابع بازگشتی سخت است.

منبع.

لیست جلسات قبل آموزش برنامه نویسی پایتون

1. آموزش نصب و اجرای برنامه نویسی پایتون
2. کلیدواژه ها و شناسه های برنامه نویسی پایتون
3. دستورات، تورفتگی ها و کامنت ها در برنامه نویسی پایتون
4. متغیرها، ثابت ها و لیترال ها در برنامه نویسی پایتون 
5. انواع داده ها در برنامه نویسی پایتون
6. تبدیل نوع در برنامه نویسی پایتون
7. ورودی، خروجی و وارد کردن در برنامه نویسی پایتون
8. عملگرها در برنامه نویسی پایتون
9. نام و دامنه در برنامه نویسی پایتون
10. دستور شرطی if…else در برنامه نویسی پایتون
11. حلقه for در برنامه نویسی پایتون
12. حلقه while در برنامه نویسی پایتون
13. دستورات break و continue در برنامه نویسی پایتون
14. دستور pass در برنامه نویسی پایتون
15. توابع در برنامه نویسی پایتون
16. آرگومان تابع در برنامه نویسی پایتون