База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

Рекурсия

Рекурсията означава функцията да извиква сама себе си, пряко или чрез други функции. За да завърши изчислението, са нужни достижим базов случай и рекурсивни стъпки, които напредват към него.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

ReturnType function(Parameters) {
    if (base_condition) return base_value;
    return combine(function(smaller_arguments));
}

Рекурсията (recursion) е техника, при която функция извиква сама себе си пряко или непряко чрез други функции. Не е необходима специална ключова дума: използва се обичайният синтаксис за извикване на функция. C++ позволява рекурсивни извиквания, но main не бива да се извиква рекурсивно.

Типичният алгоритъм има базов случай, който връща резултат без следващо извикване, и рекурсивна стъпка, която намалява задачата. За входни данни, при които изчислението трябва да завърши, всяка верига от извиквания трябва да достигне базов случай. Наличието само на условие за спиране не е достатъчно, ако аргументите никога не го удовлетворяват.

В примера sum_to(5) изчислява сумата от 1 до 5 включително. Извикванията намаляват n, докато достигне 0; при последователните връщания след това се събират чакащите стойности и резултатът е 15. Всяко извикване има собствен параметър n; това не е една обща променлива. При n <= 0 функцията връща 0.

Не приемай примера за решение при произволно големи входни данни: дълбоката рекурсия може да изчерпи ресурсите за изпълнение, а сума извън диапазона на int води до недефинирано поведение. За големи входни данни обмисли цикъл и проверки на диапазона. Посоченият източник е развиващ се проект на стандарт, а не окончателна публикация на C++23; примерът използва синтаксис, съвместим с C++23.

Примери

#include <iostream>

int sum_to(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(5) << '\n';
}

Резултат

15

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници