Негизги айырма – Рекурсия менен Итерация
Рекурсия жана Итерация программалоо маселелерин чечүү үчүн колдонулушу мүмкүн. Рекурсия же итерацияны колдонуу менен маселени чечүүнүн ыкмасы маселени чечүүнүн жолуна жараша болот. Рекурсия менен итерациянын ортосундагы негизги айырма, рекурсия - бул бир эле функциянын ичиндеги функцияны чакыруу механизми, ал эми итерация берилген шарт чын болгонго чейин нускамалардын топтомун кайра-кайра аткаруу. Рекурсия жана Итерация алгоритмдерди иштеп чыгуунун жана программалык тиркемелерди куруунун негизги ыкмалары болуп саналат.
Рекурсия деген эмне?
Функция өзүн функциянын ичинде чакырганда, ал Рекурсия деп аталат. Рекурсиянын эки түрү бар. Алар чектүү рекурсия жана чексиз рекурсия. Чектүү рекурсиянын аяктоочу шарты бар. Чексиз рекурсиянын токтотуу шарты жок.
Рекурсияны факториалдарды эсептөө үчүн программанын жардамы менен түшүндүрсө болот.
n!=n(n-1)!, эгерде n>0
n!=1, эгерде n=0;
3(3!=321) факториалын эсептөө үчүн төмөнкү кодду караңыз.
intmain () {
int мааниси=факториялык (3);
printf(“Факториал %d\n”, маани);
кайтаруу 0;
}
инфактордук (интн) {
эгерде(n==0) {
кайтаруу 1;
}
башка {
кайтаруу n фактордук(n-1);
}
}
Факториалды (3) чакырганда, ал функция фактордук (2) чакырат. Факториалды (2) чакырганда, ал функция фактордук (1) чакырат. Ошондо фактордук (1) фактордук (0) чакырат. фактордук (0) 1 кайтарат. Жогорудагы программада, “if блокундагы” n==0 шарт базалык шарт болуп саналат. Ошо сыяктуу эле, фактордук функция кайра-кайра чакырылат.
Рекурсивдүү функциялар стек менен байланыштуу. Си тилинде негизги программа көптөгөн функцияларды аткарышы мүмкүн. Ошентип, main () чакыруучу функция, ал эми негизги программа тарабынан чакырылган функция чакырылган функция. Функция чакырылганда, башкаруу чакырылган функцияга берилет. Функциянын аткарылышы аяктагандан кийин башкаруу негизгиге кайтарылат. Андан кийин негизги программа уланат. Ошентип, ал аткарууну улантуу үчүн активдештирүү жазуусун же стек кадрын түзөт.
01-сүрөт: Рекурсия
Жогорудагы программада негизгиден фактордук (3) чалуу учурунда ал чалуу стекинде активдештирүү жазуусун түзөт. Андан кийин стектин үстүндө фактордук (2) стек алкагы түзүлөт жана башкалар. Активдөө жазуусу локалдык өзгөрмөлөр ж.б. жөнүндө маалыматты сактайт. Функция чакырылган сайын, стектин үстүндө локалдык өзгөрмөлөрдүн жаңы топтому түзүлөт. Бул стек алкактары ылдамдыгын жайлатышы мүмкүн. Ошол сыяктуу эле, рекурсияда функция өзүн чакырат. Рекурсивдүү функция үчүн убакыттын татаалдыгы канча жолу табылат, функция чакырылат. Бир функцияны чакыруу үчүн убакыттын татаалдыгы O(1). Рекурсивдүү чалуулардын n саны үчүн убакыттын татаалдыгы O(n).
Итерация деген эмне?
Итерация – бул берилген шарт туура болгонго чейин кайра-кайра кайталануучу нускамалар блогу. Итерацияга "for loop", "do-while цикли" же "while цикли" аркылуу жетсе болот. “for loop” синтаксиси төмөнкүдөй.
үчүн (инициализация; шарт; өзгөртүү) {
// билдирүүлөр;
}
02-сүрөт: “үчүн циклдин агымынын диаграммасы”
Инициалдаштыруу кадамы биринчи аткарылат. Бул кадам цикл башкаруу өзгөрмөлөрүн жарыялоо жана инициализациялоо болуп саналат. Эгер шарт чын болсо, тармал кашаанын ичиндеги билдирмелер аткарылат. Бул билдирүүлөр шарт чын болгонго чейин аткарылат. Шарт туура эмес болсо, башкаруу "for циклинен" кийинки билдирүүгө өтөт. Цикл ичиндеги операторлор аткарылгандан кийин башкаруу бөлүгү өзгөртүүгө өтөт. Бул цикл башкаруу өзгөрмөсүн жаңыртуу. Андан кийин абалы дагы бир жолу текшерилет. Эгер шарт чын болсо, тармал кашаанын ичиндеги билдирүүлөр аткарылат. Ошентип "for цикли" кайталанат.
"while циклинде" цикл ичиндеги операторлор шарт чын болгонго чейин аткарылат.
while (шарт){
//билдирүүлөр
}
“do-while” циклинде шарт циклдин аягында текшерилет. Ошентип, цикл жок дегенде бир жолу аткарылат.
до{
//билдирүүлөр
} азырынча(шарт)
Итерация («for цикл») аркылуу 3 (3!) факториалын табуу программасы төмөнкүдөй.
int main(){
intn=3, фактордук=1;
inti;
for(i=1; i<=n; i++){
факториялык=фактордукi;
}
printf(“Факториалдык %d\n”, факториалдык);
кайтаруу 0;
}
Рекурсия менен Итерациянын кандай окшоштуктары бар?
- Экөө тең көйгөйдү чечүүнүн ыкмалары.
- Тапшырма рекурсияда же итерацияда чечилиши мүмкүн.
Рекурсия менен Итерациянын ортосунда кандай айырма бар?
Рекурсия жана Итерация |
|
| Рекурсия – бир эле функциянын ичиндеги функцияны чакыруу ыкмасы. | Итерация – бул берилген шарт чын болгонго чейин кайталануучу нускамалардын блогу. |
| Космостук татаалдык | |
| Рекурсивдүү программалардын мейкиндик татаалдыгы итерациялардан жогору. | Космостук татаалдык итерацияларда азыраак. |
| Ылдамдык | |
| Рекурсиянын аткарылышы жай. | Адатта, итерация рекурсияга караганда тезирээк болот. |
| Шарт | |
| Эгер токтотуу шарты болбосо, чексиз рекурсия болушу мүмкүн. | Эгер шарт эч качан жалган болбосо, ал чексиз итерация болот. |
| Стек | |
| Рекурсияда стек функция чакырылганда локалдык өзгөрмөлөрдү сактоо үчүн колдонулат. | Итерацияда стек колдонулбайт. |
| Коддун окулушу | |
| Рекурсивдүү программа окууга ыңгайлуу. | Итеративдик программаны окуу рекурсивдүү программага караганда кыйыныраак. |
Кыскача – Рекурсия жана Итерация
Бул макалада рекурсия менен итерациянын ортосундагы айырма талкууланган. Экөө тең программалоо маселелерин чечүү үчүн колдонулушу мүмкүн. Рекурсия менен итерациянын айырмасы, рекурсия – бул бир эле функциянын ичиндеги функцияны чакыруу механизми жана берилген шарт чын болгонго чейин нускамалардын топтомун кайра-кайра аткаруу үчүн аны кайталоо. Эгер көйгөй рекурсивдүү түрдө чечилсе, аны кайталоо аркылуу да чечсе болот.
Рекурсиянын жана Итерациянын PDF версиясын жүктөп алыңыз
Сиз бул макаланын PDF версиясын жүктөп алып, шилтеме эскертүүсүнө ылайык оффлайн максаттарында колдоно аласыз. Сураныч, PDF версиясын бул жерден жүктөп алыңыз Рекурсия менен Итерациянын айырмасы
