 |
Образовательный журнал для старшеклассников и учителей |
| |
Образовательный журнал для старшеклассников и учителей |
| << К разделам |
| Информатика |
| Алгоритмы |
| Теория информации |
| Теория программирования |
| Все статьи |
| Журнал |
| Подписка |
Интернет-Журнал «Потенциал»  |
| Авторам |
| Печатные номера |
|
Адрес редакции: 109544, г. Москва, ул. Рабочая, 84, редакция журнала "Потенциал". Телефоны: 787-24-94, 787-24-95, 678-35-86 E-mail: potential@potential.org.ru Главный редактор А.Д. Гладун Шеф-редактор Г.А. Четин Подробная информация Свидетельство о регистрации— СМИ ПИ № ФС 77-19521. Издаётся с января 2005 года. Тираж — 4000 экз, периодичность выхода — раз в месяц Печать — ООО "Азбука-2000" Журнал издаётся на средства выпускников технических вузов ISSN 1814-6422 |
| Полезные сайты |
|
ЗФТШ
|
|
МЦНМО
|
|
Журнал "Квант"
|
|
"Открытый Колледж"
|
|
Союз образовательных сайтов
|
|
Интернет-портал "Абитуриент"
|
| Другие ссылки... |
|
 | Пупышев Вячеслав Викторович - старший преподаватель кафедры математического обеспечения ЭВМ Удмуртского государственного университета. |
Рекурсия — это жемчужина теории алгоритмов. Это первое, с чем знакомят школьников, после того, как они овладеют процедурами ввода и вывода данных, элементарными арифметическими операциями, оператором цикла и условного оператора. Простота рекурсии обманчива. Она таит в себе множество ловушек и сложных моментов, но и преподносит много подарков.
Давно известен такой математический приём, как сведение задачи к нескольким более простым. Затем простые задачи можно снова свести к ещё более простым и так далее, пока не доберёмся до самых элементарных задач.
Представьте, что нужно пройти 1000 шагов. Для решения этой задачи вы делаете один шаг, и остаётся 999 шагов. Таким образом, задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи - сделать один шаг. Конечно, этот пример слишком прост. Далее мы рассмотрим несколько более сложных примеров, поясняющих идею рекурсии и демонстрирующих её хорошие и плохие стороны.
Прежде всего важно заметить аналогию рекурсии с понятием математической индукции. У рекурсии так же как и в методе математической индукции есть - аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии - способ сведения данной задачи к более простым задачам
(тем, которые мы уже умеем решать).
Продолжение смотрите здесь
