Бұл не?
Сабақтың тақырыбы — «Рекурсия». Талдап көрейік. Рекурсия — функция міндетті өзін-өзі шақыру арқылы шешетін жағдай, бірақ кішірек міндет үшін. Матрешканы еске түсір: біреуін ашасың, ал ішінде дәл сондай, тек кішірек матрешка, және солай ашылмайтын ең кішкентайына дейін. Сол ең кішкентай матрешка — бәрі тоқтайтын базалық жағдай.
Бұл не үшін керек?
Рекурсия көптеген технологияда жасырынып жатыр: дискідегі бумаларды осылай аралап шығады, веб-беттер мен бағдарлама кодын талдайды, ойындарда шешімдер ағашын құрады және компьютерлік графикада фракталдар салады. Сұрыптау мен іздеудің көптеген жылдам алгоритмдері «міндетті екіге бөліп, әр жартысын сол тәсілмен шеш» деген қағида бойынша құрылған. Жасанды интеллект рекурсивті функцияны оңай жазады, бірақ оның базалық жағдайы жоқ екенін және шексіздікке кетіп қалатынын немесе жадты толтырып жіберетінін тек механизмді түсінетін адам ғана байқай алады. Үлкен міндетті дәл сондай кішкентай міндеттерге бөле білу — инженер мен зерттеушінің негізгі дағдысы.
Бұл қалай жұмыс істейді?
Әр рекурсивті шақыру өз жұмысын кейінге қалдырып, оның ішіндегі кішірек шақыру аяқталғанша күтеді. Компьютер осы күтіп тұрған шақыруларды шақырулар стегі деп аталатын бумаға жинайды: соңғы басталған шақыру бірінші аяқталады, бумадағы тәрелкелер сияқты. Іс базалық жағдайға жеткенде, жауап жоғары қайтарылады, және шақырулар бірінен соң бірі аяқталады. Ханой мұнарасында бұл былай көрінеді: үлкен мұнараны көшіру үшін кішірек мұнараны қосалқы өзекке көшіресің, ең үлкен дискіні ауыстырып саласың да, кішірек мұнараны қайтадан соның үстіне көшіресің.
Аздап тарих
«Ханой мұнарасы» басқатырғышын француз математигі Эдуар Люка ойлап тауып, оны бір мың сегіз жүз сексен үшінші жылы сатылымға шығарды. Оған алпыс төрт алтын дискіні ауыстырып салып жатқан монахтар туралы және олар бұл істі бітіргенде әлемнің ақыры келетіні туралы аңыз қоса берілді. Бірақ секундына бір дискіден ауыстырса да, бұған жүздеген миллиард жыл кетеді, сондықтан уайымдайтын ештеңе жоқ.
Формула: факториал
Эн факториал — бірден эн-ге дейінгі барлық сандардың көбейтіндісі. Байқа: егер эн минус бір факториалды білсең, оны эн-ге көбейту жеткілікті — міне, рекурсия: эн факториал тең эн көбейту эн минус бір факториал. Шақырулар шексіз жалғаспауы үшін базалық жағдай керек: нөл факториал бірге тең, оны компьютер бірден біледі. Эн әрпі — теріс емес бүтін сан, оның бірліктері жоқ. Эн-ді бірге арттырсақ, жауап эн қосу бір есе өседі, сондықтан факториал керемет тез өседі.
n! = n · (n − 1)!n — теріс емес бүтін сан, —
n! — факториал: 1-ден n-ге дейінгі сандардың көбейтіндісі, —0! = 10! — рекурсияның базалық жағдайы, —
Формула: жүрістер саны
Эн дискіден тұратын мұнараны көшіру үшін неше жүріс керек? Рецептке қара: эн минус бір дискіден тұратын мұнараны екі рет көшіреміз де, ең үлкен дискімен бір жүріс жасаймыз. Демек, әр жаңа диск жұмысты екі есе арттырып, тағы бір жүріс қосады, ал қорытындысында екінің эн дәрежесінен бірді азайтқан сан шығады. Эн әрпі — дискілер саны, жауап — жүрістердің ең аз саны. Бір диск — бір жүріс, екі диск — үш жүріс, үшеуі — жеті, ал төрт диск — он бес; тағы бір диск қоссаң, жүрістер екі еседен де көп болады.
ходов = 2ⁿ − 1n — дискілер саны, —
2ⁿ − 1 — жүрістердің ең аз саны, —
Практикада не істейміз?
Ал енді практикалық тапсырманы орындап көрейік. Алдыңда үш өзек тұр: А — қайдан көшіреміз, Б — қосалқы, В — қайда көшіреміз, ал А өзегінде төрт дискіден тұратын мұнара тұр, ең үлкені төменде. Бүкіл мұнараны дискілерді бір-бірлеп ауыстырып және ешқашан үлкен дискіні кішісінің үстіне қоймай, дәл он бес жүрісте В өзегіне көшіру керек. Рекурсивті ойлан: ең үлкен дискіні босату үшін үстіңгі үшеуін алдымен қайда алып қою керек? Ал үшеуін алып қою үшін үстіңгі екеуімен не істеу керек? Жүрістер санауышын бақыла — он беске сыйсаң, демек, сен екінің төртінші дәрежесінен бірді азайту формуласын қайталадың. Егер бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, мен жауап беремін. Уайымдама.