الگوریتم های بازگشتی و بازگشتی بازگشت چیست

از lat recursio (بازگشت). به طور کلی، این نام برای فرآیند تکرار عناصر به روش "خود مشابه" است.

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

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

مثال بازگشتی

خسته کننده ترین مثال بازگشت در برنامه ریزی ریاضی محاسبه فاکتوریل است. به سنت های باشکوه خیانت نکنیم. برای کسانی که هنوز آن را انجام نداده اند: N! (ضریب N) حاصلضرب تمام اعداد طبیعی از یک تا N است (فاکتوریل صفر برابر با 1 است).
شما می توانید احمقانه اعداد از 1 تا N را در یک حلقه ضرب کنید. یا می توانید یک تابع فاکتوریل (n) بسازید که شامل یک شرط باشد و خود را فراخوانی کند. اگر n برابر با یک باشد، تابع مقدار 1 را برمی گرداند، در غیر این صورت مقدار n ضرب در فاکتوریل (n-1) را برمی گرداند.
طرح PHP

تابع فاکتوریل ($n) (اگر ($ n == 1) (بازگشت 1؛) other (intval بازگشت ($ n * فاکتوریل ($ n - 1))))

کاربردهای عملی بازگشت

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

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

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

بازگشت موتور جستجو

بله دقیقا. موتورهای جست و جو هم جایی برای بازگشت ندارند. از آنجایی که رسم اندازه گیری اعتبار یک سایت (سند) با تعداد پیوندها برقرار شد، موتورهای جستجو در دام بازگشتی افتادند و اجازه دادند برای همیشه در آن سرگردان شوند (این آرزوی صمیمانه نویسنده است). پیوند "وزن" یک سایت از تکه های کوچک "وزن" از همه مواردی که به آن لینک می دهند تشکیل شده است. برای محاسبه این وزن برای A، که توسط B، C و D به آنها اشاره می شود، باید وزن آنها را محاسبه کنید، که به نوبه خود توسط انواع دیگری منتقل می شود، که وزن آنها نیز باید محاسبه شود ... و غیره در کل کل وب در موتور جستجو شمارش می شود. یک مشکل کاملا بازگشتی و شما می گویید - یک نظریه محکم. بیشترین چیزی که هیچ کدام تمرین واقعی نیست.

پیج رنک بازگشتی از گوگل

سازندگان گوگل مدت ها پیش الگوریتم اصلی خود را برای محاسبه PageRank منتشر کردند. و مهم نیست که از آن زمان تاکنون چقدر تغییر کرده است، هر چقدر هم که با پیشرفت ها تکمیل شده باشد، اساس آن ثابت می ماند. شما نمی توانید بفهمید که صفحه B چقدر به صفحه A پیوند می دهد تا زمانی که ما محاسبه نکنیم که صفحه B چقدر از سایر صفحاتی که به آن لینک داده اند، دریافت کرده است، و تا زمانی که رتبه صفحه آن ها را محاسبه نکنیم نمی توان آن را دانست. صفحات ... ادامه؟ احتمالا دیگر لازم نیست. دوباره اوست - اعلیحضرت بازگشت .

سلام حبرهبر!

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

مختصری در مورد بازگشت

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

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

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

• کارهای بازگشتی و بازگشتی. زمینه های کاربرد بازگشت

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

وظایف

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

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

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

از شبکه

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

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

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

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

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

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

می توانید با جزئیات بیشتری با این موضوع آشنا شوید.

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

بنابراین تابع بازگشتی شامل

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

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

راه حل کلاس عمومی (بازگشت عمومی static int (int n) (// شرط خروج // حالت پایه // چه زمانی تکرار بازگشت متوقف شود؟ اگر (n == 1) (بازگشت 1;) // مرحله بازگشت / شرایط بازگشتی بازگشت بازگشت ( n - 1) * n;) اصلی خالی ثابت عمومی (Args رشته) (System.out.println (بازگشت (5))؛ // فراخوانی تابع بازگشتی))

در اینجا شرط Basic شرطی است که n = 1 باشد. از آنجایی که می دانیم 1! = 1 و برای محاسبه 1! ما به چیزی نیاز نداریم برای محاسبه 2! ما می توانیم از 1 استفاده کنیم، یعنی. 2 = 1! * 2. برای محاسبه 3! ما نیاز داریم 2 * 3 ... برای محاسبه n! ما به (n-1) نیاز داریم!* n. این مرحله بازگشت است. به عبارت دیگر برای بدست آوردن مقدار فاکتوریل از عدد n کافی است مقدار فاکتوریل عدد قبلی را در n ضرب کنیم.

برچسب ها:

• بازگشت
• وظایف
• جاوا

افزودن برچسب

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

1. ذات بازگشت

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

نمونه ای از یک روش بازگشتی:

Procedure Rec (a: integer); شروع اگر a>

در نظر بگیرید که چه اتفاقی می افتد اگر یک تماس در برنامه اصلی، به عنوان مثال، از فرم Rec (3) قرار گیرد. در زیر یک بلوک دیاگرام وجود دارد که توالی اجرای دستورات را نشان می دهد.

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

رویه Rec با پارامتر a = 3 فراخوانی می شود. شامل فراخوانی رویه Rec با پارامتر a = 2 است. فراخوانی قبلی هنوز به پایان نرسیده است، بنابراین می توانید تصور کنید که رویه دیگری در حال ایجاد است و روال اول تمام نمی شود. کارش قبل از اینکه کارش تمام شود فرآیند فراخوانی زمانی پایان می یابد که پارامتر a = 0 باشد. در این لحظه، 4 نمونه از رویه به طور همزمان اجرا می شوند. تعداد اقدامات انجام شده به طور همزمان نامیده می شود عمق بازگشت.

چهارمین رویه فراخوانی شده (Rec (0)) عدد 0 را چاپ می کند و کار خود را به پایان می رساند. پس از آن، کنترل به رویه ای که آن را فراخوانی می کند (Rec (1)) برمی گردد و عدد 1 چاپ می شود و به همین ترتیب تا زمانی که تمام مراحل تکمیل شود. تماس اولیه چهار شماره را چاپ می کند: 0، 1، 2، 3.

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

برنج. 2. اجرای رویه Rec با پارامتر 3 شامل اجرای رویه Rec با پارامتر 2 و چاپ عدد 3 است. به نوبه خود اجرای رویه Rec با پارامتر 2 شامل اجرای رویه Rec با پارامتر 1 و چاپ شماره 2 می باشد. به زودی.

به عنوان یک تمرین مستقل، آنچه را که با Rec (4) تماس می‌گیرید، در نظر بگیرید. همچنین، به این فکر کنید که وقتی رویه Rec2 (4) را که در زیر توضیح داده شده است فراخوانی می‌کنید، جایی که عبارات با هم عوض می‌شوند، چه اتفاقی می‌افتد.

رویه Rec2 (a: عدد صحیح). شروع نوشتن (a)؛ اگر a> 0، سپس Rec2 (a-1)؛ پایان؛

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

یک طرح کمی پیچیده تر ممکن است: تابع A تابع B را صدا می کند و آن نیز به نوبه خود A را فراخوانی می کند. بازگشت پیچیده... در این مورد، معلوم می شود که اولین رویه توصیف شده باید با روشی که هنوز توضیح داده نشده است تماس بگیرد. برای اینکه این امکان پذیر باشد، باید از آن استفاده کنید.

رویه A (n: عدد صحیح). (توضیحات رو به جلو (عنوان) رویه اول) رویه B (n: عدد صحیح); (توضیحات ارسال روش دوم) رویه A (n: عدد صحیح). (توضیح کامل رویه A) شروع به نوشتن (n) کنید. B (n-1)؛ پایان؛ روش B (n: عدد صحیح)؛ (توضیح کامل رویه B) شروع به نوشتن (n) کنید. اگر n

شرح فوروارد رویه B امکان فراخوانی آن را از رویه A فراهم می کند. شرح رو به جلو رویه A در این مثال مورد نیاز نیست و به دلایل زیبایی شناسی اضافه شده است.

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

برنج. 3. Ouroboros یک مار است که دم خود را می بلعد. برگرفته از رساله کیمیاگری «سینوسیوس» اثر تئودور پلکانوس (1478).

برنج. 4. بازگشت پیچیده.

3. شبیه سازی یک حلقه با استفاده از بازگشت

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

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

مثال 1.

Procedure LoopImitation (i, n: integer); (پارامتر اول شمارنده گام است، پارامتر دوم تعداد کل مراحل است) شروع به نوشتن کنید ("Hello N"، i). // در اینجا هر دستورالعملی وجود دارد که اگر i تکرار شود

نتیجه تماسی مانند LoopImitation (1، 10) دستورالعمل ها را ده بار با تغییر شمارنده از 1 به 10 اجرا می کند. در این حالت، چاپ می شود:

سلام N 1
سلام N 2
…
سلام N 10

به طور کلی، دیدن اینکه پارامترهای رویه محدودیت های تغییر مقادیر شمارنده هستند دشوار نیست.

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

مثال 2.

Procedure LoopImitation2 (i, n: integer); شروع کنم اگر من

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

سلام N 10
…
سلام N 1

اگر زنجیره‌ای از رویه‌های بازگشتی را تصور کنیم، در مثال 1 آن را از رویه‌هایی که قبلاً نامیده می‌شوند به رویه‌های بعدی عبور می‌کنیم. در مثال 2، برعکس، از دیر به زود.

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

Procedure LoopImitation3 (i, n: integer); شروع نوشتن ("Hello N"، i)؛ (بلاک اول دستورالعمل ممکن است در اینجا قرار گیرد) اگر i

در اینجا، ابتدا دستورالعمل های بلوک اول به صورت متوالی اجرا می شوند، سپس به ترتیب معکوس، دستورالعمل های بلوک دوم اجرا می شوند. وقتی LoopImitation3 (1، 10) را فرا می‌خوانیم، دریافت می‌کنیم:

سلام N 1
…
سلام N 10
سلام N 10
…
سلام N 1

برای انجام همین کار بدون بازگشت به طور همزمان دو حلقه لازم است.

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

مثال 3: تبدیل یک عدد به سیستم باینری.

همانطور که می دانید، به دست آوردن ارقام یک عدد باینری با تقسیم یک باقی مانده بر پایه سیستم اعداد 2 انجام می شود. اگر یک عدد وجود داشته باشد، آخرین رقم آن در نمایش دودویی آن است.

گرفتن کل قسمت از تقسیم بر 2:

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

در حالی که x> 0 شروع می شود c: = x mod 2; x: = x div 2; نوشتن (ج)؛ پایان؛

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

Recursion گرفتن خروجی را به ترتیب صحیح بدون آرایه و حلقه دوم آسان می کند. برای مثال:

Procedure BinaryRepresentation (x: integer); var c, x: عدد صحیح; شروع (نخستین بلوک. به ترتیب فراخوانی رویه اجرا می شود) c: = x mod 2; x: = x div 2; (تماس بازگشتی) اگر x> 0 باشد، سپس BinaryRepresentation (x); (بلوک دوم. به ترتیب معکوس اجرا می شود) write (c); پایان؛

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

4. روابط عود. بازگشت و تکرار

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

یک مثال ساده از کمیتی که با استفاده از روابط عود محاسبه می شود، فاکتوریل است

فاکتوریل بعدی را می توان از فاکتوریل قبلی به صورت زیر محاسبه کرد:

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

بردارهای فرمول (1) را می توان به عنوان مجموعه ای از مقادیر متغیر تفسیر کرد. سپس محاسبه عنصر مورد نیاز دنباله شامل به روز رسانی مکرر مقادیر آنها خواهد بود. به طور خاص برای فاکتوریل:

X: = 1; برای i: = 2 تا n x: = x * i; نوشتن (x)؛

هر یک از این به روز رسانی (x: = x * i) فراخوانی می شود تکرار، و فرآیند تکرار تکرار است در حال تکرار.

با این حال، توجه داشته باشید که رابطه (1) یک تعریف کاملاً بازگشتی از یک دنباله است و محاسبه عنصر n در واقع گرفتن چندگانه تابع f از خودش است:

به طور خاص، برای فاکتوریل، می توانید بنویسید:

تابع فاکتوریل (n: عدد صحیح): عدد صحیح; اگر n> 1 شروع شود، سپس فاکتوریل: = n * فاکتوریل (n-1) و غیره فاکتوریل: = 1; پایان؛

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

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

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

با یک رویکرد "هدر رو"، می توانید بنویسید:

تابع فیب (n: عدد صحیح): عدد صحیح; اگر n> 1 شروع شود، سپس Fib: = Fib (n-1) + Fib (n-2) و غیره Fib: = 1; پایان؛

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

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

// x1، x2 - شرایط اولیه (1، 1) // n - تعداد تابع عدد فیبوناچی مورد نیاز Fib (x1، x2، n: عدد صحیح): عدد صحیح؛ var x3: عدد صحیح اگر n> 1 شروع شود، x3 شروع شود: = x2 + x1; x1: = x2; x2: = x3; فیب: = فیب (x1، x2، n-1)؛ end else Fib: = x2; پایان؛

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

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

5. درختان

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

5.1. تعاریف اساسی راه های نشان دادن درختان

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

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

برنج. 3. چوب.

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

درخت را می توان به صورت گرافیکی به چندین روش دیگر نشان داد. برخی از آنها در شکل نشان داده شده است. 4. طبق تعریف، درخت سیستمی از مجموعه‌های تودرتو است که این مجموعه‌ها یا تلاقی نمی‌کنند یا کاملاً در یکدیگر قرار می‌گیرند. چنین مجموعه‌هایی را می‌توان به‌عنوان مناطقی در یک صفحه نشان داد (شکل 4a). در شکل 4b، مجموعه های تو در تو در یک صفحه قرار ندارند، بلکه در یک خط گسترش یافته اند. برنج. 4b همچنین می تواند به عنوان نمودار برخی از فرمول های جبری حاوی براکت های تو در تو در نظر گرفته شود. برنج. 4c روش محبوب دیگری برای به تصویر کشیدن ساختار درختی به عنوان یک تاقچه ارائه می دهد.

برنج. 4. روش های دیگر برای به تصویر کشیدن ساختارهای درختی: (الف) مجموعه های تودرتو. (ب) پرانتزهای تو در تو؛ ج) لیست امتیازات.

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

همچنین می توانید قیاسی بین فهرست جدولی و ظاهر فهرست مطالب در کتاب ها ترسیم کنید، جایی که بخش ها شامل بخش های فرعی، آن ها به نوبه خود شامل زیربخش ها و غیره هستند. روش سنتی شماره گذاری این گونه بخش ها (بخش 1، بخش های فرعی 1.1 و 1.2، بخش فرعی 1.1.2 و غیره) سیستم اعشاری دیویی نامیده می شود. به درخت در شکل اعمال شده است. 3 و 4 این سیستم خواهد داد:

1. الف 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. عبور از درختان

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

الگوریتم پیمایش رو به جلو:

• به ریشه بروید،
• تمام زیردرخت ها را از چپ به راست به ترتیب مستقیم طی کنید.

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

به ویژه، برای درخت در شکل. 3 و 4، پیمایش مستقیم دنباله ای از گره ها را به دست می دهد: A، B، C، D، E، F، G.

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

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

// Preorder Traversal نام انگلیسی رویه سفارش مستقیم PreorderTraversal ((Arguments)) است. شروع // قدم زدن در ریشه DoSomething ((Arguments)); // از زیر درخت سمت چپ عبور کنید اگر (درخت فرعی سمت چپ وجود دارد) سپس PreorderTransversal ((Arguments 2)); // از زیر درخت سمت راست عبور کنید اگر (درخت فرعی سمت راست وجود دارد) سپس PreorderTransversal ((Arguments 3)); پایان؛

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

الگوریتم پیمایش معکوس:

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

یعنی همه زیردرخت ها از چپ به راست پیمایش می شوند و بازگشت به ریشه بین این گذرها قرار دارد. برای درخت در شکل. 3 و 4 دنباله ای از گره ها را به دست می دهد: B، A، D، C، E، G، F.

در رویه بازگشتی مربوطه، اقدامات بین تماس های بازگشتی قرار می گیرند. به طور خاص برای یک درخت باینری:

// Inorder Traversal نام انگلیسی روش ترتیب معکوس InorderTraversal ((Arguments)) است. start // از زیر درخت سمت چپ عبور کنید اگر (درخت فرعی سمت چپ وجود دارد) سپس InorderTraversal ((Arguments 2)); // راه رفتن از طریق ریشه DoSomething ((Arguments)); // از زیر درخت سمت راست عبور کنید اگر (درخت فرعی سمت راست وجود دارد) سپس InorderTraversal ((Arguments 3)); پایان؛

الگوریتم پیمایش انتها به انتها:

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

برای درخت در شکل. 3 و 4 دنباله ای از گره ها را به دست می دهد: B، D، E، G، F، C، A.

در رویه بازگشتی مربوطه، اقدامات پس از تماس های بازگشتی ظاهر می شوند. به طور خاص برای یک درخت باینری:

// Postorder Traversal نام انگلیسی برای روند سفارش پسین PostorderTraversal ((Arguments)) است. start // از زیر درخت سمت چپ عبور کنید اگر (درخت فرعی سمت چپ وجود دارد) سپس PostorderTraversal ((Arguments 2)); // از زیر درخت سمت راست عبور کنید اگر (درخت فرعی سمت راست وجود دارد) سپس PostorderTraversal ((Arguments 3)); // راه رفتن از طریق ریشه DoSomething ((Arguments)); پایان؛

5.3. نمای درختی در حافظه کامپیوتر

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

نوع PTree = ^ TTree; TTree = رکورد Inf: integer; LeftSubTree، RightSubTree: PTree; پایان؛

هر گره از نوع PTree است. این یک اشاره گر است، یعنی هر گره باید با فراخوانی رویه New روی آن ایجاد شود. اگر گره برگ است، به فیلدهای LeftSubTree و RightSubTree آن مقدار اختصاص داده می شود. صفر... در غیر این صورت، گره های LeftSubTree و RightSubTree نیز توسط رویه New ایجاد می شوند.

یکی از این رکوردها به صورت شماتیک در شکل نشان داده شده است. 5.

برنج. 5. نمایش شماتیک یک رکورد TTree. یک رکورد دارای سه فیلد است: Inf - مقداری عدد، LeftSubTree و RightSubTree - اشاره گر به رکوردهایی از همان نوع TTree.

نمونه ای از درختی که از چنین رکوردهایی تشکیل شده است در شکل 6 نشان داده شده است.

برنج. 6. درختی که از رکوردهای TTree تشکیل شده است. هر رکورد یک عدد و دو اشاره گر را ذخیره می کند که می تواند هر کدام را داشته باشد صفر، یا آدرس های رکوردهای دیگر از همان نوع.

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

6. نمونه هایی از الگوریتم های بازگشتی

6.1. کشیدن یک درخت

الگوریتم ترسیم درخت را که در شکل نشان داده شده است در نظر بگیرید. 6. اگر هر خط یک گره در نظر گرفته شود، پس این تصویر کاملاً با تعریف درختی که در بخش قبل ارائه شده بود را برآورده می کند.

برنج. 6. درخت کوچک.

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

نمونه ای از چنین رویه ای که در دلفی نوشته شده است، در زیر ارائه شده است:

درخت رویه (بوم: TCanvas؛ // بوم که درخت روی آن کشیده می شود x، y: توسعه یافته؛ // مختصات ریشه زاویه: گسترش یافته؛ // زاویه ای که درخت در آن رشد می کند. طول تنه: گسترش یافته؛ // طول تنه n : عدد صحیح / / تعداد فورک ها (چند // فراخوانی بازگشتی هنوز فراخوانی نشده اند)); var x2, y2: توسعه یافته; // انتهای تنه (نقطه شاخه) x2 شروع می شود: = x + TrunkLength * cos (Angle); y2: = y - TrunkLength * sin (Angle); Canvas.MoveTo (دور (x)، دور (y)); Canvas.LineTo (گرد (x2)، دور (y2)); اگر n> 1 بود، درخت شروع می شود (کانواس، x2، y2، زاویه + پی / 4، 0.55 * طول تنه، n-1). درخت (بوم، x2، y2، Angle-Pi / 4، 0.55 * طول تنه، n-1)؛ پایان؛ پایان؛

برای بدست آوردن انجیر 6 این روال با پارامترهای زیر فراخوانی شد:

درخت (تصویر1. بوم، 175، 325، پی / 2، 120، 15);

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

6.2. برج های هانوی

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

صرف نظر از برهما، این پازل در پایان قرن نوزدهم توسط ریاضیدان فرانسوی ادوارد لوکاس ارائه شد. نسخه فروخته شده معمولاً از 7-8 دیسک استفاده می کرد (شکل 7).

برنج. 7. پازل "برج های هانوی".

فرض کنید راه حلی برای آن وجود دارد n-1 دیسک سپس برای جابجایی nدیسک ها، به صورت زیر عمل کنید:

1) جابجایی n-1 دیسک
2) جابجایی nدیسک بر روی پین آزاد باقی مانده.
3) پشته را جابجا می کنیم n-1 دیسک در مرحله (1) به دست آمد nدیسک.

از آنجایی که برای مورد n= 1، الگوریتم تغییر آشکار است، سپس با القاء با استفاده از اقدامات (1) - (3) می توانیم تعداد دلخواه دیسک را جابجا کنیم.

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

// n - تعداد دیسک ها // a، b، c - شماره پین. انتقال از پایه a، // به پایه b با پایه کمکی c انجام می شود. رویه هانوی (n، a، b، c: عدد صحیح). اگر n> 1 شروع شود سپس هانوی (n-1, a, c, b) شروع شود. writeln (a، "->، b)؛ هانوی (n-1، c، b، a)؛ end else writeln (a، "->"، b); پایان؛

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

6.3. تجزیه عبارات حسابی

وظیفه تجزیه محاسبه مقدار عبارت با استفاده از رشته موجود حاوی عبارت حسابی و مقادیر شناخته شده متغیرهای موجود در آن است.

فرآیند محاسبه عبارات حسابی را می توان به صورت یک درخت دودویی نشان داد. در واقع، هر یک از عملگرهای حسابی (+، -، *، /) به دو عملوند نیاز دارند که آنها نیز عبارت های حسابی خواهند بود و بر این اساس، می توانند به عنوان زیردرخت در نظر گرفته شوند. برنج. 8 نمونه ای از درختی را نشان می دهد که با عبارت مطابقت دارد:

برنج. 8. درخت نحو مربوط به عبارت حسابی (6).

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

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

هنگام ساختن درخت نحو، باید به ویژگی زیر توجه کنید. اگر مثلاً عبارت وجود داشته باشد

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

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

برنج. 9. درخت نحو برای بیان آ – ب + جهنگام خواندن از چپ به راست (الف) و از راست به چپ (ب).

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

7.3. تعیین یک گره درخت با تعداد آن

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

برای مثال فرض کنید می خواهید اجرا کنید کحلقه های تو در تو nمراحل در هر کدام:

برای i1: = 0 تا n-1 برای i2 ​​انجام دهید: = 0 تا n-1 برای i3 انجام دهید: = 0 تا n-1 انجام دهید ...

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

Procedure NestedCycles (شاخص ها: آرایه عدد صحیح؛ n، k، عمق: عدد صحیح). var i: عدد صحیح; اگر عمق شروع شود

برای خلاص شدن از شر بازگشت و کاهش همه چیز به یک حلقه، توجه داشته باشید که اگر مراحل را در ریشه شماره گذاری کنید n، سپس هر مرحله دارای یک عدد متشکل از ارقام i1، i2، i3، ... یا مقادیر مربوطه از آرایه Indexes است. یعنی اعداد با مقادیر شمارنده چرخه مطابقت دارند. شماره گام در سیستم اعشاری معمول:

کل مراحل خواهد بود n k... با مرور اعداد آنها در سیستم نمادگذاری اعشاری و ترجمه هر یک از آنها به یک سیستم با ریشه n، مقادیر شاخص ها را بدست می آوریم:

M: = دور (IntPower (n، k)); برای i: = 0 تا M-1 شروع کنید شماره: = i; برای p: = 0 تا k-1 شروع کنید شاخص ها: = شماره mod n; شماره: = عدد div n; پایان؛ DoSomething (شاخص ها)؛ پایان؛

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

کنترل سوالات

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

(الف) هنگامی که Rec (4) فراخوانی شود، رویه زیر چه خواهد شد؟

Procedure Rec (a: integer); شروع نوشتن (a)؛ اگر a> 0 سپس Rec (a-1)؛ نوشته شده (الف)؛ پایان؛

(ب) مقدار تابع Nod (78، 26) چقدر خواهد بود؟

تابع Nod (a, b: integer): عدد صحیح; اگر a> b شروع شود، سپس نود: = نود (a - b, b) در غیر این صورت اگر b> a سپس نود: = اشاره (a, b - a) در غیر این صورت اشاره: = a; پایان؛

(ج) هنگام فراخوانی A (1) رویه های زیر چه مواردی را چاپ می کنند؟

رویه A (n: عدد صحیح). روش B (n: عدد صحیح)؛ روش A (n: عدد صحیح)؛ شروع نوشتن (n); B (n-1)؛ پایان؛ روش B (n: عدد صحیح)؛ شروع نوشتن (n); اگر n

(د) رویه زیر هنگام فراخوانی BT (0، 1، 3) چه خواهد شد؟

روش BT (x: واقعی؛ D، MaxD: عدد صحیح). اگر D = MaxD شروع شود، سپس بنویسید (x) در غیر این صورت BT شروع شود (x - 1، D + 1، MaxD). BT (x + 1، D + 1، MaxD)؛ پایان؛ پایان؛

2. Ouroboros - یک مار که دم خود را می بلعد (شکل 14) هنگامی که باز می شود دارای طول است. L، قطر نزدیک سر دی، ضخامت دیواره شکم د... تعیین کنید چقدر دم می تواند در خودش جای بگیرد و بعد از آن دم در چند لایه گذاشته شود؟

برنج. 14. ماروبوروهای باز شده.

3. برای درخت در انجیر. 10a توالی بازدید گره ها را برای ترتیب پیمایش رو به جلو، عقب و انتها به انتها نشان می دهد.

4. یک نمایش گرافیکی از درخت، که با استفاده از براکت های تو در تو تعریف شده است، رسم کنید: (A (B (C، D)، E)، F، G).

5. درخت نحو را برای عبارت حسابی زیر رسم کنید:

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

6. برای نمودار زیر (شکل 15)، ماتریس مجاورت و ماتریس بروز را یادداشت کنید.

وظایف

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

2. یک تابع بازگشتی بنویسید که پرانتزهای صحیح را در یک رشته بررسی کند. با قرارگیری صحیح، شرایط زیر برآورده می شود:

الف) تعداد پرانتزهای باز و بسته برابر است.
(ب) در داخل هر جفت پرانتز باز - پرانتز بسته مربوطه، پرانتزها به درستی قرار می گیرند.

نمونه هایی از قرار دادن نادرست:) (، ()) (، ()) (()) و غیره.

3. این خط ممکن است دارای پرانتز، هم پرانتز و هم پرانتز باشد. هر پرانتز باز مربوط به یک بسته از همان نوع (گرد - گرد، مربع - مربع) است. یک تابع بازگشتی بنویسید تا بررسی کنید که آیا پرانتزها در این مورد درست هستند یا خیر.

نمونه ای از قرار دادن نادرست: ([)].

4. تعداد سازه‌های براکت صحیح به طول 6 5 عدد است:
یک برنامه بازگشتی بنویسید تا تمام ساختارهای براکت درست به طول 2 را ایجاد کند n.

نشانه: ساختار پرانتز درست با حداقل طول "()". سازه های بلندتر از سازه های کوتاهتر به دو روش بدست می آیند:

(الف) اگر ساختار کوچکتر در داخل پرانتز محصور شده باشد،
(ب) اگر دو ساختار کوچکتر به ترتیب نوشته شوند.

5. روتینی ایجاد کنید که همه جایگشت های ممکن را برای اعداد صحیح از 1 تا N چاپ کند.

6. رویه ای ایجاد کنید که تمام زیرمجموعه های مجموعه (1، 2،…، N) را چاپ کند.

7. رویه ای ایجاد کنید که تمام نمایش های ممکن از عدد طبیعی N را به عنوان مجموع اعداد طبیعی دیگر چاپ کند.

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

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

10. رویه ای ایجاد کنید که منحنی کوخ را ترسیم کند (شکل 12).

11. شکل را تکثیر کنید. 16. در شکل، در هر تکرار بعدی، دایره 2.5 برابر کوچکتر است (این ضریب را می توان به عنوان یک پارامتر ایجاد کرد).

ادبیات

1.D. کنات. هنر برنامه نویسی کامپیوتر. v. 1. (بخش 2.3. "درختان").
2. N. Virt. الگوریتم ها و ساختارهای داده

کارکرد: به صورت بازگشتی داده می شودتابع در تعریف خود حاوی خود است، به ویژه، تابع تعریف شده توسط فرمول بازگشتی بازگشتی است. بنابراین، یک عبارت می‌تواند مجموعه بی‌نهایتی از روش‌ها را برای محاسبه یک تابع ارائه دهد، مجموعه‌ای از اشیاء را با استفاده از تعاریف خصوصی قبلی تعریف کند.

داده ها

Struct element_of_list (element_of_list * next; / * پیوند به عنصر بعدی از همان نوع * /داده های بین المللی؛ / * برخی از داده ها * /)؛

یک ساختار داده بازگشتی اغلب استفاده از بازگشت را برای پردازش آن داده دیکته می کند.

در فیزیک

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

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

در زبان شناسی

توانایی یک زبان برای تولید جملات و ساختارهای تودرتو. پیشنهاد اولیه " گربه موش را خورد"می توان با بازگشت به عنوان تمدید کرد وانیا حدس زد که گربه موش را خورد، سپس به عنوان کاتیا می داند که وانیا حدس زد که گربه موش را خوردو غیره. بازگشت یکی از کلیات زبانی محسوب می شود، یعنی مشخصه هر زبان طبیعی است. با این حال، اخیراً بحث فعالی در مورد عدم وجود بازگشت احتمالی در یکی از زبان های آمازون - Piraha وجود داشته است که توسط زبان شناس دانیل اورت (Daniel Everett) ذکر شده است. انگلیسی) .

در فرهنگ

بیشتر لطیفه هایی که در مورد بازگشت وجود دارد مربوط به بازگشت بی نهایت است که در آن شرط خروج وجود ندارد، مثلاً ضرب المثل معروف است: "برای درک بازگشت، ابتدا باید بازگشت را درک کنید."

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

چندین داستان از استانیسلاو لم به حوادث (احتمالی) با بازگشت بی نهایت اختصاص دارد:

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

من اطلاعات کوتاه زیر را پیدا کردم:
"SEPULKI یک عنصر مهم از تمدن Ardrit (نگاه کنید به) از سیاره Enteropia (نگاه کنید به). رجوع به SEPULCARIA شود.
من به این توصیه عمل کردم و خواندم:
"SEPULKARIA - دستگاه هایی برای جداسازی (نگاه کنید به)".
من به دنبال Sepulenie گشتم. آن را خوانده بود:
«SEPULENIE شغل آردیت ها (نگاه کنید به) از سیاره انتروپیا (نگاه کنید به) است. SEPULKI را ببینید.

لم اس. «خاطرات ستارگان ایون تیخی. سفر چهاردهم.»

• داستانی از "Cyberiada" در مورد یک ماشین هوشمند که دارای هوش و تنبلی کافی برای ساختن یک دستگاه مشابه برای حل کار و سپردن راه حل به آن بود (نتیجه یک بازگشت بی پایان بود، زمانی که هر ماشین جدید مشابهی را می ساخت و از آن عبور می کرد. وظیفه به آن).
• کلمات اختصاری بازگشتی: GNU (GNU Not Unix)، PHP (PHP: Hypertext Preprocessor) و غیره.

را نیز ببینید

• توالی معکوس

یادداشت ها (ویرایش)

بنیاد ویکی مدیا 2010.

• حافظه ویدیویی
• تابش الکترومغناطیسی

ببینید «بازگشت» در فرهنگ‌های دیگر چیست:

بازگشت- بازگشت، تکرار فرهنگ لغت مترادف های روسی. اسم بازگشتی، تعداد مترادف ها: 1 ... فرهنگ لغت مترادف

بازگشت- - [] بازگشت در یک مفهوم کلی، محاسبه یک تابع بر اساس یک الگوریتم خاص. نمونه‌هایی از این الگوریتم‌ها فرمول‌های تکراری هستند که محاسبه یک عبارت معین را استخراج می‌کنند. راهنمای مترجم فنی

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

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

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

بازگشت- (زمینه.) (لات. recursio بازگشت). یکی از سه مرحله بیان صداها، تورفتگی است. ترجمه اندام های گفتار به حالت آرام یا شروع بیان صدای بعدی. در کلمه استراحت، بازگشت (تورفتگی) هنگام بیان [t] می تواند با ... ... همپوشانی داشته باشد. فرهنگ اصطلاحات زبانشناسی T.V. کره اسب

یوتیوب دانشگاهی

• 1 / 5

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

  e = 2 + 2 2 + 3 3 + 4 4 +… = 2 + f (2) (\ displaystyle e = 2 + (\ cfrac (2) (2 + (\ cfrac (3) (3 + (\ cfrac ( 4) (4+ \ ldots)))))) \; = 2 + f (2))، جایی که f (n) = n n + f (n + 1) (\ displaystyle f (n) = (\ cfrac (n) (n + f (n + 1))))محاسبه مستقیم با استفاده از فرمول بالا باعث بازگشت بی نهایت می شود، اما می توان ثابت کرد که مقدار f (n) با افزایش n به یک میل می کند (بنابراین با وجود بی نهایت بودن سری، مقدار عدد اویلر متناهی است). برای محاسبه تقریبی مقدار e کافی است به طور مصنوعی عمق بازگشت را به یک عدد از پیش تعیین شده مشخص از قبل محدود کنید و با رسیدن به آن به جای استفاده از آن از آن استفاده کنید. f (n) (\ displaystyle f (n))واحد.

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

  Struct element_of_list (element_of_list * next; / * اشاره گر به عنصر بعدی از همان نوع * /داده های بین المللی؛ / * برخی از داده ها * /)؛

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