Рекурсия: Вычисление значения рекурсивной последовательности - Lisp
Формулировка задачи:
Вот От неожиданности ощущения привел лисп-решение прямо в разделе Вычисление значения рекурсивной последовательности - C++
тема
. Задача пустяковая. Но я вдруг поймал себя на мысли, что мне приятнее реализовать ее в Лиспе:(defun task (a x n) (if (zerop n) (list '+ a x) (list '+ (list '^ (task a x (- n 1)) 2) a))) ;; проверим: (task 'a 'x 5) ==> (+ (^ (+ (^ (+ (^ (+ (^ (+ (^ (+ A X) 2) A) 2) A) 2) A) 2) A) 2) A) ;; теперь из лисповской префиксной формы в обычную инфиксную: (defun pref2inf (e) (cond ((atom e) e) (t (list (pref2inf (cadr e)) (car e) (pref2inf (caddr e)))))) ;; И окончательно: (pref2inf (task 'a 'x 5)) ==> (((((((((((A + X) ^ 2) + A) ^ 2) + A) ^ 2) + A) ^ 2) + A) ^ 2) + A) ;; Ура!
Решение задачи: «Рекурсия: Вычисление значения рекурсивной последовательности»
textual
Листинг программы
(defun iterate-function (f n) (lambda (x) (loop for y = x then (funcall f y) repeat n finally (return y)))) (defun foo (x a n) (funcall (iterate-function (lambda (x) (+ (* x x) a)) n) (+ x a))) (defun bar (x a n) (funcall (iterate-function (lambda (x) `(,x ^ 2 + ,a)) n) `(,x + ,a))) > (foo 1 1 1) 5 > (bar 'x 'a 3) ((((X + A) ^ 2 + A) ^ 2 + A) ^ 2 + A)
Объяснение кода листинга программы
В коде определены три функции:
iterate-function
- принимает два аргумента:f
иn
. Внутри функции происходит рекурсивный вызов с использованиемloop
для повторения операцииn
раз. Результатом является значениеy
.foo
- принимает три аргумента:x
,a
иn
. Внутри функции происходит вызовiterate-function
с аргументами(lambda (x) (+ (* x x) a))
иn
. Результатом является значение, полученное отiterate-function
.bar
- принимает три аргумента:x
,a
иn
. Внутри функции происходит вызовiterate-function
с аргументами(lambda (x)
(,x ^ 2 + ,a))и
n. Результатом является значение, полученное от
iterate-function. При вызове функции
foo` с аргументами 1, 1 и 1, происходит следующее:iterate-function
вызывается с аргументами(lambda (x) (+ (* x x) a))
иn
.- Внутри
iterate-function
происходит рекурсивный вызов с аргументомx
. - Результатом рекурсивного вызова является значение
x
. - Результатом вызова функции
foo
является значение5
. При вызове функцииbar
с аргументами 'x', 'a' и 3, происходит следующее: iterate-function
вызывается с аргументами(lambda (x)
(,x ^ 2 + ,a))и
n`.- Внутри
iterate-function
происходит рекурсивный вызов с аргументомx
. - Результатом рекурсивного вызова является значение
(x + a)
. - Результатом вызова функции
bar
является значение(((X + A) ^ 2 + A) ^ 2 + A)
.