Cтраница 3
Первая строка в описании всего лишь позволяет писать аргументы в любом порядке. В общем случае можно утверждать, что рекурсивное использование процедуры требует очевидной конечной глубины рекурсии, тогда как вычисление рекурсивно описанной функции влечет за собой неопределенную глубину рекурсии, зависящую от значений аргументов. Если описание предназначено для практических вычислений, то глубина рекурсии должна быть конечной. Бесконечное по глубине рекурсивное описание называется регрессивным. Некоторые рекурсивные описания могут иметь конечную глубину рекурсии при одних входных данных и бесконечную при других. Теоретически невозможно определять с помощью единого алгоритма, окажется ли произвольное описание конечным в любом случае, однако часто можно показать, будет ли в отдельных случаях глубина рекурсии конечной или бесконечной. [31]
На этом этапе целесообразно упомянуть также получение перестановок, хотя эта задача и не совсем относится к численному анализу. Все перестановки N объектов могут быть получены, если брать по очереди каждый объект и помещать его перед всеми перестановками оставшихся ( N - 1) объектов. Этот пример еще раз иллюстрирует изящество рекурсивных описаний; любое нерекурсивное описание данного процесса оказалось бы гораздо более сложным. [32]
На этом этапе целесообразно упомянуть также получение перестановок, хотя эта задача и не совсем относится к численному анализу. Все перестановки N объектов могут быть получены, если брать по очереди каждый объект и помещать его перед всеми перестановками оставшихся ( N - 1) объектов. Этот пример еще раз иллюстрирует изящество рекурсивных описаний; любое нерекурсивное описание данного процесса оказалось бы гораздо более сложным. [33]
При исполнении процедур может возникнуть ситуация, когда необходимо обратиться к этой же процедуре. Такой вид процедуры, описанной на языке АЛГОЛ, называют рекурсивной процедурой. Пользуясь этой процедурой, иногда удается коротко и наглядно описать процесс решения зада чи. Однако следует иметь в виду, что перевод рекурсивного описания на машинный язык очень сложен и доступен не каждой программе-транслятору машины. [34]
Первая строка в описании всего лишь позволяет писать аргументы в любом порядке. В общем случае можно утверждать, что рекурсивное использование процедуры требует очевидной конечной глубины рекурсии, тогда как вычисление рекурсивно описанной функции влечет за собой неопределенную глубину рекурсии, зависящую от значений аргументов. Если описание предназначено для практических вычислений, то глубина рекурсии должна быть конечной. Бесконечное по глубине рекурсивное описание называется регрессивным. Некоторые рекурсивные описания могут иметь конечную глубину рекурсии при одних входных данных и бесконечную при других. Теоретически невозможно определять с помощью единого алгоритма, окажется ли произвольное описание конечным в любом случае, однако часто можно показать, будет ли в отдельных случаях глубина рекурсии конечной или бесконечной. [35]
Различие между рекурсивным языком типа АЛГОЛа и нерекурсивным языком типа ФОРТРАНа состоит в том, что на ФОРТРАНе программист, желающий пользоваться рекурсией, должен разработать для себя соответствующий аппарат, тогда как на АЛГОЛе этот аппарат обеспечивается системой, так сказать за кулисами. Во многих рекурсивных системах за это приходится платить тем, что автоматический аппарат, предусмотренный для обеспечения рекурсии, вступает в действие даже тогда, когда программа не является рекурсивной; это приводит к напрасным затратам машинного времени. Разумеется, существуют различные способы организации рекурсии, некоторые из них будут весьма подробно рассмотрены в следующих главах. Программист может указывать, какие функции или процедуры являются рекурсивными, а какие нет, или же достаточно развитый компилятор может сам выяснять это для себя. Однако все это неидеальные решения, так как, даже если какой-то процесс может быть представлен итеративно, его рекурсивное описание может оказаться значительно более простым. Поэтому было бы выгодно сочетать легкость написания рекурсивных описаний с высокой скоростью выполнения итеративного процесса, и лучший способ достижения этой цели состоит в изменении традиционной машинной аппаратуры. Теоретическое изучение соотношений между рекурсивными и итеративными программами показывает, что иногда возможно переводить рекурсивное описание в эквивалентную итеративную программу; такое преобразование описывается более подробно в гл. [36]
Различие между рекурсивным языком типа АЛГОЛа и нерекурсивным языком типа ФОРТРАНа состоит в том, что на ФОРТРАНе программист, желающий пользоваться рекурсией, должен разработать для себя соответствующий аппарат, тогда как на АЛГОЛе этот аппарат обеспечивается системой, так сказать за кулисами. Во многих рекурсивных системах за это приходится платить тем, что автоматический аппарат, предусмотренный для обеспечения рекурсии, вступает в действие даже тогда, когда программа не является рекурсивной; это приводит к напрасным затратам машинного времени. Разумеется, существуют различные способы организации рекурсии, некоторые из них будут весьма подробно рассмотрены в следующих главах. Программист может указывать, какие функции или процедуры являются рекурсивными, а какие нет, или же достаточно развитый компилятор может сам выяснять это для себя. Однако все это неидеальные решения, так как, даже если какой-то процесс может быть представлен итеративно, его рекурсивное описание может оказаться значительно более простым. Поэтому было бы выгодно сочетать легкость написания рекурсивных описаний с высокой скоростью выполнения итеративного процесса, и лучший способ достижения этой цели состоит в изменении традиционной машинной аппаратуры. Теоретическое изучение соотношений между рекурсивными и итеративными программами показывает, что иногда возможно переводить рекурсивное описание в эквивалентную итеративную программу; такое преобразование описывается более подробно в гл. [37]
Различие между рекурсивным языком типа АЛГОЛа и нерекурсивным языком типа ФОРТРАНа состоит в том, что на ФОРТРАНе программист, желающий пользоваться рекурсией, должен разработать для себя соответствующий аппарат, тогда как на АЛГОЛе этот аппарат обеспечивается системой, так сказать за кулисами. Во многих рекурсивных системах за это приходится платить тем, что автоматический аппарат, предусмотренный для обеспечения рекурсии, вступает в действие даже тогда, когда программа не является рекурсивной; это приводит к напрасным затратам машинного времени. Разумеется, существуют различные способы организации рекурсии, некоторые из них будут весьма подробно рассмотрены в следующих главах. Программист может указывать, какие функции или процедуры являются рекурсивными, а какие нет, или же достаточно развитый компилятор может сам выяснять это для себя. Однако все это неидеальные решения, так как, даже если какой-то процесс может быть представлен итеративно, его рекурсивное описание может оказаться значительно более простым. Поэтому было бы выгодно сочетать легкость написания рекурсивных описаний с высокой скоростью выполнения итеративного процесса, и лучший способ достижения этой цели состоит в изменении традиционной машинной аппаратуры. Теоретическое изучение соотношений между рекурсивными и итеративными программами показывает, что иногда возможно переводить рекурсивное описание в эквивалентную итеративную программу; такое преобразование описывается более подробно в гл. [38]