Page 59 - Программирование. Python. Для школьников. bizdin.kg
P. 59
РЕКУРСИЯ 59
1-маселе. n! саны үчүн факториалды эсептөө мисалында рекурсия кантип
иштээрин карайлы. Мисалы, 3 санынын факториалын эсептөө үчүн, 3*2*1ге
көбөйтүү керек, б.а. n*(n-1)*((n-1)-1) амалын аткаруу керек.
def factorial(n): ЭСИҢЕ ТУТ
if n == 0:
return 1 n санынын факториалы деп, 1ден
else: n ге чейинки бардык натуралдык
return n * factorial(n - 1) сандардын көбөйтүндүсүн айта-
print(factorial(3)) быз:
>>> n!=1*2*3*4*...*n
6 #жыйынтык Мисалы, 5 санын факториалы
120га барабар 120 (5!=1*2*3*4*5).
Рекурсивдүү функциялар програм-
малоодо көптөгөн маселелерди чечишет, бирок тилекке каршы, аларды
жазууда көп учурда каталар кетет. Эң көп таралган ката – бул чексиз ре-
курсия, бул учурда функцияны чакыруу чынжыры эч качан бүтпөйт жана
компьютердин эси толуп калмайынча улана берет.
Көптөгөн чексиз рекурсиянын негизги эки себеби:
1 Рекурсиядан чыгуунун туура эмес жазуусу. Мисалы, эгер биз факто-
риалды эсептөө программасында if n==0 деген текшерүүнү унутуп
2 койсок, анда factorial(0), factorial(-1) ди чакырат, ал болсо factorial(-2)-
1 ни ж.у.с.
3
2 Функциянын параметрлеринин туура эмес жазылышы. Мисалы, эгер
4 factorial(n) функциясы кайрадан эле factorial(n) функциясын чакырса
3 да чексиз чынжыр алынат.
5
Ошондуктан, рекурсивдүү функцияны иштеп чыгууда эң биринчи кезекте
4
рекурсиянын базалык шарты деп аталган рекурсияны аяктоо шартын туура
5
түзүү керек.
Рекурсиянын түз жана тескери жүрүшү
Рекурсиянын кийинки деңгээлине кирүүгө чейин функция тарабынан атка-
рылган аракеттер рекурсиянын түз жүрүшүндө аткарылгандар деп аталат.
Ал эми тереңирээк деңгээлден учурдагы деңгээлге кайткандагы аткарыл-
ган аракеттер – рекурсиянын тескери жүрүшүндөгү аткарылгандар деп
аталат.
www.trk.kg