فرادرستوابع بازگشتی در پایتون — راهنمای گام به گام
در آموزش‌های پیشین مجله فرادرس، با توابع بازگشتی آشنا شدیم. در این آموزش، مطالبی را درباره روش پیاده سازی توابع بازگشتی در پایتون بیان می‌کنیم.
تابع در ریاضیات
توابع مفاهیمی در ریاضیات و برنامه‌نویسی هستند که انجام برخی اعمال و دستورات را تسهیل می‌کنند.
توابع در ریاضیات چند مشخصه دارند:
- می‌توانند یک یا چند ورودی دریافت کنند.
- می‌توانند یک یا چند خروجی داشته باشند.
- می‌توانند روی ورودی‌ها اعمالی انجام داده و در خروجی برگردانند به شرطی که به ازای ورودی‌های یکسان همواره خروجی مشخصی تولید کنند.
برای مثال، $$f(x)=x^2$$ یک تابع با یک ورودی و یک خروجی است، در ضمن به ازای ورودی ثابت $$x$$ همواره مقدار $$x^2$$ را برمی‌گرداند.
تابع $$ f (x,y)=\frac x y $$ نیز یک تابع با دو ورودی و یک خروجی است.
برعکس موارد فوق، رابطه $$f(x,y)=x±y$$ یک تابع نیست، زیر به ازای برخی مقدایر از $$y$$ دو خروجی متمایز تولید می‌کند.
تابع در برنامه نویسی
اما در برنامه نویسی، مفهوم تابع اندکی متفاوت‌تر است:
1. یک تابع می‌تواند هیچ نوعی از ورودی نداشته باشد:
1import time
2
3def ReturnTime():
4 return time.time()۲. یک تابع می‌تواند هیچ نوعی از خروجی نداشته باشد:
1def PrintHorizentalLine():
2 print('_'*50)3. یک تابع می‌تواند با گرفتن ورودی‌های یکسان، خروجی‌های متفاوتی تولید کند:
1import numpy as np
2
3def SelectRandom(S:str):
4 N = len(S)
5 i = np.random.uniform(0,N)
6 return S[i]به این ترتیب، مشاهده می‌کنیم که توابع در برنامه‌نویسی می‌توانند برخی از مشخصه‌های توابع در ریاضیات را نداشته باشند.
برای یادگیری برنامه‌نویسی با زبان پایتون، پیشنهاد می‌کنیم به مجموعه آموزش‌های مقدماتی تا پیشرفته پایتون فرادرس مراجعه کنید که لینک آن در ادامه آورده شده است.
- برای مشاهده مجموعه آموزش‌های برنامه نویسی پایتون (Python) — مقدماتی تا پیشرفته + اینجا کلیک کنید.
توابع بازگشتی در پایتون
توابع بازگشتی توابعی هستند که با گرفتن یک ورودی، می‌توانند پس از عملیاتی دوباره خود را فراخوانی کنند.
برای مثال تابع زیر پس از فراخوانی تا زمان بروی خطا، به چاپ کردن جمله Hello World ادامه خواهد داد:
1def HW():
2 print('Hello World')
3 HW()یا تابع زیر به ترتیب اعداد $$n$$ تا بی‌نهایت را چاپ خواهد کرد:
1def Count(n:int):
2 print(n)
3 Count(n+1)به این ترتیب، فراخوانی تابع توسط خودش مشهود است.
توابع بازگشتی چه کاربردی دارند؟
در ادامه، به برخی از کاربردهای توابع بازگشتی اشاره می‌کنیم.
فاکتوریل
فاکتوریل یک عدد صحیح به صورت زیر تعریف می‌شود:
$$ \large n !=n \times(n-1) \times(n-2) \ldots 2 \times 1, \quad 0 !=1 !=1 $$
برای پیاده‌سازی تابع فاکتوریل می‌توان به صورت زیر نوشت:
1def Factorial(N:int):
2 if N == 0 or N == 1:
3 F = 1
4 else:
5 F = 1
6 for i in range(1, N+1):
7 F *= i
8 return Fبه این ترتیب، تابع مورد نظر کار خواهد کرد.
حال اندکی رابطه گفته‌شده را تغییر می‌دهیم:
$$ \large n !=n \times(n-1) \times(n-2) \ldots 2 \times 1=n \times(n-1) ! $$
به این ترتیب، می‌تواند فاکتوریل عدد $$n$$ را به فاکتوریل عدد $$n-1$$ ربط داد. از این ویژگی بازگشتی می‌توان به صورت زیر استفاده کرد:
1def Factorial(N:int):
2 if N == 0 or N == 1:
3 return 1
4 else:
5 return N * Factorial(N-1)به این ترتیب، پیاده‌سازی تابع مورد نظر در خطوط کمتر و به راحتی انجام می‌شود.
دنباله فیبوناچی
دنباله فیبوناچی به صورت زیر تعریف می‌شود:
$$ \large F_{n}=F_{n-1}+F_{n-2}, \quad F_{1}=F_{2}=1 $$
به این ترتیب، اگر بخواهیم این تابع را به شکل معمولی پیاده‌سازی کنیم خواهیم داشت:
1def Fibonacci(N:int):
2 if N == 1 or N == 2:
3 F = 1
4 else:
5 a = 1
6 b = 1
7 for _ in range(N-2):
8 F = a + b
9 a = b
10 b = F
11 return Fحال اگر با استفاده از رابطه بازگشتی همین تابع را پیاده‌سازی کنیم خواهیم داشت:
1def Fibonacci(N:int):
2 if N == 1 or N == 2:
3 return 1
4 else:
5 return Fibonacci(N-1) * Fibonacci(N-2)به این ترتیب، مشاهده می‌کنیم که کدنویسی مورد نیاز برای توابع بازگشتی کمتر است و احتمال خطا نیز پایین است.
مورد فوق حالت‌های مربوط به پیاده‌سازی روابط ریاضی بودند. فرض کنید لیستی نامنظم و تودرتو به شکل زیر داریم:
$$ \large L=[1,2,[3,[4],[5], 6,7], 8,[[9]], 10] $$
و از ما خواسته شده است با نوشتن تابعی، لیست‌های داخلی را ساده کرده و در نهایت به یک لیست واحد برسیم. برای حل این مسئله به شکل توابع معمولی، نیاز به کدنویسی زیادی است و یک راه‌حل محتمل برای حل آن، استفاده از توابع بازگشتی است.
یک تابع برای ساده‌سازی این لیست می‌نویسم که در ورودی لیست مورد نظر را می‌گیرد:
1def Simplify(L:list):حال یک لیست خالی برای خروجی ایجاد می‌کنیم:
1def Simplify(L:list):
2 O = []حال به ازای تک تک موارد داخل لیست ورودی، بررسی می‌کنیم که آیا یک عدد وجود دارد یا یک لیست:
1def Simplify(L:list):
2 O = []
3 for i in L:
4 if isinstance(i, int):
5
6 else:حال در صورت برقراری شرط، عضو مورد نظر را به لیست خروجی اضافه می‌کنیم و در صورت عدم برقراری شرط، خود تابع را بر روی عضو مورد نظر اعمال کرده و خروجی آن را به لیست خروجی اضافه می‌کنیم:
1def Simplify(L:list):
2 O = []
3 for i in L:
4 if isinstance(i, int):
5 O.append(i)
6 else:
7 O.extend(Simplify(i))
8 return Oبه این ترتیب، تابع آماده است.
حال آن را بر روی لیست آورده شده اعمال می‌کنیم:
1L = [1, 2, [3, [4], [5], 6, 7], 8, [[9]], 10]
2
3L2 = Simplify(L)
4
5print(L2)و در خروجی به نتیجه زیر می‌رسیم:
$$ \large [1,2,3,4,5,6,7,8,9,10] $$
که خروجی مطلوب ما است.
جمع‌بندی
در این آموزش، با توابع بازگشتی در پایتون آشنا شدیم و مثال‌های از آن را بررسی کردیم.
برای مطالعه بیشتر می‌توان موارد زیر را بررسی کرد:
- بیشترین دفعات ممکن برای Recursion
- اثر Recursion بر سرعت برنامه
- اثر حافظه و سرعت توابع بازگشتی
- مقایسه سرعت توابع بازگشتی با توابع معادل عادی
- ارتباط بین فراکتال‌ها (Fractals) و توابع بازگشتی
