Конструкция let

Дата добавления: 2015-01-16; просмотров: 597; Нарушение авторских прав

§ Специальная форма let позволяет создать локальное окружение

§ (let ((x 1) (y 2))§ (+ x y))

§ В данном окружении переменным x и y присваиваются числовые значения, а потом вычисляется выражение с +

§ Существует модификация let* (let зо звёздочкой), которая позволяет использовать присвоенное значение в других присвоениях

§ (let* ((x 1) (y x))§ (+ x y))

25)Понятие рекурсии

§ Два определения:

О понимании рекурсии

§ Чтобы понять рекурсию нужно...понять рекурсию.

Из словаря:

§ Рекурсия - см. рекурсия

Цитата

§ Итерация от человека. Рекурсия - от Бога.- Л. Питер Дойч (Д. Кнут. Искусство программирования.)

§ Рассмотренный пример рекурсивной процедуры называется линейным рекурсивным процессом (ЛРП), поскольку он требует цепочки отложенных вычислений и числа шагов пропорционально n.

§ ЛРП могут приводить к сбоям в работе программ из-за исчерпания свободной памяти.

§ Другой способ вычисления факториала:

§ (define (factorial n)§ (fact-iter 1 1 n))§ § (define (fact-iter product counter max-count)§ (if (> counter max-count)§ product§ (fact-iter (* counter product)§ (+ counter 1)§ max-count)))

Решение представлено в виде двух процедур. factorial запускает процесс вычисления fact-iter с начальными данными 1 1 n (накопитель, текущий элемент, последний элемент).

В процессе работы значение параметров fact-iter меняется:

(factorial 6)(fact-iter 1 1 6)(fact-iter 1 2 6)(fact iter 2 3 6)(fact-iter 6 4 6)(fact-iter 24 5 6)(fact-iter 120 6 6)(fact-iter 720 7 6)720

\gls{tail}

§ Во втором случае рекурсия может быть представлена в виде итерации без линейного расширения объёма используемой памяти и может быть заменена обычном циклом.

§ В языке scheme поддерживается механизм хвостовой рекурсии, когда рекурсивный процесс может быть заменён на итеративный (циклический) при выполнении программы, но только тогда, когда рекурсия описана как во втором примере вычисления факториала.

<== предыдущая лекция	\|	следующая лекция ==>
Определение процедуры-предиката	\|	Блочная структура