Рекурсия: Вычисление значения рекурсивной последовательности - Lisp

Узнай цену своей работы

Формулировка задачи:

Вот

тема

. Задача пустяковая. Но я вдруг поймал себя на мысли, что мне приятнее реализовать ее в Лиспе:
(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)
 
;; Ура!
От неожиданности ощущения привел лисп-решение прямо в разделе Вычисление значения рекурсивной последовательности - C++

Решение задачи: «Рекурсия: Вычисление значения рекурсивной последовательности»

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)

Объяснение кода листинга программы

В коде определены три функции:

  1. iterate-function - принимает два аргумента: f и n. Внутри функции происходит рекурсивный вызов с использованием loop для повторения операции n раз. Результатом является значение y.
  2. foo - принимает три аргумента: x, a и n. Внутри функции происходит вызов iterate-function с аргументами (lambda (x) (+ (* x x) a)) и n. Результатом является значение, полученное от iterate-function.
  3. bar - принимает три аргумента: x, a и n. Внутри функции происходит вызов iterate-function с аргументами (lambda (x)(,x  ^ 2 + ,a))иn. Результатом является значение, полученное отiterate-function. При вызове функцииfoo` с аргументами 1, 1 и 1, происходит следующее:
  4. iterate-function вызывается с аргументами (lambda (x) (+ (* x x) a)) и n.
  5. Внутри iterate-function происходит рекурсивный вызов с аргументом x.
  6. Результатом рекурсивного вызова является значение x.
  7. Результатом вызова функции foo является значение 5. При вызове функции bar с аргументами 'x', 'a' и 3, происходит следующее:
  8. iterate-function вызывается с аргументами (lambda (x)(,x  ^ 2 + ,a))иn`.
  9. Внутри iterate-function происходит рекурсивный вызов с аргументом x.
  10. Результатом рекурсивного вызова является значение (x + a).
  11. Результатом вызова функции bar является значение (((X + A) ^ 2 + A) ^ 2 + A).

Оцени полезность:

14   голосов , оценка 3.857 из 5
Похожие ответы