درک اصول بازگشت – انجمن DEV

اگر برای شما:

• بازگشت موضوعی مبهم است یا می خواهید کمی بیشتر در مورد آن بفهمید.
• دم تماس و TCO رسانه های بیگانه هستند و;
• ترامپولین اسم داروست

پس این مقاله برای تو است.

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

پس در این سفر با من بیا بی پایان.

✋
برای ادامه، به بالای پست برگردید

دستور جلسه

بازگشت چیست

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

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

با این کار، تابع “خود را فراخوانی” می کند تا مقداری محاسبات را انجام دهد و اجرای خود را ادامه دهد.

فیبو برای افراد صمیمی

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.........

با این، تابع فیب نتایجی مانند:

fib(0) = 0
fib(1) = 1
fib(2) = 1
...
fib(7) = 13
fib(10) = 55

بنابراین ما یک پیاده سازی بازگشتی احتمالی در Ruby داریم:

def fib(position)
  return position if position < 2

  fib(position - 1) + fib(position - 2)
end

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

                 fib(10)
             /                \
     fib(9)                 fib(8)
        /          \          /   \
fib(8)     fib(7)     fib(7)    fib(6)
  /      \       /       \       /   \
fib(7) fib(6) fib(6) fib(5) fib(6) fib(5)
   /    \     /     \     /     \     /    \
fib(6) fib(5) fib(5) fib(4) fib(5) fib(4) fib(5) fib(4)
  /   \   /   \   /   \   /   \   /   \   /   \   /   \
...

در نتیجه، هرچه ورودی تابع بیشتر باشد، زمان اجرای این کد به صورت تصاعدی رشد می کند که در نمادگذاری Big-O او خواهد بود O(2^n).

آیا می توان این پیچیدگی را کاهش داد؟

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

این تکنیک وجود دارد و نامیده می شود تماس دم، یا بازگشت دم.

تماس دم

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

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

در نماد Big-O این می شود O(n)، یعنی پیچیدگی به صورت خطی به دنبال رشد ورودی افزایش می یابد.

مثال یاقوت:

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  fib(position - 1, _next, _current + _next)
end

بنابراین، تعداد تماس های بازگشتی به شدت به چیزی شبیه به این کاهش می یابد:

fib(10, 0, 1)
fib(9, 1, 1)
fib(8, 1, 2)
fib(7, 2, 3)
fib(6, 3, 5)
fib(5, 5, 8)
fib(4, 8, 13)
fib(3, 13, 21)
fib(2, 21, 34)
fib(1, 34, 55)
fib(0, 55, 89)

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

بنابراین هنگام اجرای برنامه fib com TC، زمان اجرا به طور تصاعدی کمتر از اجرای بدون TC، گرفتن است ده ها هزار بار سریعتر.

✋
واضح است که برنامه‌ای که زمان تصاعدی می‌گیرد از نظر عملکرد بد است، نه؟

# Sem TC
fib(30) # 0.75 segundos

# Com TC
fib(30) # 0.000075 segundos

بازگشت به مثال از fib(10000)، هنگام اجرا با TC، می بینیم که اجرا بسیار سریعتر است، اما:

recursion/fib.rb:10:in `fib_tc': stack level too deep (SystemStackError)
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'

اوه اوه، یک سرریز پشته!

برای اینکه بفهمیم چه خبر است، بیایید ابتدا بفهمیم که جهنم چیست پشته ه سرریز پشته.

پشته و سرریز پشته

هنگامی که یک برنامه اجرا می شود، یک ساختار داده به شکل a در حافظه تخصیص داده می شود باتری، زنگ زدن پشته، که برای ذخیره داده های مورد استفاده در یک تابع در حال اجرا استفاده می شود.

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

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

به هر فراخوانی تابع a اختصاص داده می شود قاب پشته. از آنجایی که یک تماس بازگشتی هرگز تمام نمی شود، زمان اجرا نمی داند که باید داده ها را “پاپ” کند و فریم را پایان دهد، بنابراین با هر تماس، یک قاب پشته جدید ایجاد می شود و عناصر بیشتری اضافه می شود پشته کردن

حدس بزنید چه اتفاقی می‌افتد وقتی داده‌های زیادی را به پشته اضافه می‌کنیم از حد خود فراتر رود در حافظه کامپیوتر؟

بله اتفاق معروف می افتد سرریز پشته 💥🪲، و این خطا را در Ruby هنگام اجرای فیب 10000 با tail call توضیح می دهد.

✋
پس آیا به این معنی است که محاسبه فیب 10000 یک مشکل غیرممکن برای حل با بازگشت است؟

آرام باشید، برخی از زبان ها از تکنیک بهینه سازی استفاده می کنند که شامل “جایگزینی” تماس TC توسط یک حلقه اولیه، یعنی فقط یک قاب پشته تک، بنابراین اطمینان حاصل می شود که هر فراخوانی بازگشتی به عنوان یک تکرار در حلقه تلقی می شود.

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

این تکنیک را ما می نامیم بهینه سازی تماس دم، یا TCO.

بهینه سازی تماس دم

به دلیل ماهیت امری آن و مانند بسیاری از زبان های همه منظوره دیگر، روبی به صورت بومی از TCO پشتیبانی نمی کند.

عموماً این کارکرد بیشتر در زبان‌هایی یافت می‌شود که تمایل زیادی به پارادایم کارکردی دارند و نه به پارادایم امری.

اما در روبی این امکان وجود دارد فعال کردن یا حالت TCO با یک پیکربندی ساده در دستورالعمل Ruby Runtime (YARV)، و بنابراین ما می توانیم 10000 فیب را بدون دردسر اجرا کنیم.

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  fib(position - 1, _next, _current + _next)
end

# TC com TCO
fib(10000) # 0.02 segundos

عالی! با فعال بودن TCO، یک تماس 10000 fib tail در آن اجرا می شود 0.02 ثانیه!

✋
بسیار خوب، اما وقتی نمی توانم TCO را فعال کنم یا به زبانی برنامه نویسی می کنم که TCO را پشتیبانی نمی کند، چطور؟

ترامپولین برای نجات.

ترامپولین

فهمیدن ترامپولین، بیایید در مورد مشکل و راه حل ممکن فکر کنیم.

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

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  ###################################
  #### Devemos evitar isso!!!!!! ####
  ###################################
  fib(position - 1, _next, _current + _next)
end

فرض دو، به جای اینکه یک تماس بازگشتی را مستقیماً برگردانیم، چه می شود اگر آن را برگردانیم در یک ساختار تابع ناشناس محصور شده است که زمینه را نگه می دارد در زمینه دیگری اجرا شود؟

بله، مانند یک بسته یا لامبدا برای مراقب ترین ها

در روبی می توانیم از مفهوم استفاده کنیم لامبدا.

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  lambda do
    fib(position - 1, _next, _current + _next)
  end
end

اگر تماس بگیریم result = fib(0)به دلیل اولین خط اتصال کوتاه (position < 1، بازگشت روش است 0.

اما اگر تماس بگیریم result = fib(10)، بازگشت یک تماس بازگشتی نخواهد بود، بلکه بازگشت یک تابع ناشناس خواهد بود (لامبدا).

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

از آنجایی که لامبداها زمینه را حفظ می کنند، اگر تماس بگیریم result.call، لامبدا با زمینه قبلی اجرا می شود که می تواند عدد نهایی (اگر وارد اتصال کوتاه شود) یا لامبدا دیگری را با متن جدید برگرداند.

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

بله، یکی حلقه

result = fib(10000)

while result.is_a?(Proc)
  result = result.call
end

puts result

خروجی (عدد واقعاً بزرگ):

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

🔑 نقطه کلیدی
و با این، دوستان، ما تکنیک را داریم ترامپولین: یکی حلقه اولیه غیر بازگشتی که مدام تابع دیگری را فراخوانی می کند به صورت بازگشتی نوشته شده است اما این یک لامبدا را با زمینه برمی گرداند، تا رسیدن به مقدار نهایی.

این کد، sem TCO، برای فیب 10000، 0.04 ثانیه طول می کشد، نتیجه ای بسیار نزدیک به TCO و بدون ایجاد سرریز پشته.

شگفت انگیز است، اینطور نیست؟ اکنون هیچ بهانه ای برای ننوشتن یک تابع به صورت بازگشتی در زبان هایی که از TCO پشتیبانی نمی کنند وجود ندارد.

نتیجه

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

امیدوارم موضوع بازگشت را به صورت تعلیمی روشن کرده باشم، اگر ممکن است اصلاحات یا اطلاعات مربوطه را در نظرات بگذارید.

منابع

https://twitter.com/leandronsp/status/1672043065001869312
https://twitter.com/JeffQuesado/status/1671954585987022882
https://en.wikipedia.org/wiki/Fibonacci_sequence
https://en.wikipedia.org/wiki/Recursion
https://www.geeksforgeeks.org/stack-data-structure/
https://en.wikipedia.org/wiki/Tail_call
https://en.wikipedia.org/wiki/Trampoline_(computing)
https://nithinbekal.com/posts/ruby-tco/
https://www.bigocheatsheet.com/
https://ruby-doc.org/core-3.1.0/RubyVM/InstructionSequence.html#method-c-compile_option