Lisp的递归方使用一个变量

这是试图代码Lisp的递归方使用一个变量

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

应该返回27，(f 4)应该返回256

我试着用两个变量，但它是违反规则的。

是否有可能使用递归只使用一个变量？

感谢您的任何想法

来源

2017-02-20 MinSeob Lim

是的，这是可能的：

(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))

来源

2017-02-20 14:51:09 melpomene

如果你想在alist中乘以数字，那么最好使用REDUCE而不是APPLY。 APPLY可能仅支持最大长度为CALL-ARGUMENTS-LIMIT的列表。 –

我不知道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))

借口任何语法错误。

来源

2017-02-20 14:32:04 Carcigenicate

感谢您的回答。关于语法，在CL（http）中写入'（let（（g（fn（n）...）））...）''（标签（（g（n）...））...）：//www.lispworks.com/documentation/HyperSpec/Body/s_flet_.htm） – coredump

@coredump'labels'？从来没有猜到过。当我接触我的笔记本电脑时，我会解决这个问题。感谢您的高举。 – Carcigenicate

是的。这是令人惊讶的，但历史原因是有趣的，甚至在上下文中是有道理的：https://www.reddit.com/r/lisp/comments/k1tnl/where_does_the_special_form_labels_come_from/ – coredump

使用一个额外的变量倒计时将是明智的选择，但你并不需要改变只是一个数字参数输入只是为了这个合同。你可以造一个配偶帮助做到这一点：

(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无喜悦！

来源

2017-02-20 16:50:02 Sylwester

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)

来源

2017-02-21 09:59:12

这是其中使用一个以上的参数没有功能的溶液（除了=，+，*，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)))

没有合理的实际使用，当然;但确实是一个有趣的运动。

来源

2017-02-23 07:28:47 6502

Lisp的递归方使用一个变量

回答

相关问题