4.
Рекурсия
Теория
Рекурсией в программировании называется процесс, когда функция (процедура) вызывает сама себя или другие функции и процедуры.
С помощью рекурсии можно сложные процессы представлять через простые.
В математике по рекурсии получаются числа Фибоначчи, каждое число, начиная с третьего, — это сумма двух предыдущих.
Рис. \(1\). Числа Фибоначчи
В компьютерной графике — фрактальная живопись, где каждый следующий элемент связан с предыдущим по определённой формуле.
Рис. \(2\). Фрактальное искусство
Рис. \(3\). Отображение самого себя в зеркале
В программировании также, чтобы организовать рекурсию, нужно, чтобы функция вызвала сама себя.
Пример. Задание как на ЕГЭ
Дан рекурсивный алгоритм на Паскале:
procedure \(F\)(\(n\): integer);
begin
writeln(\(n\));
if \(n\) \(<\) \(6\) then begin
\(F\)(\(n\) \(+\) \(1\));
\(F\)(\(n\) \(+\) \(2\));
end
end;
Чему равна сумма всех чисел, которые будут выведены при вызове \(F\)(\(1\))?
Решение
Разберём решение «вручную». Для этого перепишем программу в систему:
Рис. \(4\). Система
Выполним вычисления:
Сделаем подстановки и получим:
Ответ: \(129\).
С \(2021\) года ЕГЭ по информатике сдают в компьютерном варианте, поэтому для решения задач используют языки программирования; чтобы решить задачу, нужно записать программу на любом знакомом тебе ЯП.
Немного изменим программу, чтобы ответ был выведен сразу, для этого добавим переменную \(s\), которая будет считать сумму всех значений.
В окне вывода будет напечатан результат: \(1\), \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(6\), \(5\), \(6\), \(7\), \(4\), \(5\), \(6\), \(7\), \(6\), \(3\), \(4\), \(5\), \(6\), \(7\), \(6\), \(5\), \(6\), \(7\), \(0\).
Сложим все значения и получим ответ.
Ответ: \(129\).
Источники:
Рис. 1. Числа Фибоначчи. © ЯКласс.
Рис. 2. Фрактальное искусство. Автор: Soler97 - собственная работа, Общественное достояние, https://commons.wikimedia.org/w/index.php?curid=9383777. (Дата обращения: 19.04.2022.)
Рис. 3. Отображение самого себя в зеркале. © ЯКласс.
Рис. 4. Система. © ЯКласс.