Перейти до змісту

ЛР17. Рекурсія і стек викликів

Коротко про роботу

Рекурсивна функція підсумовує суфікс послідовності, переходячи до наступного індексу. Варіант визначає STUDENT_X.

Відкрити робочий зошит Як виконувати лабораторні

1. Умова

Рекурсивна функція підсумовує суфікс послідовності, переходячи до наступного індексу.

Усі обчислення виконуйте з даними свого STUDENT_X. Значення варіанта друкує перша комірка зошита.

2. Що треба знати

Робота виконується після Л1–Л8. Потрібні поняття:

  1. рекурсія
  2. базовий випадок
  3. стек викликів
  4. повернення результату

Межа матеріалу

Використовуйте поняття, вивчені до Л1–Л8. Не копіюйте суфікс на кожному виклику. Передавайте послідовність і змінюйте індекс.

3. Варіант, вхідні дані та результат

У зошиті заповніть STUDENT_NAME, STUDENT_GROUP і STUDENT_X від 1 до 30.

Вхідні дані

Поле Зміст
values послідовність
start_index початок суфікса

Поля результату

Поле Зміст
sum_result сума суфікса
call_count кількість викликів разом із базовим випадком
max_depth максимальна кількість активних викликів

Назви полів результату не змінюйте.

4. Терміни і правила

Терміни

  • базовий випадок — вхід, для якого рекурсивна функція повертає результат без нового рекурсивного виклику.
  • стек викликів — ланцюжок активних викликів функцій, які ще не завершилися.

Правила

  1. Рекурсивна функція отримує values і поточний індекс.
  2. Базовий випадок настає, коли індекс дорівнює values.size(); цей виклик також входить до call_count.
  3. sum_result — сума елементів від start_index до кінця послідовності.
  4. max_depth — найбільша кількість одночасно активних викликів, включно з кадр базового випадку.

5. Завдання

Завдання 1

Для короткого прикладу запишіть послідовність рекурсивних викликів, їхню глибину та повернені значення.

Завдання 2

Реалізуйте рекурсивну суму від start_index до кінця values. Результат запишіть у sum_result.

Завдання 3

Порахуйте всі виклики у call_count і найбільшу глибину у max_depth.

6. Перевірка і здача

  1. Запустіть самоперевірку та виправте помилки.
  2. Перезапустіть ядро і виконайте роботу ще раз від початку.
  3. Збережіть .ipynb і PDF з кодом та результатами.

Назва PDF: LR17_Прізвище_Група_VNN.pdf.