(C++) بازگشتی


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

اگر ریاضیات را به خاطر دارید، در آنجا می توانید اصل استقراء ریاضیرا ببینید. به شرح زیر است:

برخی از گزاره ها برای هر n if
طبیعی صادق است     1. برای n = 1 و
معتبر است     2. از اعتبار عبارت برای هر طبیعی دلخواه n = k  نتیجه می شود که برای n = k+1
صادق است.
در برنامه نویسی به این تکنیک recursion
می گویند
بازگشت روشی برای تعریف مجموعه ای از اشیا بر اساس خود مجموعه، بر اساس موارد پایه ساده داده شده است.

بازگشتی همچنین رویه (تابع) نامیده می‌شود که مستقیماً یا از طریق سایر رویه‌ها و توابع خود را فراخوانی می‌کند
نمونه ای از یک روش بازگشتی: <پیش> void Rec(int a) { اگر (a>0) Rec(a-1); cout << آ؛ } به طور شماتیک، کار بازگشت را می توان با یک نمودار جریان نشان داد

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

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

Training problem

بازگشت. این چیه؟

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

حلقه for حاوی یک متغیر شمارنده گام است. در یک زیربرنامه بازگشتی، چنین متغیری می تواند به عنوان یک پارامتر ارسال شود. // Procedure LoopImitation() با دو پارامتر. // پارامتر اول – گام شمار، پارامتر دوم – تعداد کل مراحل Void LoopImitation (int i، int n) { cout << "سلام ن" << من << endl; // عملگر برای هر مقدار i تکرار شود اگر (i < n) // تا زمانی که شمارنده حلقه برابر n شود، { // یک نمونه جدید از رویه را با پارامتر i+1 فراخوانی کنید (به مقدار بعدی i بروید). LoopImitation(i + 1, n); } }

Training problem

بازگشت. شبیه سازی چرخه

بازگشت و تکرار
برای درک بازگشت، باید بازگشت را درک کنید...
 
تکرار در برنامه نویسی - یک مرحلهفرایند پردازش چرخه ای داده. 
اغلب الگوریتم های تکرار شونده در مرحله جاری (تکرار) از نتیجه عملیات یا عمل مشابه محاسبه شده در مراحل قبلی استفاده می کنند.  یک مثال از این محاسبات، محاسبه روابط تکراری است. 
یک مثال ساده از یک مقدار بازگشتی فاکتوریل است: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
محاسبه مقدار در هر مرحله (تکرار) \(N=N \cdot i\) است.  هنگام محاسبه مقدار \(N\)، مقدار ذخیره شده از قبل \(N\).< br />
فاکتوریل یک عدد را می توان با استفاده از فرمول بازگشتی نیز توصیف کرد:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)

ممکن است متوجه شوید که این توضیحات چیزی بیش از یک تابع بازگشتی نیست.
در اینجا خط اول (\(n <= 1\)) حالت پایه (شرط پایان بازگشت) و خط دوم انتقال به مرحله بعدی است.  < br />   <بدن>
تابع فاکتوریل بازگشتی الگوریتم تکراری
int فاکتوریل (int n) { اگر (n > 1) return n * Factorial(n - 1); else بازگشت 1; } x = 1; برای (i = 2; i <= n; i++) x = x * i; cout << x;

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

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

Training problem

بازگشت و تکرار

وظیفه
در الفبای زبان قبیله "تومبا-یومبا"; چهار حرف: "K"، "L"، "M" و "N". شما باید تمام کلمات متشکل از n حروف را که می‌توان از حروف این الفبا ساخت، نمایش دهید.

مشکل یک مشکل brute-force معمولی است که می تواند به یک مشکل کوچکتر کاهش یابد.
ما به ترتیب حروف را جایگزین کلمه می کنیم.
اولین موقعیت یک کلمه می تواند یکی از 4 حرف الفبا (K. L, M, N) باشد.
اجازه دهید حرف K را ابتدا قرار دهیم. سپس، برای دریافت همه انواع با حرف اول K، باید همه ترکیب‌های ممکن حروف را در موقعیت‌های n - 1 باقی‌مانده و غیره برشمارید. (تصویر را ببینید).
بنابراین، مسئله به حل چهار مسئله با طول n - 1 کاهش می یابد.
 
تکرار بیش از n کاراکتر به صورت بازگشتی
w[0]='K'; // روی آخرین کاراکترهای L-1 تکرار شود w[0]='L'; // روی آخرین کاراکترهای L-1 تکرار شود w[0]='M'; // روی آخرین کاراکترهای L-1 تکرار شود w[0]='N'; // روی آخرین کاراکترهای L-1 تکرار شود w - یک رشته کاراکتر که کلمه کاری را ذخیره می کند.
بنابراین، ما بازگشت را دریافت کردیم. می‌توانیم حل مشکل را در قالب یک رویه بازگشتی ترتیب دهیم. 
باقی مانده است که مشخص شود بازگشت کی به پایان می رسد؟ وقتی همه کاراکترها تنظیم می شوند، یعنی تعداد کاراکترهای مجموعه n است. در این حالت، باید کلمه به دست آمده را روی صفحه نمایش دهید و از رویه خارج شوید.

برنامه C++ به این شکل خواهد بود.
#include<iostream> با استفاده از namespace std. void TumbaWords( رشته A، رشته &w، int N) // w - پارامتر قابل تغییر (رشته-نتیجه) // رویه TumbaWords به عنوان یک رشته کاراکتر از الفبا عبور داده می شود، // کلمه کلمه و تعداد کاراکترهایی که قبلاً تنظیم شده اند (قبل از – 0). { int i; اگر (N == w.size()) {   // اگر همه کاراکترها قبلاً روی کلمه تنظیم شده باشند،     // سپس لازم است یک رشته خروجی گرفته شود و رویه پایان یابد cout << w<< endl; برگشت؛ } برای (i = 1; i < A.size(); i ++) {   // اگر شرط بالا نادرست باشد (یعنی همه کاراکترها فاصله نداشته باشند،   // سپس در حلقه تمام کاراکترهای الفبا و را مرور می کنیم // به طور متناوب شخصیت را در اولین فضای آزاد قرار دهید w[N] = A[i]; TumbaWords (A, w, N+1)؛ } } main() { intn; کلمه رشته intn; cin>> n word.resize(n); // رشته را به اندازه n افزایش دهید TumbaWords ("KLMN"، word، 0 ); }
توجه داشته باشید که w یک پارامتر قابل تغییر (رشته نتیجه) است!

Training problem

تکرار روی خطوط شماره 1