مسیر رتبه‌برترشدن در کنکور ارشد مهندسی کامپیوتر و IT
ثبت‌نام رایگان
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

توضیح تابع بازگشتی، دنباله بازگشتی و رابطه بازگشتی

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

توابع بازگشتی نوعی از توابع هستند که به گذشته‌شان مربوط هستند و به‌عنوان خروجی، نام خود را صدا می‌زنند و بر اثر این فراخوانی تابع بار دیگر اجرا می‌شود. این نوع از توابع جزو مفاهیم مهم برنامه نویسیبرنامه نویسی کامپیوتر چیست و چطور می توانید یک برنامه نویس موفق شوید؟برنامه نویسی کامپیوتر چیست و چطور می توانید یک برنامه نویس موفق شوید؟در عصر فعلی برنامه‌نویسی یکی از پرطرفدارترین شغل‌های دنیاست، دغدغه‌‌ای افرادی که می‌خواهند در مسیر برنامه‌نویس شدن قدم بردارند این است که نمی‌دانند از کجا باید شروع کنند، در این صفحه هر آن چه برای تبدیل شدن به یک برنامه نویس حرفه ای نیاز دارید در اختیارتان قرار گرفته است هستند و دارای کاربردهای متنوعی می‌باشند و استفاده درست از آنها، سرعت اجرای برنامه‌ها را افزایش می‌دهد. برای بررسی کامل این توابع، ابتدا مروری بر تابع می‌کنیم و می‌بینیم که یک تابع تحت چه تغییراتی تبدیل به تابع بازگشتی می‌شود.

تابع بازگشتی چیست؟

توابع یکی از اساسی‌ترین مفاهیم در دنیای برنامه نویسی هستند. این ساختار به ما کمک می‌کند تا از تکرار جلوگیری کنیم و برنامه‌هایی با خوانایی بالا بنویسیم. هر تابع شامل سه بخش اساسی است: ورودی، بدنه و خروجی تابع. یک تابع در برنامه نویسی می‌تواند هیچ ورودی نداشته باشد و یا مقادیر مختلف با انواع (Types) متفاوتی را دریافت کند، از جمله عدد صحیح (Integer)، رشته (String)، عدد اعشاری (Float) و یا حتی یک تابع. خروجی تابع نیز به‌همین شکل است. بدنه هر تابعی می‌تواند به هر صورتی که برنامه‌نویس تصمیم می‌گیرد طراحی شود تا کاری را که تابع برای آن نوشته شده است را انجام دهد. اگر بخواهیم ساختار یک تابع را نمایش دهیم، به‌شکل زیر خواهد بود.

def sum(x, y):
  return x + y

این تابع که به نام sum نام‌گذاری و به زبان پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته نوشته شده است، دو متغیر به نام x و y دریافت کرده و جمع آنها را باز می‌گرداند. خروجی تابع همان‌طور که ملاحظه کردید، با دستور return مشخص می‌شود که در مثال قبل، مقدار بازگشتی می‌تواند یک عدد صحیح، عدد اعشاری، و یا هر نوعی از داده باشد. اما اگر در مقابل دستور return نام خود تابع را بنویسیم چه اتفاقی می‌افتد؟ اینجاست که وارد بحث توابع بازگشتی می‌شویم.

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

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

def factorial(n):
  if n == 0:	
    return 1
  else:
    return n * factorial(n - 1)

حال با جایگذاری عدد 5 به جای n به بررسی و نحوه اجرای این تابع می‌پردازیم. زمانی که تابع با عدد 5 فراخوانی می‌شود اتفاق‌های زیر رخ می‌دهد:

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

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

نمودار اجرای تابع بازگشتی فاکتوریل با مقدار اولیه 5

یک راه دیگر برای درک بهتر روش کار این تابع، استفاده از ابزار اشکال زدایی (Debugging)دیباگ چیست؟ معرفی روش‌‌ها و ابزارهای دیباگینگ(اشکال زدایی)دیباگ چیست؟ معرفی روش‌‌ها و ابزارهای دیباگینگ(اشکال زدایی)این مقاله عالی مفاهیم دیباگ (debug)، دیباگینگ (Debugging) یا همان اشکال زدایی، دیباگر (Debugger) را معرفی و همچنین روش‌‌ها و ابزارهای دیباگینگ را بررسی کرده پایتون است. روش استفاده از این ابزار در نرم‌افزار VSCode به این صورت است که ابتدا باید خطی را که می‌خواهید روند دیباگ کردن از آن شروع شود (Breakpoint) را انتخاب کنید. این کار به‌وسیله ایجاد نقطه قرمز رنگ با کلیک در کنار شماره خط موردنظر انجام می‌شود.

ایجاد یک نقطه شکست برای اجرای دیباگ

سپس از نوار ابزار سمت چپ گزینه Run and Debug را انتخاب و برنامه را اجرا می‌کنیم.

نحوه اجرای دیباگ

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

نمایش اجرای دیباگ برای تابع بازگشتی محاسبه فاکتوریل

اگر به بخش Call Stack دقت کنید، می‌بینید که مقدار بازگشت داده شده ابتدا در حافظه Stack قرار می‌گیرد و سپس بعد از بازگشت همه فراخوانی‌ها، به ترتیب همه آن‌ها محاسبه شده و در انتها مقدار نهایی که 120 می‌باشد، بازگردانده می‌شود.

صورت پایه و صورت بازگشتی

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

صورت پایه و صورت بازگشتی در تابع بازگشتی فاکتوریل

کاربرد توابع بازگشتی

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

مسئله برج‌ هانوی یکی دیگر از مسائلی است که به‌صورت بازگشتی حل می‌شود و پیاده‌سازی آن به‌وسیله حلقه‌ها بسیار پیچیده است:

def tower_of_Hanoi(a, b, c, n):
  if n == 1:
    print(f"{a} -> {c}")
  else:
    tower_of_Hanoi(a, c, b, n - 1)
    print(f"{a} -> {c}")
    tower_of_Hanoi(b, a, c, n - 1)

tower_of_Hanoi("A", "B", "C", 3)

این قطعه کد مسئله برج هانوی را برای سه دیسک حل می‌کند و خروجی آن به شکل زیر است.

نتیجه اجرای کد برج هانوی

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

OPTIONS = [1, 2, 3]
while True:
  user = int(input("Select 1, 2 or 3: "))
  if user in OPTIONS:
    print(f"You selected '{user}'")
    break
  else:
    print("Please select 1, 2 or 3!")

هر زمان که کاربر مقداری را که قابل قبول است (مقادیر داخل لیست OPTIONS) را وارد کند، پیغام تایید چاپ شده و حلقه با دستور Break شکسته شده و ادامه‌ برنامه اجرا می‌شود. ولی می‌توان این برنامه را به وسیله تابعی با ساختاری مشابه به توابع بازگشتی به‌صورت زیر نوشت:

def get_input(OPTIONS):
  user = int(input(f"Select between {OPTIONS}"))
  if user in OPTIONS:
    return user
  else:
    print(f"Please select {OPTIONS}")
    return get_input(OPTIONS)

get_input([1, 2, 3])

عملکرد این دو قطعه کد یکسان می‌باشد و تنها تفاوت آنها، روش پیاده‌سازی است. مشاهده می‌شود که متغیر OPTIONS به‌عنوان آرگومان به تابع داده شده است که می‌توان آن را بسته به نیاز تغییر داد. پس از این که کاربر مقداری را وارد می‌کند، چک می‌شود که آیا آن مقدار قابل قبول است یا خیر، اگر قابل قبول باشد شرط If اجرا شده و تابع مقدار وارد شده را برمی‌گرداند و اگر مقدار وارد شده قابل قبول نباشد، تابع با چاپ پیام به کاربر این مورد را اطلاع می‌دهد و با فراخوانی دوباره تابع با متغیر OPTIONS، از کاربر می‌خواهد که دوباره مقداری را وارد کند. این که برنامه‌نویس کدام یک از روش‌های گفته شده را انتخاب کند وابسته به نیاز و روش پیاده‌سازی برنامه است. هرچند می‌توان قطعه کد اول را که با حلقه پیاده‌سازی شده بود، با استفاده از توابع معمولی نیز پیاده‌سازی کرد؛ ولی به صورت کلی بسیاری از برنامه‌ها هستند که می‌توان این ساختار را برایشان در نظر گرفت.

مزایا و معایب توابع بازگشتی

مزایا و معایب توابع بازگشتی به شرح زیر می‌باشد:

مزایای توابع بازگشتی

معایب توابع بازگشتی

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

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

محاسبه مرتبه زمانی به روش مستر (Master) و بهینه سازی توابع بازگشتی

یکی از ساده‌ترین روش‌های محاسبه مرتبه زمانی توابع بازگشتی، استفاده از روش مستر است. این متد برای توابعی کاربرد دارد که فرم رابطه بازگشتی آنها به شکل $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=aT}\left(\frac{\mathrm{n}}{\mathrm{b}}\right)\mathrm{+f}\left(\mathrm{n}\right)$ است که برای این معادله قوانین برقرار است:

$\mathrm{if\ }{\mathrm{n}}^{\mathrm{a}}\mathrm{>f}\left(\mathrm{n}\right){\mathrm{then} \mathrm{T}\left(\mathrm{n}\right)\ }\mathrm{\in }\mathrm{\theta }\left({\mathrm{n}}^{\mathrm{a}}\right)$

$\mathrm{if\ }{\mathrm{n}}^{\mathrm{a}}\mathrm{}\mathrm{f}\left(\mathrm{n}\right){\mathrm{then} \mathrm{T}\left(\mathrm{n}\right)\ }\mathrm{\in }\mathrm{\theta }\left(\mathrm{f}\left(\mathrm{n}\right)\right)$

$\mathrm{if\ }{\mathrm{n}}^{\mathrm{a}}\mathrm{=}\mathrm{f}\left(\mathrm{n}\right){\mathrm{then} \mathrm{T}\left(\mathrm{n}\right)\ }\mathrm{\in }\mathrm{\theta }\left(\mathrm{f}\left(\mathrm{n}\right)\mathrm{\times }{\mathrm{log} {\mathrm{log} \mathrm{n}\ }\ }\right)$

توجه شود که منظور از علامت‌های بزرگ‌تر، کوچک‌تر و مساوی، مقایسه رشد توابع است؛ به عبارت دیگر، این که کدام طرف از معادله رشد بیشتری به ازای nهای بزرگ داشته باشد، مشخص‌کننده مرتبه در این فرم از معادلات خواهد بود (در بحث محاسبه رشد توابع و مرتبه زمانی همیشه فرض می‌کنیم متغیر مقدار بزرگی دارد).

def recursive_func(n):
    if n <= 1:
        return n * n
    else:
        return recursive_func(n - 1) + recursive_func(n - 2) + n

رابطه بازگشتی از صورت بازگشتی تابع (بخشی از تابع که نام تابع فراخوانی می‌شود) به‌دست می‌آید؛ برای مثال فرض کنید قصد داریم رابطه بازگشتی تابع زیر را به‌دست آوریم:

در ابتدا باید بررسی کنیم که در صورت بازگشتی، تابع با چه مقداری از n فراخوانی می‌شود. همان‌طور که مشخص است، تابع recursive_func یک بار با $\mathrm{n-1}$ و یک بار با $\mathrm{n-2}$ فراخوانی می‌شود؛ بنابراین تا به این جا خواهیم داشت:

$\mathrm{h}\left(\mathrm{n}\right)\mathrm{=h}\left(\mathrm{n-1}\right)\mathrm{+h}\left(\mathrm{n-2}\right)$

که $\mathrm{h}\left(\mathrm{n}\right)$ رابطه بازگشتی‌مان است. سپس باید عملی را مشخص کنیم که در این بخش از تابع رخ می‌دهد. برای روشن‌تر شدن موضوع، می‌توانیم عمل جمع را در نظر بگیریم. در صورت بازگشتی این تابع، دو بار عمل جمع صورت می‌گیرد که می‌توان آن را در معادله لحاظ کرد. ($\mathrm{f}\left(\mathrm{n}\right)$ در فرم معادله مستر اشاره به این موضوع دارد)

$\mathrm{h}\left(\mathrm{n}\right)\mathrm{=h}\left(\mathrm{n-1}\right)\mathrm{+h}\left(\mathrm{n-2}\right)\mathrm{+2}$

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

from math import floor

def power_optimal(m, n):
  if n == 0:
    return 1
  if n % 2 == 0:
    return power_optimal(m, n / 2) ** 2
  elif n % 2 != 0:
    return power_optimal(m, floor(n / 2) ** 2) * m

تابع power_optimal پیاده‌سازی بهینه بازگشتی برای محاسبه توان است که برای بررسی بهینه بودن، نیاز است مرتبه زمانی آن را محاسبه کنیم. ابتدا رابطه بازگشتی آن را به‌دست می‌آوریم. مشاهده می‌کنیم که در صورت بازگشتی، تابع power_optimal با مقدار $\frac{\mathrm{n}}{\mathrm{2}}$ فراخوانی می‌شود (باید به دو نکته دقت کنید، اول اینکه چون فقط متغیر n در پایان دادن به تابع تاثیرگذار است، در رابطه بازگشتی می‌بایست فقط n را در نظر گرفت و دوم، کف و سقف گرفتن از تقسیم، تاثیر زیادی در مرتبه زمانی به ازای n با مقدار زیاد نخواهد داشت)، سپس توان را به‌عنوان عملی در نظر می‌گیریم که در صورت بازگشتی صورت می‌گیرد. در نتیجه معادله زیر به دست می‌آید:

$\mathrm{h}\left(\mathrm{n}\right)\mathrm{=h}\left(\frac{\mathrm{n}}{\mathrm{2}}\right)\mathrm{+1}$

با کمی دقت متوجه می‌شویم که فرم رابطه بازگشتی تابع power_optimal مشابه فرم کلی مستر است و می‌توانیم از این روش برای محاسبه مرتبه زمانی استفاده کنیم. با جایگذاری مقادیر $\mathrm{a}$، $\mathrm{b}$ و $\mathrm{f}\left(\mathrm{n}\right)$ به معادله زیر خواهیم رسید:

${\mathrm{n}}^{\mathrm{1}}\ ?\ 1\ 1=0\to {\mathrm{n}}^0\ ?\ 1\to 1=1\ \text{دو طرف معادله برابر شدند} \mathrm{\ }\to \mathrm{h}\left(\mathrm{n}\right)\mathrm{\in }\mathrm{\theta }\left(\mathrm{f}\left(\mathrm{n}\right)\mathrm{\times }{\mathrm{log} {\mathrm{log} \mathrm{n}\ }\ }\right)\mathrm{f}\left(\mathrm{n}\right)\mathrm{=1}\mathrm{\to }\mathrm{h}\left(\mathrm{n}\right)\mathrm{\in }\mathrm{\theta }\left({\mathrm{log} {\mathrm{log} \mathrm{n}\ }\ }\right)$

بنابراین مرتبه این تابع از $\mathrm{\theta }\left({\mathrm{log}\mathrm{\ } {\mathrm{log}\mathrm{\ } \mathrm{n}\ }\ }\right)$ است. همان‌طور که اشاره شد، از توابع بازگشتی برای کاهش سرعت اجرا و افزایش کارایی برخی از الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد‌ها استفاده می‌شود ولی شاید برایتان سوال شده باشد که در عمل این کار چگونه صورت می‌گیرد و دلیل این محاسبات چیست؟ برای درک این موضوع، تابعی دیگر را برای محاسبه توان در نظر می‌گیریم.

def power_non_optimal(m, n):
  if n == 0:
    return 1
  else:
    return m * power_non_optimal(m, n - 1)

با کمی دقت متوجه خواهید شد که این تابع مقدار m را n بار در خودش ضرب می‌کند و هر بار خود را با فراخوانی می‌کند؛ بنابراین تابع به ازای هر مقدار n ،n بار بازگشت خواهد داشت  پس مرتبه آن از $\mathrm{\theta }\left(\mathrm{n}\right)$ است. در مقایسه با مرتبه تابع power_optimal، این تابع زمان بیشتری را صرف محاسبه می‌کند (برای درک بهتر با جایگذاری عددی بزرگ به جای n، مانند 1024، متوجه خواهید شد که تابع اول با 10 بار فراخوانی به پاسخ می‌رسد ولی تابع دوم با 1024 بار!)، برای درک ملموس‌تر به قطعه کد زیر توجه کنید:

import sys
import time
from math import floor

def power_optimal(m, n):
  if n == 0:
    return 1
  if n % 2 == 0:
    return power_optimal(m, n / 2) ** 2
  elif n % 2 != 0:
    return (power_optimal(m, floor(n / 2)) ** 2) * m
 
def power_non_optimal(m, n):
  if n == 0:
    return 1
  else:
    return m * power_non_optimal(m, n - 1)
 
sys.setrecursionlimit(4000)

start = time.time()
power_optimal(100, 2900)
end = time.time()
print(f"Optimal function: {end - start}")

start = time.time()
power_non_optimal(100, 2900)
end = time.time()
print(f"Non-optimal function: {end - start}")

نکته‌ای در ابتدا باید به آن اشاره کرد، دستور setrecursionlimit از کتابخانه sys است. این دستور باعث تغییر در محدودیت بازگشت در مفسر پایتون می‌شود و می‌توان با افزایش آن، حداکثر تعداد بازگشت‌های داخل برنامه را بیشتر کرد. با اجرای این برنامه می‌توان اختلاف سرعت اجرای دو تابع را به‌صورت تقریبی مشاهده کرد که این اندازه‌گیری نیز به‌وسیله کتابخانه Time صورت می‌گیرد.

خروجی اجرای برنامه مقایسه سرعت اجرای دو تابع بازگشتی توان

خروجی برنامه نشان می‌دهد که به ازای مقادیر بزرگ m و n، سرعت اجرای تابع بازگشتی بهینه بیشتر از سرعت اجرای تابع بازگشتی غیربهینه است. (البته باید توجه شود عوامل دیگری مانند سرعت پردازندهپردازنده (CPU) چیست؟ بررسی انواع، وظایف و کاربردهاپردازنده (CPU) چیست؟ بررسی انواع، وظایف و کاربردهاسی پی یو قلب کامپیوتر و کامپیوتر قلب دنیای کنونی است، بنابراین در این صفحه به معرفی و بررسی سی‌پی‌یو یا همان پردازنده مرکزی (CPU) پرداخته‌ شده، و بطور کامل توضیح داده‌ایم که CPU از چه بخش هایی تشکیل شده و هر بخش چه وظایف و مشخصاتی دارد. و مقدار حافظه بر سرعت پردازش اثرگذارند ولی تابع بهینه در هر شرایطی سرعت بیشتری دارد) و در نتیجه محاسبه مرتبه زمانی امری مهم در توابع بازگشتی است و از پیاده‌سازی توابع غیربهینه جلوگیری می‌کند.

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

در انتها جهت آشنایی با فرم توابع بازگشتی در زبان های برنامه نویسی مختلف، پیاده‌سازی دنباله فیبوناچی را به شش زبان پرکاربرد شامل: پایتون (Python)زبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته، جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است، جاوا اسکریپتجاوا اسکریپت چیست؟ معرفی زبان برنامه نویسی java scriptجاوا اسکریپت چیست؟ معرفی زبان برنامه نویسی java scriptزبان برنامه نویسی جاوا اسکریپت چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای JavaScript پرداخته و مبانی برنامه نویسی جاوا اسکریپت را آموزش داده، Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cاین مقاله عالی ابتدا توضیح می‌دهد که زبان برنامه نویسی c چیست، سپس به بررسی مزایا و معایب زبان C ، کاربردهای زبان سی ، و تفاوت بین C و ++C می‌پردازد، سی شارپسی شارپ چیست ⚡️سی شارپ به زبان سادهسی شارپ چیست ⚡️سی شارپ به زبان سادهاین صفحه عالی بررسی کرده که سی شارپ چیست و تاریخچه سی شارپ، محیط و ابزارهای سی شارپ، ویژگی های سی شارپ، مزایای سی شارپ و کاربرد و بازار کار سی شارپ را گفته و گولنگ (Golang) بررسی می‌کنیم.

تابع بازگشتی دنباله فیبوناچی در زبان پایتون

def fibonacci(n):
  if n <= 1:
    return n
  return fibonacci(n - 1) + fibonacci(n - 2)

تابع بازگشتی دنباله فیبوناچی در زبان جاوا

public static int fibonacci(int n) {
  if (n = 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

تابع بازگشتی دنباله فیبوناچی در زبان جاوا اسکریپت

function fibonacci(n) {
  if (n = 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

تابع بازگشتی دنباله فیبوناچی در زبان سی

int fibonacci(int n) {
  if (n = 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

static int fibonacci(int n) {
  if (n = 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

تابع بازگشتی فیبوناچی در گولنگ

func fibonacci(n int) int {
  if n = 1 {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}

جمع‌بندی

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

تابع بازگشتی چیست؟

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

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

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

مرتبه زمانی توابع بازگشتی چگونه محاسبه می‌شود؟

مرتبه زمانی توابع بازگشتی با استفاده از روش‌های مستر (Master)، درخت بازگشتی، بمب اتم و... به دست می‌آید.

بزرگ‌ترین مزیت توابع بازگشتی چیست؟

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

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (3 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام