前几天，碰到一个题目，因为是racket的练习，很自然的，就是关于递归的。

题目要求实现一个名为lenlen的函数，这个函数的数学定义是下面这样的：

1
2
3

LenLen(0) = 1
LenLen(1) = 2
LenLen(n) = digsum(n) + LenLen(n-1) + len(LenLen(n-1)) + len(len(LenLen(n-1)))

其中，digsum函数是数值n的每位数字之和，len函数是数值n的位数。

对于racket的函数实现，题目提出了性能要求，如果不能在合理时间内完成4位数的计算， 则判定为性能不达标。另外，题目给出了2个已知的结果，lenlen(123456)=3643889， lenlen(123457)=3643919。很显然，这是在暗示具体的实现要能跑通这2条结果。

要实现lenlen，首先要实现digsum和len。相对来说，len实现起来更简单， 先写这个，然后再实现digsum和lenlen。

len函数

这个函数，可以通过检索字符串长度实现，可以写作下面这样：

1
2

(define (len n)
  (string-length (number->string n)))

digsum函数

要实现这个函数，首先就得把数值n的每位数字提取出来，然后才能进行相加。 提取数字，可以通过转换为字符串来实现。因为题目要求不得使用apply、map之类的高阶函数， 所以，求和也只能用递归来实现。

先来写求和函数，可以写作下面这样：

1
2
3
4

(define (mysum lst)
  (cond
    [(null? lst) 0]
    [else (+ (string->number (car lst)) (mysum (cdr lst)))]))

有了求和函数，digsum基本上就算完成了：

1
2

(define (digsum n)
  (mysum (explode (number->string n))))

而之所以不用lambda，也是因为题目不允许使用。

lenlen函数

有了digsum和len之后，写lenlen就很简单了，可以写作下面这样：

1
2
3
4
5
6

(define (lenlen n)
  (cond
    [(zero? n) 1]
    [(= 1 n) 2]
    [else
       (+ (digsum n) (lenlen (- n 1)) (len (lenlen (- n 1))) (len (len (lenlen (- n 1)))))]))

是不是很简单？

只是，上述代码在跑(lenlen 10)的时候，就会卡顿，在这种情况下，验证123456的值肯定是不可能的。 好在，题目后面也给了提示，说应该使用local。那就加上local再试试呗。

加了local之后，上述代码可以写作下面这样：

1
2
3
4
5
6
7

(define (lenlen n)
  (cond
    [(zero? n) 1]
    [(= 1 n) 2]
    [else
     (local [(define n1 (lenlen (- n 1)))]
       (+ (digsum n) n1 (len n1) (len (len n1))))]))

再跑一遍(lenlen 10)，几乎是瞬间就有了结果，看来疗效不错。 跑一下123456，也可以在三五秒的时间内，给出与前文一致的准确结果。 由此看来，使用local保存中间结果，十分有必要。

如果再增加一个临时变量，储存len的中间结果呢？

1
2
3
4
5
6
7
8

(define (lenlen n)
  (cond
    [(zero? n) 1]
    [(= 1 n) 2]
    [else
     (local [(define n1 (lenlen (- n 1)))
             (define n2 (len n1))]
       (+ (digsum n) n1 n2 (len n2)))]))

测试下来，好像又变快了一点点。

autolisp能否跑得通题目中的2条测试呢？

因为在Dr racket里边跑1条测试，需要好几秒的时间，就想着试试autocad 的lisp环境， 看看会不会更快一点。

要用autolisp来跑，代码就要稍微改造一下，可以写作下面这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

(defun mysum  (lst)
  (cond 
	((null lst) 0)
	(t (+ (atoi (chr (car lst))) (mysum (cdr lst))))))

(defun digsum (n) (mysum (vl-string->list (itoa n))))

(defun len (n) (strlen (itoa n)))

(defun lenlen  (n / n1 n2)
  (cond 
	((zerop n) 1)
	((= 1 n) 2)
	(t
	 (setq n1 (lenlen (1- n))
		   n2 (len n1))
	 (+ (digsum n) n1 n2 (len n2)))))

在autocad 2012的visual lisp ide中进行测试，跑1234和12345，都是瞬间就给出结果了， 和dr racket的运行速度一样快。然而，很遗憾，123456是跑不通的，提示堆栈溢出了。

经过十几次的测试，发现上述代码能跑通的最大值是19973，跑19974就会溢出。

由此看来，autocad的lisp运行时，性能确实不咋的啊，堂堂一款商业软件，连人家一个教学平台都不如。