Смысловая составляющая осталась прежней. Вступление. Возможно, у этой системы найдутся приложения не тольков роли логического исчисления. Это такая теоретическая штука, изучение которой необходимо, когда вы собираетесь заняться исследованием систем типов или хотите создать свой функциональный язык программирования. Тем не менее, если у вас есть желание разобраться в том, что лежит в основе Haskell, ML и им подобных, сдвинуть точку сборки на написание кода или просто расширить свой кругозор, то прошу под кат. Начнм мы с традиционного но краткого экскурса в историю. В 3. 0 х годах прошлого века перед математиками встала так называемая проблема разрешения Entscheidungsproblem, сформулированная Давидом Гильбертом. Суть е в том, что вот есть у нас некий формальный язык, на котором можно написать какое либо утверждение. Клуб программистов Весельчак У. Статья Заметки о рекурсии. Я имею в виду, конечно, Нассима Талеба и историю никому не известной писательницы из второй главы Черного лебедя. В связи с накладными расходами полезно знать, есть ли у рекурсивной. Читать middot Текущая версия middot Править middot Править викитекст middot История. Начнм мы с традиционного но краткого экскурса в историю. Читать middot Править middot Править викитекст middot История. Существует ли алгоритм, за конечное число шагов определяющий его истинность или ложность Ответ был найден двумя великими учными того времени Алонзо Чрчем и Аланом Тьюрингом. YFJghQXa7AOf1vm5KwfqB6p4luPgpdnIl_go-dBbqAr7-SexpbFbS7YTjFEm5R74=h310' alt='История Рекурсии' title='История Рекурсии' />Они показали первый с помощью изобретнного им. Entscheidungsproblem в общем случае неразрешима. Так лямбда исчисление впервые громко заявило о себе, но ещ пару десятков лет продолжало быть достоянием математической логики. Пока в середине 6. Питер Ландин не отметил, что сложный язык программирования проще изучать, сформулировав его ядро в виде небольшого базового исчисления, выражающего самые существенные механизмы языка и дополненного набором удобных производных форм, поведение которых можно выразить путем перевода на язык базового исчисления. В качестве такой основы Ландин использовал лямбда исчисление Чрча. И вс заверте. В нм нет встроенных констант, элементарных операторов, чисел, арифметических операций, условных выражений, циклов и т. Потому что лямбда исчисление это не язык программирования, а формальный аппарат, способный определить в своих терминах любую языковую конструкцию или алгоритм. В этом смысле оно созвучно машине Тьюринга, только соответствует функциональной парадигме, а не императивной. Мы с вами рассмотрим его наиболее простую форму чистое нетипизированное лямбда исчисление, и вот что конкретно будет в нашем распоряжении. У хорошей, годной рекурсии должно быть и условие для выхода из рекурсии, иначе получается зацикливание. Типичным примером функций. Открытие первого чрного лебедя было большим сюрпризом для орнитологов, но главное, по словам Талеба, в истории не это. Ниже речь пойдт о старушке рекурсии, которую неплохо бы представлять, понимать и применять. Примечание Данная небольшая. Лига образования middot The Simpsons Симпсоны middot Истории из жизни middot Книжная лига middot Лига Юристов middot Лига Сисадминов middot Бизнес middot Лига путешественников. Термы переменная xлямбда абстракция анонимная функция. Действительно, в мире чистого лямбда исчисления возвращаемое функцией значение тоже может быть функцией. Следовательно, мы можем применить первоначальную функцию только к одному е аргументу, заморозив прочие. В результате получим новую функцию от хвоста аргументов, к которой применим предыдущее рассуждение. Такая операция называется каррированием в честь того самого Хаскелла Карри. Выглядеть это будет примерно так f. Преобразование закончено. Переменная x называется связанной, если она находится в теле t. Если же x не связана какой либо вышележащей абстракцией, то е называют свободной. Например, вхождения x в x y и. Если все переменные в терме связаны, то его называют замкнутым, или комбинатором. Мы с вами будем использовать следующий простейший комбинатор функцию тождества id. Она не выполняет никаких действий, а просто возвращает без изменений свой аргумент. Процесс вычисления. Рассмотрим следующий терм применение. Каждый шаг вычисления будет заключаться в замене всех вхождений переменной x внутри t на y. Терм применение такого вида носит имя редекса от reducible expression, redex сокращаемое выражение, а операция переписывания редекса в соответствии с указанным правилом называется бета редукцией. Существует несколько стратегий выбора редекса для очередного шага вычисления. Рассматривать их мы будем на примере следующего терма. В этом случае каждый раз редекс внутри вычисляемого терма выбирается произвольным образом. Первым всегда сокращается самый левый, самый внешний редекс. Вызов по имени. Порядок вычислений в этой стратегии аналогичен предыдущей, но к нему добавляется запрет на проведение сокращений внутри абстракции. Это так называемые ленивые вычисления. Вызов по значению. Здесь сокращение начинается с самого левого внешнего редекса, у которого в правой части стоит значение замкнутый терм, который нельзя вычислить далее. Для чистого лямбда исчисления таким термом будет. Данная стратегия используется в большинстве языков программирования, когда сначала вычисляются все аргументы, а затем все вместе подставляются в функцию. Не каждый терм имеет нормальную форму, например. Рассмотрим для примера выражение. На е то вычислении и зависнет стратегия вызова по значению, в то время как стратегия вызова по имени начнт с самого внешнего терма и там определит, что второй аргумент не нужен в принципе. Вывод если у редекса есть нормальная форма, то ленивая стратегия е обязательно найдт. Ещ одна тонкость связана с именованием переменных. Например, терм. Действительно, назови мы локальную переменную не y, а z первоначальный терм имел бы вид. Для исключения неоднозначностей такого рода надо чтко отслеживать, чтобы все свободные переменные из начального терма после подстановки оставались свободными. С этой целью используют. В этом случае данное выражение будет эквивалентно просто t. Такое преобразование называется. На этом закончим вводную в лямбда исчисление. В следующей статье мы займмся тем, ради чего вс и затевалось программированием на. Казалось бы, нет ничего более бессмысленного, чем рекурсия. Подобная цепочка вызовов никогда не завершится из за зацикливания, или в лучшем случае завершится, но аварийно, когда задача исчерпает все наличные ресурсы компьютера. На самом деле рекурсия это тонкий и изящный инструмент, который при умелом использовании способен сослужить добрую службу программисту. Действительно, почему именно рекурсии выпала честь удостоиться отдельной статьи Разве это не рядовой прием программирования, один из многих Лично я выделяю рекурсию из общего ряда по многим причинам. Вот некоторые из них Прежде всего, рекурсия красива. Первоначальное знакомство с ней может вызвать непонимание и легкий шок, но, овладев этим механизмом, вы вряд ли в дальнейшем сможете избежать соблазна пользоваться им время от времени. Изящество рекурсии в программировании я могу сравнить только с изяществом метода индукции в математике. Многие структуры, как искусственного, так и естественного происхождения, рекурсивны по самой своей сути. Рассмотрите ветви и корни деревьев, структуру сложной организации, иерархию классов в сложной программе, фракталы в любой из этих структур вы найдете многочисленные повторения целого в части. Таким образом, многие сущности естественным образом могут быть смоделированы рекурсивными структурами. А чем же еще обрабатывать рекурсивную структуру, как не рекурсивной процедурой Немало задач имеет также рекурсивную природу. Даже, пожалуй, большинство нетривиальных задач. По крайней мере, в программировании далеко не нов метод декомпозиции задачи на несколько более простых, те, в свою очередь, разделяются на еще более простые, и так до тех пор, пока не дойдем до элементарных частей, решить которые достаточно просто. Естественно, программисты не являются монополистами в этой области подобными методами пользуются архитекторы, машиностроители, математики. Несмотря на все эти достоинства, рекурсия отнюдь не спешит прописаться в арсенале средств многих программистов, даже профессиональных под профессионализмом в данный момент я подразумеваю отнюдь не степень мастерства, а факт, что именно программирование дает данному человеку средства к существованию, имеющих о ней самое смутное представление. Любое незнание обычно порождает массу предрассудков. Например, шаман племени людоедов, не имея представления об атмосферном электричестве, объясняет благодарным соплеменникам, что гроза это проявление немилости богов. И его слова принимаются за истину в первой инстанции, ибо природа не терпит пустоты, там, где нет знания, поселяется суеверие. Рекурсия также обросла слухами и суевериями. Вы можете услышать от компьютерных шаманов, что она безмерно расточительно относится к памяти забавно, но я слышал эти доводы много лет назад, программируя на мини ЭВМ PDP 1. Должен заметить, что с точки зрения практикующего программиста рекурсивное вычисление факториала весьма уступает обычному итерационному способу. Лично убедившись в этом, новичок обычно на этом и заканчивает знакомство с рекурсией, предпочитая потратить время на изучение более практичных вещей. Не будем отступать от традиции и мы. При этом, разумеется, примем вышесказанное к сведению и постараемся воспринять следующий пример просто как иллюстрацию к простейшему применению метода, а вовсе не как призыв весь остаток жизни вычислять факториалы именно таким образом. Итак, вспомним, что такое факториал. Обозначается факториал восклицательным знаком Внимательнее изучив формулу 1, мы можем прийти к выводу, что. N Казалось бы, такое определение совершенно бесполезно, так как неизвестное понятие определяется через опять же неизвестное понятие, и мы приходим к бесконечному циклу. Однако это впечатление обманчиво, потому что на самом деле факториал. Таким образом, есть надежда, что каждая следующая задача будет решаться чуть легче предыдущей. Окончательно разорвать замкнутый круг мы сможем, если дополним рекурсивное определение 2 еще одним, которое служит чем то вроде тупика, предназначенного для остановки процесса 1 Попробуем для примера вычислить значение 5, несколько раз применив правило 2 и однократно  правило 3 5 Попробуем реализовать рекурсивное вычисление факториала в виде функции на C long int Factlong int N Ведь первоначальное определение факториала ничуть не хуже, выглядит гораздо привычнее, да и реализовать его в общем то не сложнее long int Fact. N. Исключение, пожалуй, составит немногочисленная братия, программирующая на языках Lisp и Prolog, для которых рекурсивное мышление стало привычным ввиду особенностей применяемых инструментов. Id Вещей В Wow 3 3 5 A. На самом деле, разбираясь в столь детских по уровню примерах, мы затронули гораздо более глубинное и серьезное явление, а именно эквивалентность рекурсии и итерации. В теоретическом программировании существует теорема, которая гласит, что рекурсия и итерация эквивалентны. Это значит, что любой алгоритм, который можно реализовать рекурсивно, с таким же успехом может быть реализован и итеративно, и наоборот. Тем, кто знаком с теорией формальных языков, теорией конечных автоматов и подобными дисциплинами, она наверняка хорошо известна. Остальным придется поверить мне на слово, тем более что мы только что убедились в ее истинности на простейшем примере. Следует ли из этого, что мы попусту потратили время, я на написание данной статьи, вы на ее прочтение Не означает ли вышесказанное, что программисту достаточно владеть только приемами итерации для решения любых задач, поскольку она эквивалентна рекурсии Тут нам придется признать как факт, что теоретики программирования привыкли манипулировать довольно абстрактными понятиями вместо компьютера они используют машины Тьюринга, машины Поста и подобные сооружения, которые вы вряд ли приобретете в ближайшем компьютерном салоне. Соответственно, вместо программы у них алгоритм строго говоря, они не эквивалентны, ибо далеко не каждая программа является алгоритмом. При этом в центре внимания в первую очередь находится корректность алгоритма, об эффективности особенно не пекутся, ибо все, что требуется от алгоритма, это завершиться за конечное время, а уж насколько оно велико, теоретиков мало волнует, вычисления на машине Тьюринга все равно обходятся им даром. Мы же с вами живем в реальном мире, который далеко не столь идеален наши компьютеры обладают конечными ресурсами, за ограничения которых нам не выйти, а потребители наших программ конечным терпением, границы которого переходить тоже чревато. Поэтому мы вынуждены обращать внимание на такие низменные материи, как эффективность вычислений. А обратив на нее более пристальное внимание, мы будем неприятно поражены фактом несмотря на якобы обещанную эквивалентность, рекурсивный вариант вычисляет факториал куда медленнее, чем его итеративный собрат Более того, и памяти при работе он потребляет куда больше. Итак, оставим рекурсию теоретикам, а сами прекрасно обойдемся и без нееИменно к такому выводу приходят многие после изучения соответствующего раздела учебника программирования, в котором красуются все те же рекурсивные факториалы и числа Фибоначчи. Но не будем спешить с выводами. На самом деле есть очень много примеров, подобных вышеприведенному, в которых применение рекурсии просто расточительно и не выдерживает никакой конкуренции с итерацией. Однако существует немало и противоположных примеров, для которых рекурсивное решение просто и элегантно, а итеративное  громоздко и неестественно. Задача программиста  не только овладеть обоими подходами, но и научиться выбирать, какой из них применить в данном случае. Лично я, к сожалению, не могу предложить вам на этот счет готового рецепта интуиция и чувство меры  вот на что я обычно полагаюсь в подобных ситуациях. Итак, до сих пор мы рассматривали рекурсию на примере, рекурсивная реализация которого на практике малополезна. Теперь, осознав основные идеи, лежащие в основе рекурсии, приступим к рассмотрению задач, для решения которых она действительно полезна.