زیر برنامه ها بازگشت


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

اگر ریاضیات را به خاطر دارید، در آنجا می توانید اصل استقراء ریاضی را برآورده کنید. به شرح زیر است:  برخی از گزاره ها برای هر طبیعی n اگر
درست است     1) برای n = 1;
معتبر است     2) از اعتبار عبارت برای هر طبیعی دلخواه n = k  نتیجه می‌شود که برای n = k+1 صادق است.

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

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

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

void Rec(int a)
{
  if (a>0) { Rec(a-1);
  Console.WriteLine(a);
}

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

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

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

Training problem

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

ما دریافتیم که بازگشت، اجرای مکرر دستورات موجود در یک زیر روال است. و این به نوبه خود شبیه کار چرخه است. زبان های برنامه نویسی هستند که ساختار حلقه در آنها اصلا وجود ندارد، به عنوان مثال، Prolog. 
بیایید سعی کنیم کار حلقه برای را شبیه سازی کنیم. 
حلقه for حاوی یک متغیر شمارنده گام است. در یک زیر روال بازگشتی، چنین متغیری می تواند به عنوان یک پارامتر ارسال شود. <پیش> // رویه LoopImitation() با دو پارامتر // پارامتر اول – گام شمار، پارامتر دوم – تعداد کل مراحل static void LoopImitation(int i، int n) { Console.WriteLine("Hello N" + i); دستور // برای هر مقدار i تکرار شود اگر (i < n) // تا زمانی که شمارنده حلقه برابر n شود، { LoopImitation(i+1, n); // در حال فراخوانی جدید رویه نمونه، با پارامتر i+1 (به مقدار i بعدی بروید) } }

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 />   <بدن>
تابع فاکتوریل بازگشتی الگوریتم تکراری
<پیش> static int Factorial(int n){ اگر (n > 1) return n * Factorial(n - 1); else بازگشت 1; } <پیش> int x = 1; برای (int i = 2; i <= n; i++) x = x * i; Console.WriteLine("%d"، x);

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

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

Training problem

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

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

در در برخی موقعیت‌ها در رویه‌ها، می‌توانید از کلمه return  بدون آرگومان استفاده کنید - یعنی در واقع، رویه هنوز چیزی را بر نمی‌گرداند. این می‌تواند هنگام تکرار، زمانی که  ;return  برای پایان دادن به نزول در موارد پایه مقادیر پارامترهایی که دوباره برگشت داده شده اند استفاده می شود. به عنوان مثال، رویه ای که یک عدد را از اعشار به دودویی تبدیل می کند ممکن است به شکل زیر باشد: static void printTwo (int n) {     اگر (n == 0) بازگشت;   printTwo(n / 2);   if (n % 2 == 0) Console.Write(0);   else Console.Write(1); }

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 است. در این حالت، باید کلمه به دست آمده را روی صفحه نمایش دهید و از رویه خارج شوید.

برنامه سی شارپ به این شکل خواهد بود.
// w - پارامتر قابل تغییر (رشته-نتیجه) // رویه TumbaWords به عنوان یک رشته کاراکتر از الفبا عبور داده می شود، // کلمه کلمه و تعداد کاراکترهایی که قبلاً تنظیم شده است (در ابتدا – 0) استاتیک void TumbaWords (رشته A، رفرانس w، int N) { if (N == w.Length) // w.Length - تعداد کاراکترهای رشته {   // اگر همه کاراکترها قبلاً روی کلمه تنظیم شده باشند،       // سپس لازم است یک رشته خروجی گرفته شود و رویه پایان یابد Console.WriteLine(w); برگشت؛ } برای ( int i = 0; i < w.Length; i ++ ) // اگر شرط بالا نادرست باشد (یعنی همه کاراکترها فاصله نداشته باشند، {     // اگر شرط بالا نادرست است (یعنی همه کاراکترها با هم فاصله ندارند،     // سپس در حلقه تمام کاراکترهای الفبا و را مرور می کنیم   // به طور متناوب شخصیت را در اولین فضای آزاد قرار دهید w += A[i]; TumbaWords (A, ref w, N+1); w = w.Remove(w.Length - 1); // و سپس آخرین کاراکتر اضافه شده را حذف کنید،   // برای ساختن یک کلمه جدید با همان پیشوند } } استاتیک void Main() { int n = Convert.ToInt32(Console.ReadLine()); کلمه رشته = ""; TumbaWords("KLMN"، کلمه مرجع، 0); }
توجه داشته باشید که w یک پارامتر قابل تغییر (رشته نتیجه) است!

Training problem

تکرار روی خطوط