Rekursiv funksiyalar

Hanoy minorasi masalasi


Xalqalar sonini kiriting: 3


Xalqa A dan C ga o'tkazilsin
Xalqa A dan B ga o'tkazilsin
Xalqa C dan B ga o'tkazilsin
Xalqa A dan C ga o'tkazilsin
Xalqa B dan A ga o'tkazilsin
Xalqa B dan C ga o'tkazilsin
Xalqa A dan C ga o'tkazilsin
Tahlil qilib ko‘rilsa, A qoziqdagi barcha xalqalarni C qoziqqa o‘tkazish uchun 2³-1=7 ta jarayon bajarildi. Xalqalar soni 64 ta bo‘lganda bu jarayonlar soni 2⁶⁴-1 ga y’ani, 18 446 744 073 709 551 615 teng bo‘ladi.
Bundan kelib chiqadiki:
Bir yildagi sekundlar soni 31 536 000 ga teng. Bir dona diskni bir qoziqdan boshqasiga olib o‘tish uchun bir sekund sarflanadi deb hisoblansa quyidagiga kelish mumkin:
18 446 744 073 709 551 615 : 31 536 000=584 942 417 355.072
Barcha 64 ta diskni A qoziqdan C qoziqqa olib o‘tish uchun
584 942 417 355.072 yil kerak bo‘ladi. Kompyuter bir sekundda bir milliard (10⁹) operatsiya bajara oladi deb hisoblansa, bir yilda quyidagicha operatsiya bajara oladi:
31 536 000*10⁹ = 31 536 000 000 000 000.
64 ta diskni A qoziqdan C qoziqqa olib o‘tish uchun kompyuterga quyidagicha miqdorda vaqt kerak bo‘ladi:
18 446 744 073 709 551 615 : 31 536 000 000 000 000 585
Ya’ni, 585 yil vaqt kerak bo‘ladi.


Nazorat savollari

1. 
   Rekursiya deb nimaga aytiladi?
   
2. 
   Rekursiya uchun qanday aniqlanishlar o‘rinli?
   
3. 
   Agar faktorial funksiyasiga n>0 qiymat berilsa, qanday holat ro‘y beradi?
   
4. 
   Rekursiv funksiyalarni to‘g‘ri amal qilishi uchun qanday to‘xtash sharti bo‘lishi kerak?
   
5. 
   Har bir rekursiv murojaat qo‘shimcha xotira talab qiladimi?
   
6. 
   Rekursiya chiroyli, ixcham ko‘ringani bilan xotirani tejash va hisoblash vaqtini qisqartirish nuqtai-nazaridan uni imkon qadar iterativ hisoblash bilan almashtirilgani ma’qulmi?
   
7. 
   Rekursiya qanday to‘xtatiladi?
   
8. 
   Har bir rekursiv formula nechta ifodaga ega bo‘lishi kerak?