Негізгі айырмашылық – Рекурсия мен Итерация
Рекурсия мен Итерацияны бағдарламалау мәселелерін шешу үшін пайдалануға болады. Рекурсия немесе итерация көмегімен мәселені шешу тәсілі мәселені шешу жолына байланысты. Рекурсия мен итерация арасындағы негізгі айырмашылық мынада: рекурсия - бұл бір функциядағы функцияны шақыру механизмі, ал итерация берілген шарт ақиқат болғанша нұсқаулар жинағын қайталап орындау. Рекурсия және Итерация алгоритмдерді әзірлеу және бағдарламалық қосымшаларды құрудың негізгі әдістері болып табылады.
Рекурсия дегеніміз не?
Функция өзін функция ішінде шақырғанда, ол Рекурсия ретінде белгілі. Рекурсияның екі түрі бар. Олар шекті рекурсия және шексіз рекурсия. Ақырғы рекурсияның аяқталу шарты бар. Шексіз рекурсияның аяқтау шарты жоқ.
Рекурсияны факториалды есептеу үшін бағдарлама арқылы түсіндіруге болады.
n!=n(n-1)!, егер n>0
n!=1, егер n=0;
3(3!=321) факториалын есептеу үшін төмендегі кодты қараңыз.
intmain () {
int мәні=факторлық (3);
printf(“Факторлық – %d\n”, мән);
қайтару 0;
}
инфакторлық (inn) {
егер(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 циклінде» цикл ішіндегі операторлар шарт ақиқат болғанша орындалады.
әзірге (шарт){
//мәлімдемелер
}
«do-while» циклінде шарт цикл соңында тексеріледі. Осылайша, цикл кемінде бір рет орындалады.
жасау{
//мәлімдемелер
} while(шарт)
Итерация («for циклі») арқылы 3 (3!) факториалын табуға арналған бағдарлама төмендегідей.
int main(){
intn=3, факториалды=1;
inti;
үшін(i=1; i<=n; i++){
факторлық=факторлықi;
}
printf(“Факторлық – %d\n”, факториалды);
қайтару 0;
}
Рекурсия мен итерацияның қандай ұқсастықтары бар?
- Екеуі де мәселені шешудің әдістері.
- Тапсырманы рекурсияда немесе итерацияда шешуге болады.
Рекурсия мен итерацияның айырмашылығы неде?
Рекурсия және Итерация |
|
| Рекурсия – бір функция ішіндегі функцияны шақыру әдісі. | Итерация – берілген шарт дұрыс болғанша қайталанатын нұсқаулар блогы. |
| Ғарыштық күрделілік | |
| Рекурсивті бағдарламалардың кеңістік күрделілігі итерациялардан жоғары. | Ғарыш күрделілігі итерацияларда азырақ. |
| Жылдам | |
| Рекурсияның орындалуы баяу. | Әдетте итерация рекурсияға қарағанда жылдамырақ. |
| Жағдай | |
| Аяқтау шарты болмаса, шексіз рекурсия болуы мүмкін. | Егер шарт ешқашан жалған болмаса, ол шексіз итерация болады. |
| Стек | |
| Рекурсияда стек функция шақырылған кезде жергілікті айнымалы мәндерді сақтау үшін пайдаланылады. | Итерацияда стек пайдаланылмайды. |
| Кодты оқу мүмкіндігі | |
| Рекурсивті бағдарлама оқуға ыңғайлы. | Итеративті бағдарламаны оқу рекурсивті бағдарламаға қарағанда қиынырақ. |
Қорытынды – Рекурсия және Итерация
Бұл мақала рекурсия мен итерация арасындағы айырмашылықты талқылады. Екеуі де бағдарламалау мәселелерін шешу үшін пайдаланылуы мүмкін. Рекурсия мен итерацияның айырмашылығы мынада: рекурсия - бұл бір функцияның ішіндегі функцияны шақыру және берілген шарт ақиқат болғанша нұсқаулар жинағын қайталап орындау үшін оны қайталау механизмі. Егер мәселені рекурсивті түрде шешуге болатын болса, оны қайталау арқылы да шешуге болады.
Рекурсия мен Итерацияның PDF нұсқасын жүктеп алу
Сіз осы мақаланың PDF нұсқасын жүктеп алып, сілтеме жазбасына сәйкес офлайн мақсаттарда пайдалана аласыз. PDF нұсқасын мына жерден жүктеп алыңыз Рекурсия мен итерация арасындағы айырмашылық
