Рекурсия
Екі айна бір-біріне қарама-қарсы қойылғанда не болатынын көрдің бе? Айнада — тағы да айна, ішінде — тағы да айна, шексіздікке дейін. Немесе орыс матрёшкасын ойлап көр — әр қуыршақтың ішінде тағы кішірек, дәл сол секілді, тағы бір қуыршақ бар. Дәл осындай «өзін-өзі қайталау» идеясы программалауда да бар — оны рекурсия деп атайды.
Рекурсия — тек программалауда ғана емес, өнерде де кездеседі: гүлді қырыққабаттың фракталды құрылымында, архитектурадағы қайталанатын бағандарда, тіпті қазақ поэзиясындағы қайырмаларда. Информатикада бұл идея нақты, пайдалы механизмге айналады.
Рекурсия — процедура немесе функцияның ӨЗІН-ӨЗІ шақыруы арқылы есептеу процесін ұйымдастыру тәсілі.
Рекурсияны түсінудің ЕҢ ЖАҚСЫ жолы — факториал есебі. Санның факториалы (n!) дегеніміз — 1-ден n-ге дейінгі барлық санның көбейтіндісі. Бірақ мұнда қызық байқау бар: n! = n × (n−1)! — яғни, n-нің факториалын есептеу үшін (n−1)-дің факториалын білу жеткілікті!
Берілді: n натурал саны (n! = 1×2×...×n, 0!=1).
Неге рекурсия қолданамыз? n! = n·(n−1)! қатынасы функцияны ӨЗІ АРҚЫЛЫ анықтауға мүмкіндік береді — базалық жағдай ретінде n=0 кезінде 1 қайтарамыз.
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)Қалай орындалады? factorial(2) шақырылса:
factorial(2) → 2 * factorial(1)
→ 2 * (1 * factorial(0))
→ 2 * (1 * 1) = 2Жауабы: факториал n! = 1, егер n=0; n! = n·(n−1)!, егер n>0.
Функция өзін-өзі шақырғанда, компьютер «мен қайда тоқтадым, қайда ораламын» дегенді есте сақтауы керек. Мұны компьютер арнайы жад аймағында сақтайды.
Стек (ағылшынша *stack* — байлам) — уақытша деректерді немесе қайтарылатын адрестерді сақтауға арналған арнайы жад аумағы.
Кіріктірілген шақырулардың жалпы саны — рекурсия тереңдігі деп аталады (мыс. factorial(n) үшін дәл n+1 шақыру болады). Егер рекурсия шексіз болса, стек тез толып, программа құлайды.
| Артықшылығы | Кемшілігі |
|---|---|
| Код қарапайым, анық, ықшам болады | Жедел жады үнемді пайдаланылмайды |
| Күрделі есепті «табиғи» түрде сипаттайды | Программаны айтарлықтай баяулатуы мүмкін |
Берілді: Фибоначчи тізбегі — әр келесі мүше алдыңғы екеуінің қосындысына тең: 1, 1, 2, 3, 5, 8, 13, ...
Табу керек: тізбекті N мүшеге дейін рекурсия арқылы шығару.
def Fib(p, q):
global i, n
t = p + q
i += 1
print(t, end=' ')
if i < n:
Fib(q, t)
n = int(input('N='))
x = 1
y = 1
i = 0
print(1, 1, end=' ')
Fib(x, y)Жауабы: N=8 үшін — 1 1 2 3 5 8 13 21 34
Берілді: k саны.
Неге бұл рекурсия? Санның соңғы цифры (n % 10) мен қалған цифрлар (n // 10) арасында қатынас бар — функция «қалған бөлігін» өзі арқылы шешеді.
def sumDig(n):
sum = n % 10
if n >= 10:
sum += sumDig(n // 10)
return sum
k = int(input('k='))
print(sumDig(k))Базалық жағдай: n < 10 болғанда — тек соңғы цифр қайтарылады, рекурсия тоқтайды.
Жауабы: k=56255252125533 үшін — 51.
- Рекурсия — функцияның өзін-өзі шақыруы арқылы есептеу; міндетті түрде тоқтату шарты (базалық жағдай) болуы керек.
- Факториал (n! = n·(n−1)!) — рекурсияның классикалық мысалы.
- Стек — рекурсивті шақырулардың қайтарылатын адрестерін сақтайтын жад; рекурсия тереңдігі — толық шақырулар саны.
- Рекурсия код жазуды ықшамдайды, бірақ жады мен жылдамдық жағынан циклге қарағанда «қымбатырақ».