калинин.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-ресурсы Фильмы Интернет Программное обеспечение Жизнь Благодарности Форум Хронология