15-маъруза Рекурсив функциялар

• 15-маъруза
• Рекурсив функциялар.
• Мисоллар.

• acm.tuit.uz/forum

• Рекурция

• Функция танасида ўзини ўзи чақирса рекурция дейилади. Рекурция икки хил бўлади:

• acm.tuit.uz/forum

• Оддий – агар функция ўз танасида ўзини чақирса;
• Воситали – агар биринчи функция иккинчи функцияни чақирса, иккинчиси эса ўз навбатида биринчи функцияни чақирса.

• Одатда рекурция математикада кенг қўлланилади. Чунки аксарият математик формулалар рекурсив аниқланади.

• Рекурцияга мисоллар

• Факториални ҳисоблаш формуласи

• Бутун сонни даражасини ҳисоблаш

• Кўриниб турибдики, навбатдаги қийматни ҳисоблаш учун функциянинг “олдинги қиймати” маълум бўлиши керак.

• acm.tuit.uz/forum

• long Faktorial(int n)
• {
• if (!n) return 1;
• else return n * Faktorial (n - 1);
• }

• Факториал ва даража рекурсив ф-ялари

• double Daraja(double x, int n)
• {
• if (!n) return 1;
• else return x * Daraja(x, n - 1);
• }

• Факториал функцияси

• Ҳақиқий сонни даражасини ҳисоблаш ф-яси

• acm.tuit.uz/forum

• Ханой минораси

• Масала. Учта А, В, С қозиқ ва n та ҳар хил ўлчамли халқалар берилган. Халқаларни ўлчамлари ўсиш тартибида 1 дан n гача тартибланган. А қозиқдаги барча халқаларни В қозиққа, ёрдамчи С қозиқдан фойдаланган ҳолда ўтказинг. Халқаларни биттадан кўчириш керак ва катта ўлчамли халқани кичик ўлчамли халқа устига қўйиш мумкин эмас.

• acm.tuit.uz/forum

• int Hanoy (int n, char a = 'A', char b = 'B', char c = 'C' )
• {
• if (n)
• {
• Hanoy(n - 1, a, c, b);
• cout << "Xalqa " << a << " dan " << b << " ga o'tkazilsin\n";
• Hanoy (n - 1, c, b, a);
• }
• }
• int main()
• {
• int Xalqalar_soni;
• cout << "Hanoy minorasi masalasi" << endl;
• cout << "Xalqalar sonini kiriting: ";
• cin>> Xalqalar_soni;
• Hanoy(Xalqalar_soni);
• getch(); return 0;}

• Ханой минораси дастури

• Xalqalar sonini kiriting: 3 ta
• Xalqa A dan B ga o'tkazilsin
• Xalqa A dan C ga o'tkazilsin
• Xalqa B dan C ga o'tkazilsin
• Xalqa A dan B ga o'tkazilsin
• Xalqa C dan A ga o'tkazilsin
• Xalqa C dan B ga o'tkazilsin
• Xalqa A dan B ga o'tkazilsin
• A
• B 3 2 1
• C

• Xalqalar sonini kiriting: 4 ta
• Xalqa A dan C ga o'tkazilsin
• Xalqa A dan B ga o'tkazilsin
• Xalqa C dan B ga o'tkazilsin
• Xalqa A dan C ga o'tkazilsin
• Xalqa B dan A ga o'tkazilsin
• Xalqa B dan C ga o'tkazilsin
• Xalqa A dan C ga o'tkazilsin
• Xalqa A dan B ga o'tkazilsin
• Xalqa C dan B ga o'tkazilsin
• Xalqa C dan A ga o'tkazilsin
• Xalqa B dan A ga o'tkazilsin
• Xalqa C dan B ga o'tkazilsin
• Xalqa A dan C ga o'tkazilsin
• Xalqa A dan B ga o'tkazilsin
• Xalqa C dan B ga o'tkazilsin

• acm.tuit.uz/forum

• Ханой минораси натижалари

• acm.tuit.uz/forum

• Ханой минораси (4 та элемент)

• ЭКУБ функцияси

• #include
• void EKUB(int a, int b)
• {
• if (a > b) a= a - b; else b = b - a; // Kattasidan kichigini ayiramiz
• if (b == 0)
• {
• cout << a; return; // Funksiya ishini tugashi
• }
• EKUB(a, b); // Funksiya o'zini yangi
• // parametrlar bilan chaqiradi
• }
• int main()
• {
• int K, L;
• cin >> K >> L;
• EKUB (K, L);
• getch();
• return 0;
• }

• Рекурсив функция

• Масала. Рекурсив функциядан фойдаланган ҳолда берилган иккита сондан рақамлари йиғиндиси катта бўлган сонни топинг.

• int sum ;
• int raqam(int son)
• {
• sum += son % 10;
• son = son / 10;
• if (son == 0) return sum;
• raqam (son);
• }

• int sum, sum_1, sum_2 ;
• int raqam(int son)
• {
• sum += son % 10;
• son = son / 10;
• if (son == 0) return sum;
• raqam (son);
• }
• int main()
• {
• int sum_1 = 0, sum_2 = 0;
• int son_1, son_2;
• cin>>son_1>>son_2;
• sum_1 = raqam(son_1);
• sum_2 = raqam(son_2);
• if (sum_1 > sum_2) cout << son_1; else cout<
• getch();
• return 0;
• }