明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 750|回复: 1

[源码] 聊聊lisp递归算法

[复制链接]
发表于 2019-10-26 17:04 | 显示全部楼层 |阅读模式
本帖最后由 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),如此等等。


"觉得好,就打赏"
还没有人打赏,支持一下
发表于 2019-10-27 13:47 | 显示全部楼层
对新手来说
估计看个几遍还是懵的
以实例来分析讲解比较好
比方说“块内实体统一图层”
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2024-3-29 19:09 , Processed in 0.181910 second(s), 26 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表