Теория:
Рекурсией в программировании называется процесс, когда функция (процедура) вызывает сама себя или другие функции и процедуры.
С помощью рекурсии можно сложные процессы представлять через простые.
В математике по рекурсии получаются числа Фибоначчи, каждое число, начиная с третьего, — это сумма двух предыдущих.
Рис. \(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\), которая будет считать сумму всех значений.
var \(s\): integer;
procedure \(F\)(\(n\): integer);
begin
writeln(\(n\));
if \(n\) \(<6\) then begin \(F\)(\(n\) \(+\) \(1\));
\(F\)(\(n\) \(+\) \(2\));
end
end;
begin
\(s\): \(=0\);
\(F\)(\(1\));
writeln(\(s\));
end.
В окне вывода будет напечатан результат: \(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. Система. © ЯКласс.