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
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.