زیربرنامه های (پایتون). بازگشت

بازگشت

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

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

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

مثال

<پیش> def Rec(a): اگر (a>0): Rec(a-1) چاپ (الف)
به طور شماتیک، کار بازگشت را می توان با یک نمودار جریان نشان داد



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

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

بازگشت به عنوان جایگزینی حلقه

دیده‌ایم که بازگشت، اجرای مکرر دستورالعمل‌های موجود در یک زیر روال است. و این به نوبه خود شبیه کار چرخه است. زبان های برنامه نویسی هستند که ساختار حلقه در آنها به طور کلی وجود ندارد. به عنوان مثال، Prolog. 
بیایید سعی کنیم کار حلقه for را شبیه سازی کنیم. 
حلقه for حاوی یک متغیر شمارنده گام است. در یک زیربرنامه بازگشتی، چنین متغیری می تواند به عنوان یک پارامتر ارسال شود. <پیش> # Procedure LoopImitation () با دو پارامتر # پارامتر اول – گام شمار، پارامتر دوم – تعداد کل مراحل Def LoopImitation(i، n): print("Hello N"، i) # عبارت برای هر مقدار i تکرار شود اگر من < n: # تا زمانی که شمارنده حلقه با مقدار n برابر شود، LoopImitation(i + 1, n) # یک نمونه جدید از رویه را فراخوانی کنید. # با پارامتر i+1 (به مقدار بعدی i بروید)

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

تکرار در برنامه نویسی - یک مرحلهفرایند پردازش چرخه ای داده. 
اغلب الگوریتم های تکرار شونده در مرحله جاری (تکرار) از نتیجه عملیات یا عمل مشابه محاسبه شده در مراحل قبلی استفاده می کنند.  یک مثال از این محاسبات، محاسبه روابط تکراری است. 
یک مثال ساده از یک مقدار بازگشتی فاکتوریل است: \(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\)) حالت پایه (شرط پایان بازگشت) و خط دوم انتقال به مرحله بعدی است.   <بدن>

تابع فاکتوریل بازگشتی	الگوریتم تکراری
def Factorial(n): اگر n > 1: بازگشت n * فاکتوریل (n - 1) دیگر:   بازگشت 1	x=1 برای i در محدوده (1, n + 1): x = x * i;

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

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

وظیفه

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

مشکل یک مشکل brute-force معمولی است که می تواند به یک مشکل کوچکتر کاهش یابد.
ما به ترتیب حروف را جایگزین کلمه می کنیم.
اولین موقعیت یک کلمه می تواند یکی از 4 حرف الفبا (K, L, M, N) باشد.
ابتدا حرف 'K' را اول قرار دهید. سپس، برای به دست آوردن همه انواع با حرف اول 'K'، باید همه ترکیب‌های ممکن حروف را در n-1 موقعیت‌ها و .etc. (تصویر را ببینید)

بنابراین، ما به یک راه حل بازگشتی رسیدیم: در یک حلقه، تمام حروف اول ممکن را مرور کنید (هر حرف الفبا را به نوبه خود در وهله اول قرار دهید) و برای هر مورد تمام "دم" های ممکن را بسازید. طول n-1.
 

تکرار بازگشتی کاراکترها

شما باید بازگشت را متوقف کنید و زمانی که قسمت باقی مانده خالی است (n = 0)، کلمه تمام شده را خروجی بگیرید. همه حروف قبلا انتخاب شده اند. 
روال بازگشتی به این صورت است:  <پیش> def TumbaWords (کلمه، الفبا، n): اگر n < 1: چاپ (کلمه) برگشت برای c در الفبا: TumbaWords (کلمه + ج، الفبا، n - 1)