110. Рекурсивни операции с линейни списъци — дължина
При рекурсия функцията извиква себе си за по-малка задача. Тук непразният списък има първи възел и остатък, който също е списък. Броим първия възел като 1 и прибавяме дължината на остатъка. Празният списък има дължина 0. Това е базовият случай и той приключва извикванията.
При списък с два възела изчислението стига до 1 + (1 + length(nullptr)). Първо се връща 0, после 1 и накрая 2. Стойностите в самите възли могат да са произволни.
Рекурсивни операции в разширената разработка
Самостоятелна задача
Условие
Маршрутът на изложба минава през зали №4, №9 и №7 в този ред. Искаме броя на залите. Всеки възел съдържа номер value и указател next към следващия възел. &first е адресът на първия възел, node->next дава указателя към следващия, а nullptr отбелязва края. Функцията length получава указател към началото на списъка, който брои.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
using namespace std; // Така можем да пишем cout вместо std::cout.
struct Node { // Описваме от какво се състои един възел.
int value; // Тук пазим цяло число за този обект.
Node* next; // Пазим адреса на следващия възел. Node* е указател към възел.
}; // Край на описанието на типа.
int length(Node* node) { // Функцията брои възлите, като започва от подадения адрес.
if (node == nullptr) // Проверяваме дали адресът е празен.
return 0; // Празният остатък от списъка има дължина 0.
return 1 + length(node->next); // Броим текущия възел с 1 и извикваме същата функция за следващия.
} // Край на функцията.
int main() { // Оттук започва изпълнението на програмата.
Node last{7, nullptr}; // Създаваме последния възел с число 7 и без следващ възел.
Node middle{9, &last}; // Създаваме възел с число 9 и го свързваме с последния.
Node first{4, &middle}; // Създаваме възел с число 4 и го свързваме със средния.
cout << length(&first) << '\n'; // Подаваме адреса на първия възел на length и печатаме върнатия брой.
} // Край на програмата.
- Кои възли получават поред извикванията на
lengthи какъв аргумент получава последното? - Кой ред спира рекурсията и каква стойност връща тогава?
- Какви стойности се връщат от последното извикване до първото? Какво извежда
cout? - Ако в рекурсивния ред напишем
length(node)вместоlength(node->next), ще стигнем ли до базовия случай при този маршрут? Защо?
Отговори за самопроверка
1. Аргументи
Поред се подават указатели към first (№4), middle (№9) и last (№7), следвани от nullptr.
2. Базов случай
При node == nullptr се изпълнява return 0; и това извикване приключва.
3. Връщани стойности
Връщат се 0, 1, 2 и 3. Всяко чакащо извикване добавя по едно. cout извежда 3.
4. Същият аргумент
Всяко извикване отново получава указател към №4. За този непразен списък базовият случай остава недостижим.