Cтраница 1
Рекурсивное программирование в общем более короткое и содержательное. Особенно полезно использовать рекурсию в тех случаях, когда решаемая задача или обрабатываемые данные по сути своей рекурсивны. [1]
Основные методы программирования на Лиспе - функциональное и рекурсивное программирование - рассматриваются более детально и систематично с подразделением типов функций и форм рекурсии на отдельные виды, что является новшеством по сравнению с предшествующими публикациями по Лиспу. Первая часть книги может использоваться для самостоятельного изучения как языка Лисп, так и функционального программирования. [2]
Язык Модула-2 хорошо приспособлен для задачи рекурсивного программирования. Процедуры Модулы-2, как обычные, так и процедуры-функции, могут вызывать сами себя. Процедура, вызывающая сама себя, не единственная форма рекурсивного программирования. Другой случай, приводящий к рекурсии, - процедура А вызывает процедуру В, в свою очередь вызывающую процедуру А. В этом случае рекурсия называется косвенной, но тем не менее рекурсией. [3]
Если вы уже знакомы с рекурсией и рекурсивным программированием, вы найдете мало нового в этой главе. [4]
В последующем параграфе мы увидим, что метод рекурсивного программирования - не лучший способ вычисления факториала. Это пример ситуации, в которой задачу можно, но не следует решать рекурсивно. [5]
Модуль может вызывать другой модуль уровнем ниже; он не может вызывать модуль своего уровня или выше. Однако он может вызывать сам себя - это случай рекурсивного программирования. Подобные связи упрощают межмодульный обмен данными. Однако иногда возникает потребность активизировать модуль, расположенный несколькими уровнями ниже. Это разрешено, но в таком случае модуль должен быть указан в схеме несколько раз на соответствующих уровнях. Такие модули следует специально отмечать на схеме иерархии. [6]
Хотя такого рода структуры не изучаются в данной книге, эта программа представляет интерес по нескольким соображениям. Наиболее важное из них то, что она демонстрирует значение и мощность методов рекурсивного программирования. Любое двоичное дерево состоит из корня, а также правого и левого поддерева, выходящих из этого корня. Каждое поддерево само является деревом. [7]
Например, хорошо изучены рекурсивные схемы программ, корректность вычислений в функциональных системах ( теория неподвижной точки), рекурсивное программирование ( язык ЛИСП, функциональные системы Бэкуса и им подобные), трансляция языков программирования и ряд других задач. Однако возникающие при этом подходы во многом не связаны между собой, ориентированы на решение хотя и важных, но частных проблем, и носят специальный характер. [8]
Язык Модула-2 хорошо приспособлен для задачи рекурсивного программирования. Процедуры Модулы-2, как обычные, так и процедуры-функции, могут вызывать сами себя. Процедура, вызывающая сама себя, не единственная форма рекурсивного программирования. Другой случай, приводящий к рекурсии, - процедура А вызывает процедуру В, в свою очередь вызывающую процедуру А. В этом случае рекурсия называется косвенной, но тем не менее рекурсией. [9]
В настоящее время распространен взгляд на рекурсию как на интересное, но необязательное украшение системы программирования. К тому же против рекурсии существует значительное предубеждение, которое объясняется тем, что в большинстве случаев машины не предназначены для работы с рекурсивными процедурами и поэтому выполняют их неэффективно. Однако если преимущества этого способа программирования получат должную оценку, то машины будут конструироваться с таким расчетом, чтобы облегчать рекурсивное программирование. Надеюсь, что эта книга сможет способствовать признанию рекурсии и убедит читателя в том, что рекурсия не является чем-то нарочито усложненным и не предназначена для касты посвященных, а просто представляет собой еще одно средство программирования, которым можно пользоваться удачно или злоупотреблять, как и всяким другим. [10]
В настоящее время распространен взгляд на рекурсию как на интересное, но необязательное украшение системы программирования. К тому же против рекурсии существует значительное предубеждение, которое объясняется тем, что в большинстве случаев машины не предназначены для работы с рекурсивными процедурами и поэтому выполняют их неэффективно. Однако если преимущества этого способа программирования получат должную оценку, то машины будут конструироваться с таким расчетом, чтобы облегчать рекурсивное программирование. [11]
Тип CONTROLLED мы не рассматриваем. Если переменная объявляется как STATIC, то память для этой переменной отводится в начале выполнения программы и не освобождается до конца ее выполнения. Если переменная объявляется как AUTOMATIC, то память отводится каждый раз при входе в процедуру и освобождается при выходе из нее. Если память для данных уже отведена при входе в процедуру, а новый вход в процедуру происходит до выхода из нее, то уже отведенная память опускается в магазин и отводится новая память, которая используется до первого выхода из процедуры, после чего восстанавливается ( поднимается из магазина) ранее выделенная память. Такая методика распределения памяти требуется при организации рекурсивного программирования, с которым мы не знакомились. Для данных с описателем CONTROLLED ( указатель) память отводится, когда выполняется оператор READ SET ( указатель), и сохраняется за ними до следующего отведения памяти для этого файла или до его закрытия. [12]
Есть несколько категорий задач, допускающих рекурсивные определения и решения. Одна из таких категорий - математические формулы, определения которых рекурсивны по своей сути. Под этим мы понимаем математические выражения, в которых определение общего члена выражения имеет вид функции предыдущих членов. Поскольку эта книга - не учебник математики, объяснение математической рекурсии будет дано на самом примитивном уровне. Цель состоит в том, чтобы продемонстрировать метод рекурсивного программирования Модулы-2, а не обучать математике. [13]