Условия всех задач из категории B6
Историческая справка и теоретические сведения
Реку́рсия - процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии.
Термин «рекурсия» используется в различных специальных областях знаний - от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.
С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.
Содержание и мощность рекурсивного определения, а также его главное назначение, состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множество объектов.
Для создания рекурсивных алгоритмов необходимо и достаточно наличие понятия процедуры или функции. Программы, в которых используются рекурсивные процедуры отличаются простотой, наглядностью и компактностью текста.
Смежные определения, имеющие отношение к рекурсии:
максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии;
число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.
Методические указания
Для успешного решения задач из данной категории вы должны:
знать наизусть определение рекурсии;
глубоко понимать формы записи рекурсии (на спуске, на возврате, смешанный вариант);
уметь исследовать предложенный алгоритм, записанный в математической форме и переводить его на "рельсы" алгоритмического языка или языка программирования;
знать, хотя бы один из современных и востребованных языков программирования (например, Pascal, Basic, C, C++, Java, C#);
уметь проводить графическую интерпретацию условия задачи и делать правильные логические умозаключения.
Задача №1
Дано:
алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующим соотношением:
F(1) = F(2) = 1
F(n) = F(n - 1) + F(n - 2), при n > 2.
Вопрос:
чему равно значение функции F(6)?