Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Повторение через итерацию или рекурсию

Функция - отображение между множествами | Управляющие структуры Лиспа являются формами | LET создаёт локальную связь | Разветвление вычислений: условное предложение COND | Использование файлов | LOAD загружает определения |


Читайте также:
  1. D) Между двумя теплоносителями через газ
  2. II. Повторение изученного материала.
  3. III. Повторение о сложном предложении.
  4. V. Анализ текста. Повторение.
  5. А где ты научилась драться? - посмотрел на меня через зеркало заднего вида Мирослав, уверенно ведя машину.
  6. А через неделю его нашли мертвым в собственной постели, диагноз - передоз.
  7. А) через ходатайство

В "чистом" функциональном Лиспе нет ни циклических предложений (  for, progn и другие), ни тем более операторов передачи управления. Для программирования повторяющихся вычислений в нём используются лишь условные предложения и определения рекурсивных, или вызывающих самих себя, функций.
Например, рекурсивный вариант функции  expt можно было бы определить так:

('number defmethod expt (n) (nil if (n < 2) this (this * (this expt (n - 1)))))

Функция  expt вызывает себя до тех пор, пока используемый как счётчик аргумент n не уменьшится до единицы, т.е. всего лишь n-1 раз. После этого в качестве результата вызова функции expt возвращается значение this. При каждой передаче значения на предыдущий уровень результат умножается на this. Так this окажется перемноженным на себя n раз.
Рекурсивное определение функции  expt короче, и лучше отражает суть функции, чем версии, основанные на for*.
Рассмотрим ещё одну функцию, просто определяемую через рекурсию, - факториал (факториал - это произведение данного числа на все целые положительные числа, меньшие данного. Например, факториал от 5, обозначаемый как 5!, есть 1*2*3*4*5=120. Факториалом нуля считается 1): 

>('number defmethod! () (nil if (this < 2) 1 (this * ((this - 1)!))))(lambda nil (nil if (this < 2) 1 (this * ((this - 1)!))))>(5!)120

Итеративные и рекурсивные программы теоретически одинаковы по своим вычислительным возможностям, иными словами, множества вычислимых с их помощью функций совпадают (так называемые частично рекурсивные функции). Так что любое вычисление в принципе, можно запрограммировать любым из этих способов. Однако свойства итеративных и рекурсивных вариантов программ могут существенно отличаться. В связи с этим часто приходится решать, какой из способов программирования больше подходит для данной задачи. От сделанного выбора зависит простота и естественность программирования, а также его эффективность с точки зрения времени исполнения и использования памяти. 
С помощью итеративного программирования, как правило, более длинного и трудного в осуществлении, результат может вычисляться значительно проще и быстрее. Это происходит по двум причинам, во-первых, потому, что вычислительные машины в общем ориентированы на пошаговые вычисления, и, во-вторых, потому, что трансляторы не всегда в состоянии преобразовать рекурсивное определение в итеративное и используют при вычислениях стек, несмотря на то что он не всегда нужен. 
Рекурсивное программирование в общем более короткое и содержательное. Особенно полезно использовать рекурсию в тех случаях, когда решаемая задача или обрабатываемые данные по сути своей рекурсивны. Например, математическое определение факториала рекурсивно и его реализация через рекурсивную функцию совершенно естественна: 

n! = 1 , если n=0
n! = n*(n-1)! , если n>0

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

 

Рекурсия (Lisp)

Рекурсия - один из основных приёмов программирования в декларативных языках, какими являются Пролог и Лисп. Предикат или функция называются рекурсивными, если они ссылаются на самих себя. При этом задача разбивается на части все меньшего и меньшего размера до тех пор, пока они не станут настолько малы, что их решение не будет сводиться к набору из одной или нескольких простейших операций.

Обычно рекурсивная программа состоит как минимум из двух частей:

  1. граничного условия, при котором рекурсия останавливается;
  2. рекурсивного условия, при котором в описание функции или предиката входит и сама функция или предикат.

Механизм рекурсии часто объясняют на вычислениях чисел Фибоначчи, первые 10 которых приведены в таблице:

 

Числа Фибоначчи (первые 10 значений)
Номер числа Фибоначчи                      
Значение числа Фибоначчи                      

 

Здесь каждое следующее число представляет собой сумму двух предыдущих чисел.

Эти числа могут быть определены следующим соотношением:

fib(0) = 1

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2)

На рисунке представлена схема вычисления числа Фибоначчи с помощью рекурсии.

На Лиспе программа, реализующая эту функцию, будет выглядеть так:

(defun fib(n)

(if (< n 2) 1;граничное условие

(+ (fib (- n 1)) (fib (- n 2)))));рекурсивное условие

>(fib 10)

 


Дата добавления: 2015-07-21; просмотров: 68 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Циклические вычисления: предложения FOR, FOR*, WHILE и DO-WHILE| READ-LINE читает и возвращает выражение

mybiblioteka.su - 2015-2024 год. (0.007 сек.)