لیست ها و بازگشت ها را توصیف کنید .
لیست ها و بازگشت ها را توصیف کنید .
بیان خیلی از عملیات لیستها با استفاده از متدهاي بازگشتی بسیار عادي است. براي نمونه، در زیر یک الگوریتم بازگشتی را براي چاپ یک لیست بهطور معکوس مشاهده میکنید.
1 .لیست را به دو قطعه تفکیک کن: اولین گره (که رأس نامیده میشود) و بقیۀ آن (کـه دنبالـه نامیده میشود)
2 .دنباله را بهطور معکوس چاپ کن.
3 .رأس را چاپ کن.
البته در گام فراخوانی بازگشتی، فرض میشود که ما راهی براي چاپ یـک لیسـت بـهطـور معکوس در اختیار داریم. اما اگر فرض کنیم که فراخوانی بازگشتی کار میکنـد -بـر اسـاسجهـش بـا اطمینان- آنگاه میتوانیم خودمان را قانع کنیم که این الگوریتم کار میکند. تمام آنچه که نیاز داریم یک حالت مبنا و راهی براي اثبات ایـن موضـوع اسـت کـه بـهازاء هـر لیست، ما سرانجام به حالت مبنا میرسیم. با در نظر گرفتن تعریف بازگشـتی یـک لیسـت یـک حالـت مبناي معمول، لیستی تهی است که با None نمایش داده میشود:
def printBackward(list):
if list == None: return
head = list
tail = list.next
printBackward(tail)
print head,
اولین خط به عنوان حالت مبنا رفتار میکند که در عمل کاري انجام نمیدهـد. دو خـط بعـدي لیست را به رأس و دنباله تفکیک میکند و دو خط آخر لیست را چاپ میکنـد. کامـایی کـه در پایـان آخرین خط وجود دارد، پایتون را از چاپ خط جدید بعد از هر گره باز میدارد. ما همانطور که printList را فراخوانی کردیم، این تابع را فراخوانی میکنیم:
>>> printBackward(node1)
3 2 1
نتیجه یک لیست معکوس است. ممکن است تعجب کنید کـه چـرا printList و printBackward تـابع هسـتند و نـه متدهایی در کلاس Node . دلیل این امر آن است که ما میخواهیم از None براي نمایش یک لیست تهی استفاده کنـیم و احضار یک متد بر روي None قانونی نیست. این محدودیت توابع را بـراي نوشـتن کـدي زیبـا و قابـل دستکاري به سبک شیءگرا نامناسب میسازد. آیا میتوانیم ثابت کنیم که printBackward همیشه پایان مـییابـد؟ بـه بیـانی دیگـر آیـا همیشه به حالت مبنا میرسیم؟ در حقیقت پاسخ منفی است. بعضـی از لیسـتهـا ایـن متـد را خـراب میکنند.
برای اموزش های ویدیویی زبان پایتون به بستر ویدیو های اموزشی بروید
ثبت نام
با ایمیل خود وارد شویدورود
