Рекурсивдүү ойлонуу: Python'догу рекурсия
Маселени өзүнүн кичирейтилген көчүрмөсүн чакырып чечкен функция
- рекурсияга аныктама берип, базалык учур менен рекурсивдүү учурду ажырата билесиз,
- рекурсивдүү чакырууда чакыруу стеги кантип өсүп, кайра ачылганын изилдей аласыз,
- классикалык рекурсияларды жаза аласыз: факториал, Фибоначчи, тизменин суммасы жана каталогдорду кыдыруу,
- рекурсия циклден качан жакшыраак окулаарын, качан цикл коопсузураак экенин чече аласыз,
- Python'дун рекурсия чегин түшүндүрүп, терең рекурсия эмне үчүн
RecursionErrorчыгарарын билесиз.
1. Рекурсия деген эмне
Сиз мурунтан эле башка функцияларды чакырган функцияларды жазасыз. Рекурсия — бул жөн эле өзүн чакырган функция. Бул тегерек сыяктуу угулат, жана ошондой болмок, эгер ар бир чакыруу маселенин кичине бөлүгүндө иштебесе — бөлүк ушунчалык кичине болуп, жооп ачык-айкын болгонго чейин жана жаңы чакыруу керек эместигине чейин.
Өзү аркылуу аныкталган маселени элестетиңиз. «n факториалы — бул n көбөйтүлгөн n - 1 факториалы». Бул сүйлөм чоң маселени (n факториалы) кичине маселе (n - 1 факториалы) аркылуу сүрөттөйт. Рекурсия бул өзүнө шилтеме кылган сүрөттөмөнү түз кодго айландырат.
def factorial(n):
if n == 0: # базалык учур: көбөйтө турган эч нерсе калган жок
return 1
return n * factorial(n - 1) # рекурсивдүү учур: кичине маселе
print(factorial(4)) # 24Акыркы сапта функция өзүнө шилтеме кылат. Цикл жок, бирок ал 4 * 3 * 2 * 1 көбөйтөт. Сыры — ар бир чакыруу өзүнүн көбөйтүүсүн жасоодон мурун кичине чакыруунун бүтүшүн күтөт.