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

11.09.00

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

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

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

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

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

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

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

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

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

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

Резюме

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

Ссылки по теме