递归 — 从斐波那契数列的Lisp求法开始

yxp

收集和总结一下递归的用法，不足之处请大家指正。
从下面例子可以看出递归的算法如同数学归纳法，在函数内部会一直倒推至n=0（1）的值，如果不能收敛(缺少递归结束条件)，就会出现堆栈溢出。因此对于短表尚可，长表运行效率较低。


斐波那契数列也叫黄金分割数列，从第三项开始值为前两项之和 '(1 1 2 3 5 8 13 21 34 55)
递归1，求斐氏数列第n项值
示例:  (Fib 12)  返回 144
(defun Fib(n)(if (and (> n 0)(< n 3)) 1 (+ (Fib (- n 1))(Fib (- n 2)))))


递归2，删除L表中的重复元素
示例: (delSame '(1 3 2 4 2 3 5))   返回 (1 3 2 4 5)
(defun delSame (L) (if L (cons (car L) (delSame (vl-remove (car L) L)))))


递归3，删除L表的前n个元素
示例: (delFnth 3 '(1 2 3 4 5 6))   返回 (4 5 6)
(defun delFnth (n L)(if (= n 0) L (delFnth (1- n) (cdr L))))


递归4，返回L表的前n个元素
示例: (getFnth 3 '(1 2 3 4 5 6))   返回 (1 2 3)
(defun getFnth (n L)(if (= n 0) nil (cons (car L) (getFnth (1- n) (cdr L)))))


递归5，删除L表的第n个元素
示例：(Delnth 2 '(1 2 3 4 5 6)  返回 (1 2 4 5 6)
(defun Delnth (n L)(if (= n 0)(cdr L)(cons (car L) (Delnth (1- n) (cdr L)))))


递归6，更新L表的第n个元素va
示例: (Renth 0 2  '(1 2 3 4 5 6))  返回 (1 2 0 4 5 6)
(defun Renth (va n L)(if (= n 0)(cons va (cdr L))(cons (car L) (Renth va (1- n) (cdr L)))))


递归7，插入元素va到L表的第n位
示例: (Insnth 0 2 '(1 2 3 4 5 6))  返回 (1 2 0 3 4 5 6)
(defun Insnth (va n L)(if (= n 0)(cons va L) (cons (car L) (Insnth va (1- n) (cdr L)))))


其他组合应用，例如：返回L表的m到n位，不分m，n的大小
示例: (getList 2 4 '(1 2 3 4 5 6))  返回 (3 4 5)
(defun getList(m n L)(getFnth (+ (abs (- m n)) 1) (delFnth (min m n) L)))

想想数学归纳法，递归的结构就会比较清晰，对表其他递归操作可以此类推。
对表的操作基本上都以 n=0，或者空表作为递归结束条件，以 1- 或 cdr 作为循环条件，循环语句的结构极其简单，且与 n=0 时的结构相同；
从n开始调用自身，当满足 n=0 条件时，便不再循环调用自身；
大部分递归结构都可以用循环算法代替。

以上递归基本是调用组合 cons、car、cdr 函数，所以对于短表操作效率还是很高的。
据说，nth 函数本身就是 car 和 cdr 内部函数的递归表达式。相当于：
(defun Xnth (n L)(if (= n 0)(car L)(Xnth (1- n) (cdr L))))
测试: (Xnth 3 '(1 2 3 4 5 6)) 返回 4
简单吧。再比如
(defun Xlength (L)(if L (1+ (Xlength (cdr L))) 0))
结束条件为空表，返回0，否则返回 1+
测试: (Xlength '(1 2 3 4 5 6))  返回 6

如果你看懂了，可以试着写一下：
1 求自然数L表前n个元素之和
  如 (nSum 3 '(7 24 12 11 2 5)) 返回 43
2 在L表中间隔插入va值
  如 (InsV '(1 2 3 4 5) "a") 返回 (1 "a" 2 "a" 3 "a" 4 "a" 5)

ll_j

递归是个很值得研究的问题，理论上使用递归很简单，但往往使用不好，就造成堆栈溢出。
现在关于递归还有一个“尾递归”的概念，就是为了解决堆栈问题，道理看似很清楚，想用却并不容易，楼主部分也顺便研究一下。

twsyzx

这么好的文章,看到的晚了

浮起让更多的人受益

zhqdh

确实是好东西,先收藏,打起了精神再学习.

shiyan001

我用递归2的方法（delSame ）处理点表时怎么进入死循环，跳不出来。

zhongys

好文章，学习。

pannelchen

我是做题的:

; 求自然数L表前n个元素之和
  ;如 (nSum 3 '(7 24 12 11 2 5)) 返回 43
(defun nsum(n l) (if (= n 0) 0        (+ (car l) (nsum (1- n) (cdr l)))))

;在L表中间隔插入va值
; 如 (InsV '(1 2 3 4 5) "a") 返回 (1 "a" 2 "a" 3 "a" 4 "a" 5)
(defun insv(l va) (if (> (length l) 2) (cons (car l) (cons va  (insv (cdr l) va))) (cons (car l) (cons va (cdr l)))))

004

递归1
(and (> n 0)(< n 3))
改成 (and (< n 3) (> n 0))  因为一般输入都是大于3的,就不需要判断>0了
写成(< 0 n 3) 会好看点

004

全凭测试出来的..难啊.
(defun nSum (n lst)
  (if (= n 1)
    (car lst)
    (+ (car lst) (nSum (1- n) (cdr lst)))
  )
)
(nSum 3 '(7 24 12 11 2 5))

(defun InsV (lst va)
  (if (cdr lst)
    (cons (car lst) (cons va (InsV (cdr lst) va)))
    (list (car lst))
  )
)
(InsV '(1 2 3 4 5) "a")