بازگشت چگونه کار می کند؟ با مثال کد توضیح داده شده است

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

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

بازگشت چیست؟

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

در اینجا یک مثال است:

def call_me():
    call_me()

در اینجا تابع خود را فراخوانی می کند که به آن بازگشت می گویند.

اما “خود را فراخوانی” فقط یک تعریف برنامه ای از بازگشت است. بازگشت شامل تجزیه یک مسئله به قطعات کوچکتر است تا جایی که نتوان آن را بیشتر تجزیه کرد. شما قطعات کوچک را حل می کنید و آنها را کنار هم می گذارید تا مشکل کلی حل شود.

قیاس زندگی واقعی بازگشت

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

تصور کنید در صف سواری دیزنی هستید و نمی دانید چند نفر از شما جلوتر هستند.

برای فهمیدن این موضوع، از فرد مقابل خود بپرسید.

آن شخص نیز نمی داند، بنابراین از فرد مقابل می پرسند.

این process ادامه می‌یابد تا این که سؤال به دست فرد جلوی خط می‌رسد و می‌بیند که هیچ‌کس جلوی او نیست و پاسخ می‌دهد که هیچ نفر جلوتر نیست.

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

وقتی فرد جلویی پاسخ می دهد، “0 نفر جلوتر هستند” نفر بعدی یکی را اضافه می کند و پاسخ می دهد “1 نفر جلوتر است” و غیره روی.

تا زمانی که پاسخ مستقیماً به شخص مقابل شما برسد، یک مورد دیگر اضافه می کند و به شما می گوید. به این ترتیب فقط با اضافه کردن می توانید موقعیت خود را در خط تعیین کنید 1 به شماره ای که فرد مقابل شما داده است.

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

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

جزئیات فنی بازگشت

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

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

مثال ساده از بازگشت

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

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

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

فاکتوریل یک عدد عبارت است از ضرب همه اعداد از 1 تا آن عدد

به عنوان مثال، فاکتوریل از 5 است 120 – به این معنا که 5×4×3×2×1.

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

5×(5−1)!

این بدان معناست که اگر قدر آن را بدانیم (5−1)! ما به راحتی می توانیم فاکتوریل را فقط با ضرب بدست آوریم 5 توسط آن

در اینجا روش یافتن فاکتوریل ها آمده است 4، 3، 2، 1، و 0:

Factorial of 4 = 4×(4−1)!
Factorial of 3 = 3×(3−1)!
Factorial of 2 = 2×(2−1)!
Factorial of 1 = 1
Factorial of 0 = 1

با مشاهده این، مشخص می شود که برای یافتن فاکتوریل از 5، باید ضرب کنیم 5 توسط 4!.

مثال کلی تر

برای یافتن فاکتوریل از n، باید ضرب کنیم n با (n−1)!. این کاری است که باید به صورت بازگشتی انجام دهید.

حال باید شرط توقف برای بازگشت وجود داشته باشد. شرایط توقف زمانی است که ما هیچ عملیات دیگری انجام نمی دهیم. چه زمانی n است 1 یا n است 0، ما به سادگی می توانیم بازگشت را متوقف کنیم زیرا این مقادیر فاکتوریل های شناخته شده ای دارند. ما به سادگی می توانیم فاکتوریل را بگوییم 1 است 1 و همین امر برای 0.

بنابراین، با تجزیه آن، حداقل کاری که برای یافتن فاکتوریل n باید انجام دهیم، است n×(n−1)!. و ما می توانیم انجام عملیات را متوقف کنیم روی وقتی فاکتوریل را پیدا کنیم 1 یا 0.

بیایید ببینیم که در کد چگونه به نظر می رسد:

# calculate factorial of n
def fact(n):
   
   # no work required
    if n == 1 or n == 0:
        return 1
        
    # minimum amount of work
    return n * fact(n - 1)

n = 5

# calculate factorial
factorial = fact(n)
print(factorial)

خروجی:

120

بیایید ببینیم چگونه کار می کند:

در اولین فراخوانی تابع، فاکتوریل از 5 ارزیابی می شود. سپس در فراخوانی دوم، فاکتوریل از 4 ارزیابی می شود و غیره روی تا فاکتوریل از 2 ارزیابی می شود.

هنگام فراخوانی فاکتوریل از 2، ما داریم 2×fact(2−1)، که است 2×fact(1).

این به کیس پایه ما ضربه می زند. بنابراین، بازگشت متوقف می شود و 2×fact(1) برمی گرداند 2×1 به فراخوانی تابع قبلی، و نتیجه در پشته ظاهر می شود.

به طور مشابه، در اینجا روش ارزیابی سایر موارد است:

بنابراین تابع در نهایت مقدار را برمی گرداند 120 به فراخوانی تابع اولیه

چرا به یک کیس پایه نیاز داریم؟

در مثال بالا از شرط توقف برای کد استفاده کرده ایم. اما اگر یک شرط توقف اضافه نکنیم یا اگر تابعی که می نویسیم هرگز شرط توقف را نداشته باشد چه؟

آیا کد برای همیشه اجرا می شود؟

نه – حتی اگر خاتمه ندهید، کد شما برای همیشه اجرا نخواهد شد. بیایید با کمک یک مثال درک کنیم که چرا این مورد است.

def print_five():
    print(5)
    
    # call itself
    print_five()
    
# function call
print_five()

خروجی:

5
5
5
...

RecursionError: maximum recursion depth exceeded

اگر کد بالا را اجرا کنید، خواهید دید که این تابع برای همیشه اجرا نمی شود و با یک پیام به پایان می رسد RecursionError: maximum recursion depth exceeded.

هنگامی که یک تابع فراخوانی می شود، در یک پشته تماس ذخیره می شود. در اینجا روش عملکرد است print_five() هنگامی که برای اولین بار فراخوانی می شود، در پشته تماس ذخیره می شود.

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

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

وقتی پشته پر است، دیگر نمی‌تواند تماس‌های دیگری را بپذیرد و باعث خطای سرریز پشته می‌شود.

بنابراین، مورد پایه برای جلوگیری از چنین خطاهایی و اطمینان از پایان صحیح بازگشت ضروری است.

حال بیایید مثال دیگری را ببینیم تا بازگشت را بیشتر درک کنیم.

چگونه بررسی کنیم که آیا کلمه یک پالیندروم است یا خیر

قبل از اینکه وارد کد شویم، باید بدانید که پالیندروم چیست. پالیندروم کلمه ای است که به صورت یکسان به جلو و عقب خوانده می شود.

مثلا، racecar همان جلو و عقب را می خواند.

برای بررسی اینکه آیا یک کلمه پالیندروم است، باید بررسی کنیم که آیا حرف اول و آخر یکسان است یا خیر. اگر آنها هستند، سپس بررسی می کنیم که آیا حروف دوم و آخر یکسان هستند یا خیر.

در چارچوب racecar، حرف اول و آخر یکسان است، بنابراین بررسی می کنیم که آیا حرف دوم و آخر یکسان است یا خیر. آنها هستند، بنابراین اکنون بررسی می کنیم که آیا حروف سوم و سوم به آخر یکسان هستند یا خیر. اکنون فقط یک حرف برای بررسی باقی مانده است. یک حرف منفرد همیشه یک پالیندروم است زیرا هر دو طرف یکسان خوانده می شود.

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

حداقل مقدار کار

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

کار لازم نیست

وقتی یک حرف باقی مانده یا اصلاً حرفی باقی نمانده است، به سادگی می توانیم بگوییم که آن یک پالیندروم است.

حالا بیایید ببینیم کد چگونه به نظر می رسد:

# check palindrome
def check_palindrome(text):
   
    # stopping condition
    # if the size of text is 1 or 0 return true
    if len(text) == 0 or len(text) == 1:
        return True
    
    # least amount of work
    # check if first and last char are the same
    # if same remove first and last char from string
    if(text[0]==text[-1]):
        return(check_palindrome(text[1:-1]))
    
    return False

# check if string is palindrome
text = "racecar"
is_palindrome = check_palindrome(text)
print(is_palindrome)

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

زمان استفاده از Recursion

بازگشت می تواند زیبا و ساده به نظر برسد. اما اغلب به مراحل زیادی نیاز دارد تا حتی مشکلات ساده را به دلیل سربار CPU از اضافه کردن مکرر متدها به پشته حل کند. بنابراین قبل از استفاده از آن، مطمئن شوید که به دقت بررسی کرده اید که آیا راه حل مناسبی برای مشکل شما است یا خیر.

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

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

بسته بندی

این فقط مقدمه ای برای بازگشت است. موارد زیادی وجود دارد که از Recursion استفاده می شود، و ممکن است در مورد روش عملکرد همه چیز گیج شوید. نمونه های پیشرفته تری را پوشش خواهم داد روی بازگشت در مقاله بعدی

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

• ویدیوی freeCodeCamp روی بازگشت: من باید به freeCodeCamp برای ویدیوی عالی آنها فریاد بزنم روی بازگشت، که الهام بخش بسیاری از این مقاله است.
• Recursion by Programiz Pro: یکی دیگر از منابع خوب دوره Recursion توسط Programiz است. این یک دوره آموزشی برتر است، بنابراین رایگان نیست، اما با تفکر طراحی شده است. به علاوه، می‌توانید به طور مستقیم تمرین کنید روی پلت فرم آنها، که ارزش آن را دارد.

مهم نیست از کجا یاد می گیرید، زمان زیادی را صرف جستجوی منبع کامل نکنید. فقط مفاهیم را درک کنید و شروع به تمرین کنید – این تنها راهی است که واقعاً یاد خواهید گرفت.