Функции в других языках программирования
Рекурсия
Практическая работа №22 «Функции»
Практическая работа №23 «Функции-2»
Вы уже знакомы с рекурсивными процедурами, которые вызывают сами себя. Функции тоже могут быть рекурсивными, в некоторых случаях это позволяет записать решение задачи намного проще.
Рекурсивная функция — это функция, которая вызывает сама себя.
Вернёмся к задаче вычисления суммы цифр числа. Можно сформулировать алгоритм её решения так: сумма цифр числа N равна значению последней цифры плюс сумма цифр числа, полученного отбрасыванием последней цифры.
Вход: натуральное число N.
Шаг 1: d := mod (N,10)
Шаг 2: М := div (N, 10)
Шаг 3: s : = сумма цифр числа М
Шаг 4: sum := s + d
Результат: sum.
Итак, для того чтобы найти сумму цифр числа, нужно сложить его последнюю цифру и сумму цифр другого числа, т. е. выполнить тот же самый алгоритм, только с другими исходными данными (эта строка в записи алгоритма выделена фоном). Получился рекурсивный алгоритм, в программе его можно записать в виде рекурсивной функции:
Изучите текст функции и ответьте на вопросы.
— Зачем добавлен условный оператор с условием N=0?
— Что произойдёт, если удалить этот условный оператор?
— Как можно доказать, что для любого целого числа рекурсия обязательно закончится?
В рекурсивном варианте функции исчез цикл, поэтому можно сделать вывод: рекурсия может заменить цикл. Верно и обратное: любую рекурсивную функцию можно записать без рекурсии, с помощью циклов. Решение с помощью цикла (оно называется итерационным) обычно работает быстрее, чем рекурсивное, и требует меньше памяти. Однако рекурсивное решение очень часто короче и проще для понимания.
Используя дополнительные источники, выясните, что означает слово «итерация». От какого слова оно произошло?
Следующая страница Выводы