学习 lisp 递归

llsheng_73

个人觉得最好的要依赖于递归，它对于真正理解算法没帮助，相反的，把一些经典的算法从递归剥离出来可能对于算法的理解会更深入些,个人看法，希望别介意

lanjqka

2. ;|
   
3. _$$ (czr '(0 1 2 3 4))
   
4. 4
   
5. |;
   
6. (defun czr (lst)
   
7.   (if (null (cadr lst))
   
8.     (car lst)
   
9.     (czr (cdr lst))
   
10.   )
    
11. )
    
12. 
    
13. ;|
    
14. _$$ (cztr '(0 1 2 3 4))
    
15. 3
    
16. |;
    
17. (defun cztr (lst)
    
18.   (if (null (caddr lst))
    
19.     (car lst)
    
20.     (cztr (cdr lst))
    
21.   )
    
22. )
    
23. 
    
24. ;|
    
25. _$$ (czttr '(0 1 2 3 4))
    
26. 2
    
27. |;
    
28. (defun czttr (lst)
    
29.   (if (null (cadddr lst))
    
30.     (car lst)
    
31.     (czttr (cdr lst))
    
32.   )
    
33. )
    
34. 
    
35. ;|
    
36. _$$ (ctr '(0 1 2 3 4))
    
37. (0 1 2 3)
    
38. |;
    
39. (defun ctr (lst)
    
40.   (if (null (cadr lst))
    
41.     nil
    
42.     (cons (car lst) (ctr (cdr lst)))
    
43.   )
    
44. )
    
45. 
    
46. ;|
    
47. _$$ (cttr '(0 1 2 3 4))
    
48. (0 1 2)
    
49. |;
    
50. (defun cttr (lst)
    
51.   (if (null (caddr lst))
    
52.     nil
    
53.     (cons (car lst) (cttr (cdr lst)))
    
54.   )
    
55. )
    
56. 
    
57. ;|
    
58. _$$ (ctttr '(0 1 2 3 4))
    
59. (0 1)
    
60. |;
    
61. (defun ctttr (lst)
    
62.   (if (null (cadddr lst))
    
63.     nil
    
64.     (cons (car lst) (ctttr (cdr lst)))
    
65.   )
    
66. )

;|<br /> _$$ (czr '(0 1 2 3 4))<br /> 4<br /> |;<br /> (defun czr (lst)<br />   (if (null (cadr lst))<br />     (car lst)<br />     (czr (cdr lst))<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (cztr '(0 1 2 3 4))<br /> 3<br /> |;<br /> (defun cztr (lst)<br />   (if (null (caddr lst))<br />     (car lst)<br />     (cztr (cdr lst))<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (czttr '(0 1 2 3 4))<br /> 2<br /> |;<br /> (defun czttr (lst)<br />   (if (null (cadddr lst))<br />     (car lst)<br />     (czttr (cdr lst))<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (ctr '(0 1 2 3 4))<br /> (0 1 2 3)<br /> |;<br /> (defun ctr (lst)<br />   (if (null (cadr lst))<br />     nil<br />     (cons (car lst) (ctr (cdr lst)))<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (cttr '(0 1 2 3 4))<br /> (0 1 2)<br /> |;<br /> (defun cttr (lst)<br />   (if (null (caddr lst))<br />     nil<br />     (cons (car lst) (cttr (cdr lst)))<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (ctttr '(0 1 2 3 4))<br /> (0 1)<br /> |;<br /> (defun ctttr (lst)<br />   (if (null (cadddr lst))<br />     nil<br />     (cons (car lst) (ctttr (cdr lst)))<br />   )<br /> )

lanjqka

llsheng_73 发表于 2014-1-13 13:27
个人觉得最好的要依赖于递归，它对于真正理解算法没帮助，相反的，把一些经典的算法从递归剥离出来可能对于 ...

不介意
只是学习递归
不希望做争论

lanjqka

2. ;|
   
3. _$$$$$$$$ (powerset '(1 2 3))
   
4. ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)
   
5. _$$$$$$$$ (powerset '(0 1 2 3))
   
6. ((0 1 2 3) (0 1 2) (0 1 3) (0 1) (0 2 3) (0 2) (0 3) (0) (1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)
   
7. |;
   
8. (defun powerset (lst)
   
9.   (if (null lst)
   
10.     (list nil)
    
11.     (setpower (list (car lst)) (powerset (cdr lst)))
    
12.   )
    
13. )
    
14. ;|
    
15. _$$$$$$$$ (mapcar-append '(0) '((1 2) (1) (2)))
    
16. ((0 1 2) (0 1) (0 2))
    
17. _$$$$$$$$ (setpower '(0) '((1 2) (1) (2)))
    
18. ((0 1 2) (0 1) (0 2) (1 2) (1) (2))
    
19. |;
    
20. (defun setpower (lsta lstb)
    
21.   (defun mapcar-append (lsta lstb)
    
22.     (if (null lsta)
    
23.       nil
    
24.       (if (null lstb)
    
25.         nil
    
26.         (cons (append lsta (car lstb)) (mapcar-append lsta (cdr lstb)))
    
27.       )
    
28.     )
    
29.   )
    
30.   (append (mapcar-append lsta lstb) lstb)
    
31.   ;;(append (mapcar '(lambda (x) (append lsta x)) lstb) lstb)
    
32. )

;|<br /> _$$$$$$$$ (powerset '(1 2 3))<br /> ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)<br /> _$$$$$$$$ (powerset '(0 1 2 3))<br /> ((0 1 2 3) (0 1 2) (0 1 3) (0 1) (0 2 3) (0 2) (0 3) (0) (1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)<br /> |;<br /> (defun powerset (lst)<br />   (if (null lst)<br />     (list nil)<br />     (setpower (list (car lst)) (powerset (cdr lst)))<br />   )<br /> )<br /> ;|<br /> _$$$$$$$$ (mapcar-append '(0) '((1 2) (1) (2)))<br /> ((0 1 2) (0 1) (0 2))<br /> _$$$$$$$$ (setpower '(0) '((1 2) (1) (2)))<br /> ((0 1 2) (0 1) (0 2) (1 2) (1) (2))<br /> |;<br /> (defun setpower (lsta lstb)<br />   (defun mapcar-append (lsta lstb)<br />     (if (null lsta)<br />       nil<br />       (if (null lstb)<br />         nil<br />         (cons (append lsta (car lstb)) (mapcar-append lsta (cdr lstb)))<br />       )<br />     )<br />   )<br />   (append (mapcar-append lsta lstb) lstb)<br />   ;;(append (mapcar '(lambda (x) (append lsta x)) lstb) lstb)<br /> )

lanjqka

2. ;|
   
3. _$$ (find-matching-pair '= '(1 2 3 4 5 6 7 1))
   
4. (1 . 1)
   
5. _$$ (find-matching-pair '< '(1 2 3 4 5 6 7 1))
   
6. (1 . 2)
   
7. _$$ (find-matching-pair '> '(1 2 3 4 5 6 7 1))
   
8. nil
   
9. |;
   
10. (defun find-matching-pair (test lst)
    
11.   (if (null (cadr lst))
    
12.     nil
    
13.     (if ((eval test) (car lst) (cadr lst))
    
14.       (cons (car lst) (cadr lst))
    
15.       (find-matching-pair test (cons (car lst) (cddr lst)))
    
16.     )
    
17.   )
    
18. )

;|<br /> _$$ (find-matching-pair '= '(1 2 3 4 5 6 7 1))<br /> (1 . 1)<br /> _$$ (find-matching-pair '< '(1 2 3 4 5 6 7 1))<br /> (1 . 2)<br /> _$$ (find-matching-pair '> '(1 2 3 4 5 6 7 1))<br /> nil<br /> |;<br /> (defun find-matching-pair (test lst)<br />   (if (null (cadr lst))<br />     nil<br />     (if ((eval test) (car lst) (cadr lst))<br />       (cons (car lst) (cadr lst))<br />       (find-matching-pair test (cons (car lst) (cddr lst)))<br />     )<br />   )<br /> )

q3_2006

这个用递归怎么写...拜托高手指导下

2. (defun tst (l n / k nn)
   
3.   (setq k -1 nn (length l))
   
4.   (mapcar
   
5.     (function
   
6.       (lambda (a / ll m)
   
7.        (setq k (1+ k) m k)
   
8.        (repeat n
   
9.        (setq ll (append ll (list (nth m l))))
   
10.        (setq m (rem (1+ m) nn))
    
11.        ll
    
12.        )
    
13.        )
    
14.       )
    
15.     l
    
16.     )
    
17.   )

(defun tst (l n / k nn)<br />   (setq k -1 nn (length l))<br />   (mapcar<br />     (function<br />       (lambda (a / ll m)<br />        (setq k (1+ k) m k)<br />        (repeat n<br />        (setq ll (append ll (list (nth m l))))<br />        (setq m (rem (1+ m) nn))<br />        ll<br />        )<br />        )<br />       )<br />     l<br />     )<br />   )

lanjqka

q3_2006 发表于 2014-1-17 11:37
这个用递归怎么写...拜托高手指导下

2. ;|
   
3. _$$ (ntha 2 '(0 1 2 3 4))
   
4. (0 1)
   
5. |;
   
6. (defun ntha (n lst)
   
7.   (if (null lst)
   
8.     nil
   
9.     (if (zerop n)
   
10.       nil
    
11.       (cons (car lst) (ntha (- n 1) (cdr lst)))
    
12.     )
    
13.   )
    
14. )
    
15. 
    
16. ;|
    
17. _$$ (tst '(0 1 2 3 4) 2)
    
18. ((0 1) (1 2) (2 3) (3 4))
    
19. |;
    
20. (defun tst (lst n)
    
21.   (if (null lst)
    
22.     nil
    
23.     (if (< (length lst) n)
    
24.       nil
    
25.       (cons (ntha n lst) (tst (cdr lst) n))
    
26.     )
    
27.   )
    
28. )

;|<br /> _$$ (ntha 2 '(0 1 2 3 4))<br /> (0 1)<br /> |;<br /> (defun ntha (n lst)<br />   (if (null lst)<br />     nil<br />     (if (zerop n)<br />       nil<br />       (cons (car lst) (ntha (- n 1) (cdr lst)))<br />     )<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (tst '(0 1 2 3 4) 2)<br /> ((0 1) (1 2) (2 3) (3 4))<br /> |;<br /> (defun tst (lst n)<br />   (if (null lst)<br />     nil<br />     (if (< (length lst) n)<br />       nil<br />       (cons (ntha n lst) (tst (cdr lst) n))<br />     )<br />   )<br /> )

lanjqka

2. 
   
3. ;|
   
4. _$$ (-sublst '(0 1 2 3 4 5 6) 2 3)
   
5. (2 3 4)
   
6. |;
   
7. (defun -sublst (lst i n) ;(if (catchapply (sublst lst ist iend)
   
8.   (if (null lst)
   
9.     nil
   
10.     (if (zerop i)
    
11.       (if (zerop n)
    
12.         nil
    
13.         (cons (car lst) (-sublst (cdr lst) i (- n 1)))
    
14.       )
    
15.       (-sublst (cdr lst) (- i 1) n)
    
16.     )
    
17.   )
    
18. )
    
19. 
    
20. 
    
21. ;|
    
22. _$$ (nthrm 2 '(0 1 2 3 4))
    
23. (0 1 3 4)
    
24. _$$ (nthrm 0 '("a"))
    
25. nil
    
26. |;
    
27. (defun nthrm (n lst)
    
28.   (if (null lst)
    
29.     nil
    
30.     (if (zerop n)
    
31.       (cdr lst)
    
32.       (cons (car lst) (nthrm (- n 1) (cdr lst)))
    
33.     )
    
34.   )
    
35. )
    
36. 
    
37. ;|
    
38. _$$ (ntha 2 '(0 1 2 3 4))
    
39. (0 1)
    
40. |;
    
41. (defun ntha (n lst)
    
42.   (if (null lst)
    
43.     nil
    
44.     (if (zerop n)
    
45.       nil
    
46.       (cons (car lst) (ntha (- n 1) (cdr lst)))
    
47.     )
    
48.   )
    
49. )
    
50. 
    
51. ;|
    
52. _$$ (nthb 2 '(0 1 2 3 4))
    
53. (3 4)
    
54. |;
    
55. (defun nthb (n lst)
    
56.   (if (null lst)
    
57.     nil
    
58.     (if (zerop n)
    
59.       (cdr lst)
    
60.       (nthb (- n 1) (cdr lst))
    
61.     )
    
62.   )
    
63. )
    
64. 
    
65. ;|
    
66. _$$ (nthac 2 '(0 1 2 3 4))
    
67. (0 1 2)
    
68. |;
    
69. (defun nthac (n lst)
    
70.   (if (null lst)
    
71.     nil
    
72.     (if (zerop n)
    
73.       (cons (car lst) nil)
    
74.       (cons (car lst) (nthac (- n 1) (cdr lst)))
    
75.     )
    
76.   )
    
77. )
    
78. 
    
79. ;|
    
80. _$$ (nthbc 2 '(0 1 2 3 4))
    
81. (2 3 4)
    
82. |;
    
83. (defun nthbc (n lst)
    
84.   (if (null lst)
    
85.     nil
    
86.     (if (zerop n)
    
87.       lst
    
88.       (nthbc (- n 1) (cdr lst))
    
89.     )
    
90.   )
    
91. )

<br /> ;|<br /> _$$ (-sublst '(0 1 2 3 4 5 6) 2 3)<br /> (2 3 4)<br /> |;<br /> (defun -sublst (lst i n) ;(if (catchapply (sublst lst ist iend)<br />   (if (null lst)<br />     nil<br />     (if (zerop i)<br />       (if (zerop n)<br />         nil<br />         (cons (car lst) (-sublst (cdr lst) i (- n 1)))<br />       )<br />       (-sublst (cdr lst) (- i 1) n)<br />     )<br />   )<br /> )<br /> <br /> <br /> ;|<br /> _$$ (nthrm 2 '(0 1 2 3 4))<br /> (0 1 3 4)<br /> _$$ (nthrm 0 '("a"))<br /> nil<br /> |;<br /> (defun nthrm (n lst)<br />   (if (null lst)<br />     nil<br />     (if (zerop n)<br />       (cdr lst)<br />       (cons (car lst) (nthrm (- n 1) (cdr lst)))<br />     )<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (ntha 2 '(0 1 2 3 4))<br /> (0 1)<br /> |;<br /> (defun ntha (n lst)<br />   (if (null lst)<br />     nil<br />     (if (zerop n)<br />       nil<br />       (cons (car lst) (ntha (- n 1) (cdr lst)))<br />     )<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (nthb 2 '(0 1 2 3 4))<br /> (3 4)<br /> |;<br /> (defun nthb (n lst)<br />   (if (null lst)<br />     nil<br />     (if (zerop n)<br />       (cdr lst)<br />       (nthb (- n 1) (cdr lst))<br />     )<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (nthac 2 '(0 1 2 3 4))<br /> (0 1 2)<br /> |;<br /> (defun nthac (n lst)<br />   (if (null lst)<br />     nil<br />     (if (zerop n)<br />       (cons (car lst) nil)<br />       (cons (car lst) (nthac (- n 1) (cdr lst)))<br />     )<br />   )<br /> )<br /> <br /> ;|<br /> _$$ (nthbc 2 '(0 1 2 3 4))<br /> (2 3 4)<br /> |;<br /> (defun nthbc (n lst)<br />   (if (null lst)<br />     nil<br />     (if (zerop n)<br />       lst<br />       (nthbc (- n 1) (cdr lst))<br />     )<br />   )<br /> )

q3_2006

lanjqka 发表于 2014-1-20 10:36

谢谢,学习了!

lanjqka

2. ;|
   
3. _$$ (-sub-cons-s '(0 1 2 3 4 5 6) 2)
   
4. ((0 1) (2 3) (4 5))
   
5. |;
   
6. (defun -sub-cons-s (lst n)
   
7.   (if (null lst)
   
8.     nil
   
9.     (if (< (length lst) n)
   
10.       nil
    
11.       (cons (ntha n lst) (-sub-cons-s (nthbc n lst) n)))))

;|<br /> _$$ (-sub-cons-s '(0 1 2 3 4 5 6) 2)<br /> ((0 1) (2 3) (4 5))<br /> |;<br /> (defun -sub-cons-s (lst n)<br />   (if (null lst)<br />     nil<br />     (if (< (length lst) n)<br />       nil<br />       (cons (ntha n lst) (-sub-cons-s (nthbc n lst) n)))))