Рекурсия

Функция ошол эле маселенин кичине версиясын чечиш үчүн өзүн-өзү чакырганда

Негизги идея: Рекурсия — бул функция өзүн-өзү чакырганда. Ар бир чакыруу бир аз кичирээк маселенин үстүндө иштейт, ал эми маселе жообу түшүнүктүү болгонго чейин кичирейет. Андан кийин бардык кичине жооптор акыркы натыйжага кайра биригет.

Аягында сиз төмөнкүлөрдү жасай аласыз:

рекурсивдик функция деген эмне экенин түшүндүрүү,
базалык учурду рекурсивдик учурдан айырмалоо,
чакыруу стеги кантип өсүп, анан жыйналарын байкоо,
факториал жана Фибоначчи сыяктуу классикалык мисалдарды окуу,
рекурсия качан циклден түшүнүктүү экенин чечүү.

1. Рекурсия деген эмне?

Матрёшка куурчактарынын топтомун элестетиңиз. Чоң куурчакты ачасыз, ичинен кичирээгин табасыз. Аны ачасыз — дагы кичирээгин табасыз. Таптакыр ачылбаган эң кичине куурчакка жеткенче улантасыз. Ошол акыркы куурчак — сиз токтой турган жер.

Рекурсия ушундай эле иштейт. Рекурсивдик функция маселенин кичине бөлүгүнүн үстүндө өзүн-өзү чакыра берет. Ачылбаган эң кичине матрёшка сыяктуу, анын өзүн чакырууну токтото турган учуру болушу керек. Ошол токтоо чекити болбосо, ал түбөлүккө иштемек.

C++ функциялары темасында сиз функция башка функцияны чакыра аларын үйрөндүңүз. Мына таң калычтуусу: функцияга өзүн-өзү чакырууга уруксат. Рекурсия ушул гана.

Рекурсивдик чечимдин эки милдети бар: качан токтоону билүү жана токтоого бара жатып маселени кантип кичирейтүүнү билүү.

2. Базалык учур жана рекурсивдик учур

Ар бир жакшы рекурсивдик функцияда так эки бөлүк болот:

Базалык учур — бул эң жөнөкөй маселе, өзүн кайра чакырбай эле дароо жооп бере турган. Бул эң кичине матрёшка. Ал рекурсияны токтотот.
Рекурсивдик учур — бул функция өзүн кичирээк маселенин үстүндө чакырып, ошол жоопту өзүнүкүн курууга колдонгон жер.

Сандан нөлгө чейин артка саноону карап көрөлү:

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n < 0) {          // БАЗАЛЫК УЧУР: жасай турган эч нерсе калган жок
        return;
    }
    cout << n << " ";     // бир аз иш
    countdown(n - 1);     // РЕКУРСИВДИК УЧУР: кичирээк маселе
}

int main() {
    countdown(3);
    return 0;
}

Күтүлгөн натыйжа:

3 2 1 0

Ар бир чакыруу n - 1 берерин байкаңыз. Сан кичирейе берет: 3, анан 2, анан 1, анан 0, анан -1. Ал акыры -1ге жеткенде базалык учур return; иштеп, чакыруулар чынжыры токтойт.

Базалык учурду унутуп калсаңыз, функция өзүн чакырууну эч качан токтотпойт. Бул чексиз рекурсия деп аталат жана программа стектин ашып кетүүсү менен кулайт.

Рекурсия