(курс 68 ч.) §25. Функции | Рекурсия (informatika_09_68_pol) (68 часов в уч. год)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, углубленный уровень)


Уроки 43 - 44
§25. Функции



Содержание урока

Что такое функция?

Функции в других языках программирования

Примеры функций

Логические функции

Рекурсия

Выводы

Вопросы и задания

Практическая работа №22 «Функции»

Практическая работа №23 «Функции-2»


Рекурсия


Вы уже знакомы с рекурсивными процедурами, которые вызывают сами себя. Функции тоже могут быть рекурсивными, в некоторых случаях это позволяет записать решение задачи намного проще.

Рекурсивная функция — это функция, которая вызывает сама себя.

Вернёмся к задаче вычисления суммы цифр числа. Можно сформулировать алгоритм её решения так: сумма цифр числа N равна значению последней цифры плюс сумма цифр числа, полученного отбрасыванием последней цифры.

Вход: натуральное число N.

Шаг 1: d := mod (N,10)

Шаг 2: М := div (N, 10)

Шаг 3: s : = сумма цифр числа М

Шаг 4: sum := s + d

Результат: sum.


Итак, для того чтобы найти сумму цифр числа, нужно сложить его последнюю цифру и сумму цифр другого числа, т. е. выполнить тот же самый алгоритм, только с другими исходными данными (эта строка в записи алгоритма выделена фоном). Получился рекурсивный алгоритм, в программе его можно записать в виде рекурсивной функции:

Изучите текст функции и ответьте на вопросы.

— Зачем добавлен условный оператор с условием N=0?
— Что произойдёт, если удалить этот условный оператор?
— Как можно доказать, что для любого целого числа рекурсия обязательно закончится?

В рекурсивном варианте функции исчез цикл, поэтому можно сделать вывод: рекурсия может заменить цикл. Верно и обратное: любую рекурсивную функцию можно записать без рекурсии, с помощью циклов. Решение с помощью цикла (оно называется итерационным) обычно работает быстрее, чем рекурсивное, и требует меньше памяти. Однако рекурсивное решение очень часто короче и проще для понимания.

Используя дополнительные источники, выясните, что означает слово «итерация». От какого слова оно произошло?



Следующая страница Выводы



Cкачать материалы урока







Наверх