聊聊lisp递归算法
本帖最后由 1291500406 于 2019-10-27 15:28 编辑递归是重复完成相同工作的有效方法。SHORTEN函数所用的是递归，其中包括一行LISP码，这行码使SHORTEN在它自身内部又发生一次。换句话说，SHORTEN执行中的一部分涉及再次执行SHORTEN，例如：
(DEFUN SHORTEN(l)
(COND((NULL l) NIL)
(T (PRINT l)
(SHORTEN (CDR l)))))←
当程序运行，LISP求值器到达箭头所示的那行末尾时，已经建立了这个函数的一种新版本。这种新版本的自变量不同于输入数据。当求值器在新的SHORTEN中达到相同点时，同样的事情再次发生。如此重复，直到某一点，最后一行建立一个以空表作为自变量的SHORTEN的新版本。在最后这个循环中，不能达到箭头所指这点，因为COND把求值器引向NIL或什么也不做的指令。为便于说明，我们试对这个函数输入一个很短的表：
(SETQ ANIMALS '(DOG CAT MOUSE))
在数据已经减少为NIL的循环中，机器不需要做什么。下一步机器所要做的工作是结束所有那些被部分地完成了的SHORTEN版本，并且回到最高层。为了使这个过程更清楚一些，我们把这个函数改写为：
(DEFUN SHORTEN(l)
(COND((NULLl)NIL)
(T(SHORTEN(CDR l))
(PRINT l))))
在这种情况下，1不是在每个向前的循环中被打印，而是留到CONS已最终结束递归后再打印。所以，首先打印只留下一个元素的那个版本的1，因为当1中只留下一个元素时，1的CDR是NIL。这样，在下一个被打印的1版本中有两个元素，如此继续，直到整个表为止。
举例
Fib(0) = Fib(1) = 1
Fin(n) = Fib(n-1) + Fib(n-2)
(defun fib (n)(if (<= n 1)1(+ (fib (- n 1))(fib (- n 2)))))
如果你计算(fib 10)，那么函数就会计算(fib 9) 和(fib 8)。
计算(fib 9)，它必须又一次计算(fib 8)，如此等等。
对新手来说
估计看个几遍还是懵的
以实例来分析讲解比较好
比方说“块内实体统一图层”
页:
[1]