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

در آموزش‌های پیشین مجله فرادرس، با توابع بازگشتی آشنا شدیم. در این آموزش، مطالبی را درباره روش پیاده سازی توابع بازگشتی در پایتون بیان می‌کنیم.

تابع در ریاضیات

توابع مفاهیمی در ریاضیات و برنامه‌نویسی هستند که انجام برخی اعمال و دستورات را تسهیل می‌کنند.

فیلم آموزش تابع در ریاضی و آمار ۲ – پایه یازدهم علوم انسانی (رایگان) در فرادرس

کلیک کنید

توابع در ریاضیات چند مشخصه دارند:

1. می‌توانند یک یا چند ورودی دریافت کنند.
2. می‌توانند یک یا چند خروجی داشته باشند.
3. می‌توانند روی ورودی‌ها اعمالی انجام داده و در خروجی برگردانند به شرطی که به ازای ورودی‌های یکسان همواره خروجی مشخصی تولید کنند.

برای مثال، $$f(x)=x^2$$ یک تابع با یک ورودی و یک خروجی است، در ضمن به ازای ورودی ثابت $$x$$ همواره مقدار $$x^2$$ را برمی‌گرداند.

تابع $$f (x,y)=\frac x y$$ نیز یک تابع با دو ورودی و یک خروجی است.

برعکس موارد فوق، رابطه $$f(x,y)=x±y$$ یک تابع نیست، زیر به ازای برخی مقدایر از $$y$$ دو خروجی متمایز تولید می‌کند.

تابع در برنامه نویسی

اما در برنامه نویسی، مفهوم تابع اندکی متفاوت‌تر است:

فیلم آموزش تابع در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

1. یک تابع می‌تواند هیچ نوعی از ورودی نداشته باشد:

۲. یک تابع می‌تواند هیچ نوعی از خروجی‌ نداشته باشد:

3. یک تابع می‌تواند با گرفتن ورودی‌های یکسان، خروجی‌های متفاوتی تولید کند:

به این ترتیب، مشاهده می‌کنیم که توابع در برنامه‌نویسی می‌توانند برخی از مشخصه‌های توابع در ریاضیات را نداشته باشند.

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

• برای مشاهده مجموعه آموزش‌های برنامه نویسی پایتون (Python) — مقدماتی تا پیشرفته + اینجا کلیک کنید.

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

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

برای مثال تابع زیر پس از فراخوانی تا زمان بروی خطا، به چاپ کردن جمله Hello World ادامه خواهد داد:

یا تابع زیر به ترتیب اعداد $$n$$ تا بی‌نهایت را چاپ خواهد کرد:

به این ترتیب، فراخوانی تابع توسط خودش مشهود است.

توابع بازگشتی چه کاربردی دارند؟

در ادامه، به برخی از کاربردهای توابع بازگشتی اشاره می‌کنیم.

فیلم آموزش حل روابط بازگشتی + مفاهیم کلیدی در فرادرس

کلیک کنید

فاکتوریل

فاکتوریل یک عدد صحیح به صورت زیر تعریف می‌شود:

$$\large n !=n \times(n-1) \times(n-2) \ldots 2 \times 1, \quad 0 !=1 !=1$$

برای پیاده‌سازی تابع فاکتوریل می‌توان به صورت زیر نوشت:

به این ترتیب، تابع مورد نظر کار خواهد کرد.

حال اندکی رابطه گفته‌شده را تغییر می‌دهیم:

$$\large n !=n \times(n-1) \times(n-2) \ldots 2 \times 1=n \times(n-1) !$$

به این ترتیب، می‌تواند فاکتوریل عدد $$n$$ را به فاکتوریل عدد $$n-1$$ ربط داد. از این ویژگی بازگشتی می‌توان به صورت زیر استفاده کرد:

به این ترتیب، پیاده‌سازی تابع مورد نظر در خطوط کمتر و به راحتی انجام می‌شود.

دنباله فیبوناچی

دنباله فیبوناچی به صورت زیر تعریف می‌شود:

$$\large F_{n}=F_{n-1}+F_{n-2}, \quad F_{1}=F_{2}=1$$

به این ترتیب، اگر بخواهیم این تابع را به شکل معمولی پیاده‌سازی کنیم خواهیم داشت:

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

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

فیلم آموزش شبیه سازی سری فیبوناچی و محاسبه عدد طلایی در سیمیولینک (رایگان) در فرادرس

کلیک کنید

مورد فوق حالت‌های مربوط به پیاده‌سازی روابط ریاضی بودند. فرض کنید لیستی نامنظم و تودرتو به شکل زیر داریم:

$$\large L=[1,2,[3,[4],[5], 6,7], 8,[[9]], 10]$$

و از ما خواسته شده است با نوشتن تابعی، لیست‌های داخلی را ساده کرده و در نهایت به یک لیست واحد برسیم. برای حل این مسئله به شکل توابع معمولی، نیاز به کدنویسی زیادی است و یک راه‌حل محتمل برای حل آن، استفاده از توابع بازگشتی است.

یک تابع برای ساده‌سازی این لیست می‌نویسم که در ورودی لیست مورد نظر را می‌گیرد:

حال یک لیست خالی برای خروجی ایجاد می‌کنیم:

حال به ازای تک تک موارد داخل لیست ورودی، بررسی می‌کنیم که آیا یک عدد وجود دارد یا یک لیست:

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

به این ترتیب، تابع آماده است.

فیلم آموزش محاسبات عددی – مرور و حل مساله در فرادرس

کلیک کنید

حال آن را بر روی لیست آورده شده اعمال می‌کنیم:

و در خروجی به نتیجه زیر می‌رسیم:

$$\large [1,2,3,4,5,6,7,8,9,10]$$

که خروجی مطلوب ما است.

فیلم مجموعه آموزش برنامه نویسی پایتون Python – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

جمع‌بندی

در این آموزش، با توابع بازگشتی در پایتون آشنا شدیم و مثال‌های از آن را بررسی کردیم.

برای مطالعه بیشتر می‌توان موارد زیر را بررسی کرد:

1. بیشترین دفعات ممکن برای Recursion
2. اثر Recursion بر سرعت برنامه
3. اثر حافظه و سرعت توابع بازگشتی
4. مقایسه سرعت توابع بازگشتی با توابع معادل عادی
5. ارتباط بین فراکتال‌ها (Fractals) و توابع بازگشتی