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 и печатаме върнатия брой.
}                                    // Край на програмата.
  1. Кои възли получават поред извикванията на length и какъв аргумент получава последното?
  2. Кой ред спира рекурсията и каква стойност връща тогава?
  3. Какви стойности се връщат от последното извикване до първото? Какво извежда cout?
  4. Ако в рекурсивния ред напишем 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. За този непразен списък базовият случай остава недостижим.

Изтегли main.cpp.