درک مدرن از بازگشت: تعریف عملکرد و دسترسی به آن از خارج و از این عملکرد. اعتقاد بر این است که بازگشت توسط ریاضیدانان متولد شد: محاسبه فاکتوریل، سری نامتناهی، فراکتال ها، کسرهای ادامه دار… با این حال، بازگشت را می توان در همه جا یافت. قوانین عینی طبیعی، بازگشت را به عنوان الگوریتم اصلی و شکل بیان (وجود) خود نه چندان از اشیاء جهان مادی، که به طور کلی الگوریتم اصلی حرکت در نظر می گیرند.
افراد با تخصص های مختلف در زمینه های مختلف علم و فناوری از الگوریتم بازگشتی f (x) استفاده می کنند که در آن "x ~/=f (x)". تابعی که خود را فراخوانی می‌کند راه‌حل قوی است، اما شکل‌دهی و درک این راه‌حل، در بیشتر موارد، کار بسیار دشواری است.
در دوران باستان برای افزایش فضای کاخ از بازگشت استفاده می شد. از طریق سیستمی از آینه ها که به سمت یکدیگر هدایت می شوند، می توانید جلوه های فضایی سه بعدی خیره کننده ای ایجاد کنید. اما آیا درک چگونگی آن بسیار آسان استاین آینه ها را تنظیم کنید؟ تعیین اینکه نقطه ای در فضا کجاست که از طریق چندین آینه منعکس شده است، حتی دشوارتر است.
بازگشت، الگوریتم های بازگشتی: معنا و نحو
مسئله ای که با تکرار یک دنباله از عملیات فرموله می شود، می تواند به صورت بازگشتی حل شود. یک الگوریتم ساده (محاسبه یک معادله درجه دوم، یک اسکریپت برای پر کردن یک صفحه وب با اطلاعات، خواندن یک فایل، ارسال پیام…) نیازی به بازگشت ندارد.
تفاوتهای اصلی الگوریتمی که امکان حل بازگشتی را فراهم می کند:
- الگوریتمی وجود دارد که باید چندین بار اجرا شود؛
- الگوریتم به داده هایی نیاز دارد که هر بار تغییر کند؛
- الگوریتم لازم نیست هر بار تغییر کند؛
- یک شرط نهایی وجود دارد: الگوریتم بازگشتی است - نه بی نهایت.
به طور کلی نمی توان ادعا کرد که اجرای یکباره شرط لازم برای عدم وجود دلیل برای بازگشت است. همچنین نمی‌توانید به شرط نهایی اجباری نیاز داشته باشید: بازگشت‌های بی‌نهایت دامنه خاص خود را دارند.
الگوریتم بازگشتی است: وقتی دنباله ای از عملیات به طور مکرر انجام می شود، روی داده هایی که هر بار تغییر می کنند و هر بار نتیجه جدیدی می دهند.
فرمول بازگشت
درک ریاضی بازگشت و آنالوگ آن در برنامه نویسی متفاوت است. ریاضیات، اگرچه نشانه هایی از برنامه نویسی وجود دارد، اما برنامه نویسی ریاضیات بسیار بالاتری است.
یک الگوریتم خوش نوشته مانند آینه ای از عقل نویسنده اش است. عمومیفرمول بازگشتی در برنامه نویسی "f(x)" است، که در آن "x ~/=f(x)" حداقل دو تفسیر دارد. در اینجا "~" شباهت یا عدم وجود نتیجه است و "=" وجود نتیجه تابع است.
گزینه اول: دینامیک داده.
- تابع "f(x)" یک الگوریتم بازگشتی و تغییرناپذیر دارد؛
- "x" و نتیجه "f(x)" هر بار مقادیر جدیدی دارند، نتیجه "f(x)" پارامتر "x" جدید این تابع است.
گزینه دوم: پویایی کد.
- تابع "f(x)" چندین الگوریتم دارد که داده ها را پالایش (تحلیل) می کند؛
- تحلیل داده - یک قسمت از کد و پیاده سازی الگوریتم های بازگشتی که عمل مورد نظر را انجام می دهند - قسمت دوم کد؛
- نتیجه تابع "f(x)" نیست.
بدون نتیجه طبیعی است. برنامه نویسی ریاضی نیست، در اینجا لازم نیست نتیجه به صراحت وجود داشته باشد. یک تابع بازگشتی می تواند به سادگی سایت ها را تجزیه کند و پایگاه داده را پر کند یا اشیاء را مطابق ورودی ورودی نمونه سازی کند.
داده و بازگشت
برنامه‌نویسی الگوریتم‌های بازگشتی مربوط به محاسبه فاکتوریل نیست، که در آن تابع هر بار مقدار معینی را دریافت می‌کند که یک مقدار بیشتر یا کمتر از یک است - گزینه پیاده‌سازی به ترجیح توسعه‌دهنده بستگی دارد.
مهم نیست که "8!" چگونه فاکتوریل باشد،الگوریتمی که دقیقاً از این فرمول پیروی می کند.
پردازش اطلاعات "ریاضیات" با ترتیبی کاملاً متفاوت است. توابع و الگوریتم های بازگشتی در اینجا بر روی حروف، کلمات، عبارات، جملات و پاراگراف ها عمل می کنند. هر سطح بعدی از سطح قبلی استفاده می کند.
جریان داده های ورودی در طیف وسیعی از شرایط تجزیه و تحلیل می شود، اما فرآیند تجزیه و تحلیل عموماً بازگشتی است. نوشتن الگوریتم های منحصر به فرد برای همه انواع جریان ورودی منطقی نیست. باید یک عملکرد وجود داشته باشد. در اینجا، الگوریتم های بازگشتی نمونه هایی از نحوه تشکیل یک جریان خروجی مناسب برای ورودی هستند. این خروجی الگوریتم بازگشتی نیست، اما راه حل مطلوب و ضروری است.
انتزاع، بازگشت و OOP
برنامه‌نویسی شی‌گرا (OOP) و بازگشت، اساساً موجودیت‌های متفاوتی هستند، اما کاملاً مکمل یکدیگر هستند. انتزاع ربطی به بازگشت ندارد، اما از طریق لنز OOP امکان پیاده سازی بازگشت متنی را ایجاد می کند.
برای مثال، اطلاعات در حال تجزیه هستند و حروف، کلمات، عبارات، جملات و پاراگراف ها به طور جداگانه برجسته می شوند. بدیهی است که توسعه دهنده ایجاد نمونه هایی از اشیاء از این پنج نوع را فراهم می کند و راه حلی از الگوریتم های بازگشتی را در هر سطح ارائه می دهد.
در این میان، اگر در سطح حروف «جستجوی معنا فایده ای ندارد»، معناشناسی در سطح کلمات ظاهر می شود. شما می توانید کلمات را به فعل، اسم، قید، حرف اضافه تقسیم کنید… می توانید جلوتر بروید و موارد را تعریف کنید.
در سطح عبارت، معناشناسی با علائم نگارشی و منطق تکمیل می شود.ترکیب کلمات در سطح جملات سطح معنایی کامل تری پیدا می شود و یک پاراگراف را می توان به عنوان یک فکر کامل در نظر گرفت.
توسعه شی گرا، وراثت ویژگی ها و روش ها را از پیش تعیین می کند و پیشنهاد می کند که سلسله مراتب اشیاء را با ایجاد یک اجداد کاملاً انتزاعی شروع کنید. در عین حال، بدون شک، تحلیل هر یک از نوادگان بازگشتی خواهد بود و در بسیاری از موقعیت ها (حروف، کلمات، عبارات و جملات) در سطح فنی تفاوت زیادی نخواهد داشت. پاراگراف‌ها، مانند افکار کامل، ممکن است از این فهرست برجسته شوند، اما اصل نیستند.
مهم است که بخش عظیم الگوریتم را بتوان در سطح اجدادی انتزاعی فرموله کرد و آن را در سطح هر نواد با داده ها و روش هایی که از سطح انتزاعی فراخوانی می شوند، اصلاح کرد. در این زمینه، انتزاع افق های جدیدی را برای بازگشت باز می کند.
ویژگی های تاریخی OOP
OOP دو بار وارد دنیای نرم افزار شده است، اگرچه برخی از کارشناسان ممکن است ظهور محاسبات ابری و ایده های مدرن در مورد اشیاء و کلاس ها را به عنوان دور جدیدی در توسعه فناوری های IT مشخص کنند.
اصطلاحات "شیء" و "هدف" در زمینه مدرن OOP معمولاً به دهه های 50 و 60 قرن گذشته نسبت داده می شود، اما آنها با سال 1965 و ظهور Simula، Lisp، Algol، Smalltalk مرتبط هستند..
در آن روزها، برنامه نویسی به طور خاص توسعه نیافته بود و نمی توانست به اندازه کافی به مفاهیم انقلابی پاسخ دهد. مبارزه ایده‌ها و سبک‌های برنامه‌نویسی (C / C ++ و پاسکال - عمدتاً) هنوز بسیار دور بود و پایگاه‌های داده هنوز به صورت مفهومی شکل می‌گرفتند.
در اواخر دهه 80 و اوایل دهه 90، اشیاء در پاسکال ظاهر شدند و همه کلاس های C / C ++ را به خاطر می آوردند - این نشان دهنده دور جدیدی از علاقه به OOP بود و در آن زمان بود که ابزارها، در درجه اول زبان های برنامه نویسی، دیگر از کار افتادند. فقط از ایده های شی گرا پشتیبانی می کند، اما بر این اساس تکامل می یابد.
البته، اگر الگوریتم های بازگشتی قبلی فقط توابعی بودند که در کد کلی برنامه استفاده می شد، اکنون بازگشت می تواند بخشی از ویژگی های یک شی (کلاس) شود که فرصت های جالبی را در زمینه وراثت ارائه می کند.
ویژگی OOP مدرن
توسعه OOP در ابتدا اشیاء (کلاس ها) را به عنوان مجموعه ای از داده ها و ویژگی ها (روش ها) اعلام کرد. در واقع در مورد داده هایی بود که نحو و معنی دارند. اما پس از آن امکان ارائه OOP به عنوان ابزاری برای مدیریت اشیاء واقعی وجود نداشت.
OOP به ابزاری برای مدیریت اشیاء "ماهیت کامپیوتری" تبدیل شده است. یک اسکریپت، یک دکمه، یک آیتم منو، یک نوار منو، یک برچسب در پنجره مرورگر یک شی است. اما نه یک ماشین، یک محصول غذایی، یک کلمه یا یک جمله. اشیاء واقعی خارج از برنامه نویسی شی گرا باقی مانده اند و ابزارهای رایانه ای تجسم جدیدی به خود گرفته اند.
به دلیل تفاوت در زبان های برنامه نویسی محبوب، گویش های OOP زیادی پدید آمده است. از نظر معنایی، آنها عملاً معادل هستند و تمرکز آنها بر حوزه ابزاری، و نه بر حوزه کاربردی، این امکان را فراهم می کند که توصیف اشیاء واقعی فراتر رود.الگوریتم‌ها و اطمینان از وجود بین پلتفرمی و بین‌زبانی آنها.
پشته ها و مکانیسم های فراخوانی عملکرد
مکانیسم‌های فراخوانی توابع (رویه‌ها، الگوریتم‌ها) نیازمند ارسال داده‌ها (پارامترها)، برگرداندن نتیجه و به خاطر سپردن آدرس اپراتور است که باید کنترل را پس از تکمیل تابع (رویه) دریافت کند.
معمولاً از پشته برای این منظور استفاده می شود، اگرچه زبان های برنامه نویسی یا خود توسعه دهنده می توانند گزینه های مختلفی را برای انتقال کنترل ارائه دهند. برنامه نویسی مدرن اذعان می کند که نام یک تابع نه تنها می تواند یک پارامتر باشد، بلکه می تواند در طول اجرای الگوریتم تشکیل شود. در حین اجرای الگوریتم دیگری نیز می توان یک الگوریتم ایجاد کرد.
مفهوم الگوریتم های بازگشتی، زمانی که می توان نام و بدن آنها را در زمان شکل گیری کار (انتخاب الگوریتم مورد نظر) تعیین کرد، بازگشت پذیری را نه تنها به نحوه انجام کاری، بلکه همچنین به اینکه دقیقاً چه کسی باید انجام دهد گسترش می دهد. انجام دهید. انتخاب یک الگوریتم با نام "معنی" آن امیدوار کننده است، اما مشکلاتی را ایجاد می کند.
بازگشتی در مجموعه ای از توابع
شما نمی توانید بگویید که یک الگوریتم زمانی که خود را فراخوانی می کند بازگشتی است و تمام. برنامه نویسی یک جزم نیست، و مفهوم بازگشتی بودن یک الزام انحصاری برای فراخوانی خود از بدنه الگوریتم شما نیست.
کاربردهای عملی همیشه راه حل تمیزی ارائه نمی دهند. اغلب، داده های اولیه باید آماده شوند و نتیجه فراخوانی بازگشتی باید در چارچوب کل مسئله (کل الگوریتم) دربه طور کلی.
در واقع، نه تنها قبل از فراخوانی یک تابع بازگشتی، بلکه پس از تکمیل آن، برنامه دیگری را می توان یا باید فراخوانی کرد. اگر مشکل خاصی با فراخوانی وجود نداشته باشد: تابع بازگشتی A() تابع B() را فراخوانی می کند که کاری را انجام می دهد و A() را فراخوانی می کند، بلافاصله با بازگشت کنترل مشکل ایجاد می شود. پس از تکمیل فراخوانی بازگشتی، تابع A() باید کنترل را دریافت کند تا بتواند B() را دوباره فراخوانی کند، که دوباره آن را فراخوانی می کند. بازگرداندن کنترل همانطور که باید در پشته به B() راه حل اشتباهی است.
برنامه نویس در انتخاب پارامترها محدود نیست و می تواند آنها را با نام توابع تکمیل کند. به عبارت دیگر، راه حل ایده آل این است که نام B() را به A() منتقل کنید و اجازه دهید A() خود B() را صدا کند. در این صورت هیچ مشکلی برای کنترل برگشتی وجود نخواهد داشت و اجرای الگوریتم بازگشتی شفاف تر خواهد بود.
درک و سطح بازگشت
مشکل توسعه الگوریتم های بازگشتی این است که باید پویایی فرآیند را درک کنید. هنگام استفاده از بازگشت در روش های شی، به ویژه در سطح یک اجداد انتزاعی، مشکل درک الگوریتم خود در زمینه زمان اجرای آن وجود دارد.
در حال حاضر، هیچ محدودیتی در سطح تودرتو توابع و ظرفیت پشته در مکانیسم های فراخوانی وجود ندارد، اما یک مشکل درک وجود دارد: در چه مقطعی از زمان، کدام سطح داده یا کدام مکان در الگوریتم عمومی به نام بازگشتی عملکرد و تعداد تماس هایی که خودش دارد.
ابزارهای اشکال زدایی موجود اغلب ناتوان هستندراه حل درست را به برنامه نویس بگویید.
حلقه و بازگشت
در نظر گرفته می شود که اجرای چرخه ای معادل بازگشت است. در واقع، در برخی موارد، الگوریتم بازگشتی را می توان در نحو ساختارهای شرطی و چرخه ای پیاده سازی کرد.
با این حال، اگر درک روشنی وجود داشته باشد که یک تابع خاص باید از طریق یک الگوریتم بازگشتی پیاده‌سازی شود، هرگونه استفاده خارجی از یک حلقه یا عبارات شرطی باید کنار گذاشته شود.
معنی در اینجا این است که یک راه حل بازگشتی به شکل تابعی که از خودش استفاده می کند، یک الگوریتم کامل و از نظر عملکردی کامل خواهد بود. این الگوریتم به برنامه نویس نیاز دارد که آن را با تلاش و درک دینامیک الگوریتم ایجاد کند، اما راه حل نهایی است که نیازی به کنترل خارجی ندارد.
هر ترکیبی از عملگرهای شرطی و چرخه ای خارجی به ما اجازه نمی دهد الگوریتم بازگشتی را به عنوان یک تابع کامل نشان دهیم.
توافق بازگشتی و OOP
تقریباً در همه انواع توسعه یک الگوریتم بازگشتی، طرحی برای توسعه دو الگوریتم ایجاد می شود. الگوریتم اول لیستی از اشیاء (نمونه) آینده را تولید می کند و الگوریتم دوم در واقع یک تابع بازگشتی است.
بهترین راه حل این است که بازگشت را به عنوان یک ویژگی (روش) واحد که در واقع حاوی الگوریتم بازگشتی است، مرتب کنیم و تمام کارهای مقدماتی را در سازنده شیء قرار دهیم.
یک الگوریتم بازگشتی تنها زمانی راه حل مناسبی خواهد بود که کار کندفقط توسط خودش، بدون کنترل و مدیریت خارجی. یک الگوریتم خارجی فقط می تواند یک سیگنال برای کار بدهد. نتیجه این کار باید راه حل مورد انتظار، بدون پشتیبانی خارجی باشد.
بازگشت همیشه باید یک راه حل مستقل و کامل باشد.
درک بصری و کامل بودن عملکرد
وقتی برنامه نویسی شی گرا به استاندارد واقعی تبدیل شد، آشکار شد که برای کدنویسی مؤثر، باید تفکر خود را تغییر دهید. برنامه نویس باید در طول اجرای الگوریتم از نحو و معنای زبان به پویایی معنایی حرکت کند.
ویژگی بازگشت: می توان آن را برای همه چیز اعمال کرد:
- خراش دادن وب؛
- عملیات جستجو;
- تجزیه اطلاعات متن؛
- خواندن یا ایجاد اسناد MS Word؛
- نمونه‌برداری یا تجزیه و تحلیل برچسب‌ها…
ویژگی OOP: توصیف یک الگوریتم بازگشتی در سطح یک اجداد انتزاعی را امکان پذیر می کند، اما برای ارجاع آن به نوادگان منحصر به فرد، که هر کدام دارای پالت داده ها و ویژگی های خاص خود هستند، امکان پذیر است.
بازگشت ایده آل است زیرا به کامل بودن عملکرد الگوریتم آن نیاز دارد. OOP عملکرد یک الگوریتم بازگشتی را با دسترسی به همه کودکان منحصر به فرد بهبود می بخشد.
