04 / РЕКУРЗИВНИ ФУНКЦИИ
Помал проблем.
Иста функција.
Рекурзивна функција се повикува себеси за помал случај од истиот проблем. Секој пример има услов за запирање и чекор што нè приближува до него. Прво се создаваат повиците, а потоа нивните резултати се враќаат наназад. Рекурзијата не е секогаш подобра од циклус: секој активен повик користи простор во магацинот на повици.
Сметка во продавница: рекурзивен збир на цени
Имаме три цени: 120, 80 и 200 денари. Наместо циклус, ја пресметуваме сумата на првите n цени како последната цена плус сумата на претходните n − 1.
01 / ОСНОВЕН СЛУЧАЈКога n е 0, нема производи и функцијата враќа 0.
02 / ПОМАЛ ПРОБЛЕМСекој повик го намалува n за 1. Проблемот станува помал и конечно стигнува до празната низа.
#include <iostream>
long long sumPrices(const int prices[], int n) {
if (n == 0) {
return 0;
}
return prices[n - 1] + sumPrices(prices, n - 1);
}
int main() {
const int prices[] = {120, 80, 200};
const int n = sizeof(prices) / sizeof(prices[0]);
std::cout << sumPrices(prices, n) << '\n';
}
Следи ги повиците.
sumPrices(prices, 3) = 200 + sumPrices(prices, 2)sumPrices(prices, 2) = 80 + sumPrices(prices, 1)sumPrices(prices, 1) = 120 + sumPrices(prices, 0)sumPrices(prices, 0) = 0Враќање: 0 → 120 → 200 → 400
ИЗЛЕЗ ОД ПРОГРАМАТА
Внимавај: Функцијата претпоставува дека n е ненегативен и не ја надминува должината на низата. За празна низа не се чита елемент. Сложеноста е O(n), со O(n) длабочина на повици; за голема низа, циклус е попрактичен.
↗Пробај сам.Додај производ од 50 денари. Пред да ја извршиш програмата, запиши ги повиците и очекуваниот резултат 450.
ПРИМЕР 02 / C++Шифра на производ: рекурзивен збир на цифри
За шифрата 1254 сакаме да го добиеме збирот на цифрите: 1 + 2 + 5 + 4. Ова е едноставна пресметка со шифра, а не безбеден механизам за проверка на идентитет или интегритет.
01 / ОСНОВЕН СЛУЧАЈКога бројот ќе стане 0, нема преостанати цифри и враќаме 0.
02 / ПОМАЛ ПРОБЛЕМn % 10 ја дава последната цифра. n / 10, со целобројно делење, ја отстранува и го намалува проблемот.
#include <iostream>
unsigned int sumDigits(unsigned int n) {
if (n == 0) {
return 0;
}
return n % 10 + sumDigits(n / 10);
}
int main() {
std::cout << sumDigits(1254) << '\n';
}
Следи ги повиците.
sumDigits(1254) = 4 + sumDigits(125)sumDigits(125) = 5 + sumDigits(12)sumDigits(12) = 2 + sumDigits(1)sumDigits(1) = 1 + sumDigits(0)sumDigits(0) = 0Враќање: 0 → 1 → 3 → 8 → 12
ИЗЛЕЗ ОД ПРОГРАМАТА
Внимавај: Примерот работи со ненегативен цел број. Типот unsigned int не е наменет за внес на негативни шифри. Ако се важни почетни нули, шифрата треба да се чува како текст. Бројот на повици расте со бројот на цифрите.
↗Пробај сам.Пресметај sumDigits(9070). Последната нула е валидна цифра, а очекуваниот збир е 16.
ПРИМЕР 03 / C++Магацин: рекурзивно пребарување на подредени шифри
Магацинот има подредени шифри 1001, 1007, 1012, 1050 и 1088. Бараме 1050. Бинарното пребарување проверува средина и ја отфрла половината во која бараната вредност не може да се наоѓа.
01 / ОСНОВЕН СЛУЧАЈАко left е поголемо од right, интервалот е празен и враќаме −1. Ако средниот елемент е бараната шифра, ја враќаме неговата позиција.
02 / ПОМАЛ ПРОБЛЕМПродолжуваме само во левата или десната половина. Границите ја исклучуваат веќе проверената средина, па интервалот строго се намалува.
#include <iostream>
int findCode(const int codes[], int left, int right, int target) {
if (left > right) {
return -1;
}
const int mid = left + (right - left) / 2;
if (codes[mid] == target) {
return mid;
}
if (target < codes[mid]) {
return findCode(codes, left, mid - 1, target);
}
return findCode(codes, mid + 1, right, target);
}
int main() {
const int codes[] = {1001, 1007, 1012, 1050, 1088};
std::cout << findCode(codes, 0, 4, 1050) << '\n';
}
Следи ги повиците.
Интервал [0, 4]: mid = 2, codes[2] = 10121050 е поголемо од 1012 → продолжуваме во [3, 4]Интервал [3, 4]: mid = 3, codes[3] = 1050Шифрата е најдена → враќаме индекс 3
ИЗЛЕЗ ОД ПРОГРАМАТА
Внимавај: Низата мора да биде подредена по растечки редослед, а границите да бидат валидни. Индекс 3 е четвртиот елемент, бидејќи броењето почнува од 0. За отсутна шифра се враќа −1. При дупликати се враќа едно совпаѓање, не нужно првото. Пребарувањето бара O(log n) време и O(log n) длабочина на повици.
↗Пробај сам.Побарај 1060 и следи како интервалот станува празен. Очекуваниот резултат е −1.