Rambler's Top100 Service калинин.ru / программирование / алгоритмы /  << 11.09.00 >>

Рекурсия, часть II

Собственно, в своей прошлой заметке я рассказал немного не о том, о чем хотел. Поэтому сегодня придется дополнять ;)

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

И в этом нет ничего смешного. Дать определение алгоритма очень сложно. Потому что то, например, что традиционно проговаривают детям в школе на уроках информатики, определением не является. Там обычно говорят примерно следующее: алгоритм это последовательность элементарных действий и т.д. В то же самое время, если придираться, остается вопрос: а какое действие считать элементарным? И насколько верно то, что ЛЮБАЯ последовательность будет алгоритмом?

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

Давать эти формальные определения я не буду (желающие могут обратиться к специальной литературе). Кстати, мое нежелание конкретизировать вызвано прежде всего тем, что я, со своим "неформальным" объяснением на пальцах формальных вопросов, могу скорее запутать читателя, чем что-то ему объяснить. Так что для меня главным является упомянуть, а если кого-то это заинтересовало, то он запросто сможет посмотреть это и без меня в более академическом изложении.

Надо отметить, что кроме рекурсивных функций, для определения алгоритмов могут быть использованы и другие подходы, например, машина Тьюринга и нормальные алгоритмы Маркова.

Машина Тьюринга, наверно, является самым популярным формальным определением алгоритма (но, вполне возможно что и не самым удачным), на основании которой построена модель машины Фон-Неймана. А на ней основаны практически все современные императивные языки программирования и компьютерные архитектуры. Так что практическая ценность у формальных определений алгоритмов имеется --- программируя на Delphi вы работаете с многоленточной машиной Тьюринга ;)

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

Очень часто утверждается, что функциональные языки программирования значительно лучше усваиваются школьниками, чем императивные (потому что рекурсия логичнее цикла и лучше, если она вводится сначала, а потом циклы как частный случай рекурсии). На мой взгляд это немного неверно: лучше усваивается не какая-то конкретная тема, а то, что лучше объясняют. Практика показывает, что среди школьных учителей информатики крайне редко встречаются люди, которые действительно знают свой предмет хотя бы на "студенческом" (я имею в виду студента нормального технического ВУЗа) уровне. Поэтому и рассказать ничего не могут, так что тут дело не в языке программирования.

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

Резюме

Термин рекурсия очень важен не только потому, что использование рекурсивных функций в своих программах должно сопровождаться глубокими размышлениями на тему "а что будет, если". На рекурсии может быть построена вообще вся теория алгоритмов...


Версия для печати


  Ссылки по теме:
/comment/books/11_07_00.shtml
   Программирование: теоремы и задачи.
/comment/books/08_09_00.shtml
   Искусство программирования.
Р. Грэхем, Д. Кнут, О.Паташник
   Конкретная математика (основание информатики).
  Рядом в разделе:
Полный перебор (11.11.00)
   Зачастую, когда говорят о качестве решения некоторой задачи, для того что бы определить наихудший вариант, приводят пример "полного перебора". Сколько раз...   >>>>
Рекурсия (04.09.00)
   Возможно для кого-то это будет удивительным, но наиболее известным алгоритмом является сортировка пузырьком (не то, что бы ее все знали, просто...   >>>>
  Рядом по дате:
volatile (12.09.00)
   И опять я публикую здесь текст из конференции SU.C_CPP. Впору заводить для этого отдельный раздел ;) Автор этого письма, Александр Кротов,...   >>>>
Пакет шрифтов Cyr-RFX (10.09.00)
   Руссификация X11 стала в последнее время достаточно простой. Для этого достаточно указать X-серверу то, что он находится в России и попросить...   >>>>
  Содержание:
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
   C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Просто так
Студенческое
Туризм
  Байки
Фотографии
Комментарии
   Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Благодарности
Форум
Хронология
 
  В этом разделе:
Полный перебор (11.11.00)
   Зачастую, когда говорят о качестве решения некоторой задачи, для того что бы определить наихудший вариант, приводят пример "полного перебора". Сколько раз...   >>>>
Рекурсия, часть II (11.09.00)
   Собственно, в своей я рассказал немного не о том, о чем хотел. Поэтому сегодня придется дополнять ;) Кроме того, что рекурсия...   >>>>
Рекурсия (04.09.00)
   Возможно для кого-то это будет удивительным, но наиболее известным алгоритмом является сортировка пузырьком (не то, что бы ее все знали, просто...   >>>>
Использование конечных автоматов (21.08.00)
   Я не хочу давать формальных определений, цель этой заметки --- показать "на пальцах" использование конечных автоматов (КА) для решения различных задач...   >>>>
Содержание раздела полностью...
   Примерно в тоже время
volatile (12.09.00)
   И опять я публикую здесь текст из конференции SU.C_CPP. Впору заводить для этого отдельный раздел ;) Автор этого письма, Александр Кротов,...   >>>>
Пакет шрифтов Cyr-RFX (10.09.00)
   Руссификация X11 стала в последнее время достаточно простой. Для этого достаточно указать X-серверу то, что он находится в России и попросить...   >>>>
Хронология полностью...
   Содержание
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
  C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Туризм
  Байки
Фотографии
Комментарии
  Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Студенческое
Просто так
Благодарности
Форум
Хронология
© 2000-2008, Andrey L. Kalinin
mailto:andrey@kalinin.ru
Rambler's Top100