Lisp рекурсивный квадрат использовать один переменных

Question

Это Стараясь код

(defun f (a n) 
    (if (zerop n) 
     1 
     (* a (f a (- n 1))))) 

должен вернуть 27, (f 4) должен вернуть 256

Я попытался с помощью двух переменных, но это против правил.

Можно ли использовать только одну переменную с использованием рекурсивной?

Спасибо за любые идеи

Answer 1

Да, это возможно:

(defun f (n) 
    (cond 
    ((numberp n) 
     (f (cons n n))) 
    ((zerop (car n)) 
     1) 
    (t 
     (* (cdr n) 
     (f (cons (1- (car n)) 
        (cdr n))))))) 

Хитрость заключается в том, что вы можете хранить любую структуру данных (в том числе пара чисел) в одной переменной.

---

В качестве альтернативы, вы можете использовать хелперы из стандартной библиотеки:

(defun f (n) 
    (apply #'* 
     (loop repeat n collect n))) 

Но это не использовать рекурсию. Или просто:

(defun f (n) 
    (expt n n)) 

Answer 2

я не знаю CL, но я знаю, Clojure и других языков, которые используют рекурсию.

В случае, когда рекурсивная функция имеет 1 параметр, действующий в качестве аккумулятора, но только для первого вызова, типичным способом для этого является обертка f в другой функции. Есть 2 (в основном одни и те же) способы сделать это:

(defun g (a n) 
    (if (zerop n) 
     1 
     (* a (g a (- n 1))))) 

(defun f (n) 
    ; I'm assuming you want the initial value of "a" to be 1 
    (g 1 n)) 

Или, более лаконично:

(defun f (n) 
    (let (g (fn (n) 
      (if (zerop n) 
       1 
       (* a (g a (- n 1)))))))) 
    ; Instead of f being recursive, f calls g, which is recursive 
    (g 1 n)) 

Извините любые синтаксические ошибки.

Answer 3

Использование дополнительной переменной отсчитывать бы здравомыслящий выбор, но вам не нужно менять договор только одного числового ввода аргумента только для этого. Вы можете сделать помощник, чтобы сделать это:

(defun exptnn (n) 
    "Get the (expt n n)" 
    (check-type n integer) 
    (labels ((helper (acc count) 
      (if (zerop count) 
       acc 
       (helper (* acc n) (1- count))))) 
    (if (< n 0) 
     (/ 1 (helper 1 (- n))) 
     (helper 1 n)))) 

Теперь решить с без каких-либо помощников только с одним аргументом можно, так как есть решение сделать это уже, но я должен сказать, что это как программирование в Brainf*ck без радость!

Answer 4

CL-USER 15 > (defun f (n) 
       (labels ((g (m) 
         (if (zerop m) 
          1 
          (* n (g (1- m)))))) 
       (g n))) 
F 

CL-USER 16 > (f 0) 
1 

CL-USER 17 > (f 1) 
1 

CL-USER 18 > (f 2) 
4 

CL-USER 19 > (f 3) 
27 

CL-USER 20 > (f 4) 
256 

CL-USER 21 > (loop for i below 10 collect (f i)) 
(1 1 4 27 256 3125 46656 823543 16777216 387420489) 

Answer 5

Это решение, в котором не используются функции с более чем одним параметром (за исключением =, +, *, logand, ash; Отметим также, что logand и ash всегда имеют константу в качестве второго параметра, чтобы они могли также реализуются как унарные функции).

Идея состоит в том, чтобы «скрыть» два параметра, необходимые для очевидного рекурсивного подхода в одном целом с использованием нечетных/четных битов.

(defun pair (n) 
    (if (= n 0) 
     0 
     (+ (* 3 (logand n 1)) 
     (ash (pair (ash n -1)) 2)))) 

(defun pair-first (p) 
    (if (= p 0) 
     0 
     (+ (logand p 1) 
     (ash (pair-first (ash p -2)) 1)))) 

(defun pair-second (p) 
    (pair-first (ash p -1))) 

(defun subsec (p) 
    (if (= 2 (logand p 2)) 
     (- p 2) 
     (+ (logand p 1) 2 (ash (subsec (ash p -2)) 2)))) 

(defun pairpow (p) 
    (if (= (pair-second p) 1) 
     (pair-first p) 
     (* (pair-first p) 
     (pairpow (subsec p))))) 

(defun f (n) 
    (pairpow (pair n))) 

Нет разумного использования, конечно; но забавное упражнение действительно.