Инструменты пользователя

Инструменты сайта


examination:flp:question26

Структура программы в РС – Лиспе.

Структура программы на Лиспе (его базовой, или элементарной, версии) крайне проста. Она представляет собой последовательность lambda-описаний функций и их вызовов с параметрами. Каждая функция поочередно вызывается, и результат ее работы сразу выводится на консоль. А главным механизмом управления последовательностью вычислений в Лиспе считается рекурсия (вызов функцией самой себя), а не условные и циклические вычисления, как принято в массовых языках программирования наподобие Си или Паскаля. В элементарном Лиспе их просто нету, кроме некоего условного прообраза cond!

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

Факториал-числа( N ) равен: - единице (1), если N = 1; - выражению (N * Факториал-числа( N-1 )) , если N больше 1.

В таком случае вычисление факториала произойдет автоматически. Например, по нашему алгоритму

Факториал-числа( 4 ) = 4 * Факториал-числа( 3 ) = 4 * (3 * Факториал-числа( 2 )) = 4 * 3 * (2 * Факториал-числа( 1 )) = 4 * 3 * 2 * 1 = 24

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

Запишем этот алгоритм на языке Лисп:

; N - параметр, как переменная :
(define FAKTORIAL (lambda (N)

; условие :
(cond

; если N <= 1 , то возвращаем единицу...
((<= N 1) 1)

; в противном случае...
(true

; ...возвращаем N*FAKTORIAL(N-1)
(* N (FAKTORIAL (- N 1)) )) 
) ) )
examination/flp/question26.txt · Последние изменения: 2014/01/15 12:17 (внешнее изменение)