电脑编程技术1

Understand recursion using Lisp_1

Recursion can be difficult to trace at first. Start with the simplest case, the base case. Below is a simple example:

Problem: Define a function MY-LENGTH that takes one parameter, a proper list L, and returns the number of top-level elements in L. Examples (test cases):
(MY-LENGTH NIL)               → 0
(MY-LENGTH '(B (A B C)))      → 2
(MY-LENGTH '(A (((B))) C))    → 3
(MY-LENGTH '(A B C))          → 3

Solution: What is the simplest case in this problem? It is when the list L does not contain any elements. So we can define the base case:

#To define a function in Lisp, the format is (defun function_name (parameter(s)) (body_expression_list))
(defun MY-LENGTH (L)
#COND format: (COND ((conditional statement_1) return_value_or_return_expressions_1) ((c_s_2) r_v_o_r_e_1) ... (t (c_s_n) r_v_o_r_e_n))
(COND ((NULL L) 0)#if L is an empty list, returns 0
)
)

Now let's think about a slightly more difficult case, that is when the list L only has one element.
(defun MY-LENGTH (L)
(COND ((NULL L) 0)#if L is an empty list, it returns 0
#pseudocode: When L only has one element, it returns 1
)
)

But there is no built-in way to check whether L only has one element, we need to begin to think about the recursion case.
Think about the answer first; how can we go from the base case (0) to what we want (1)? It's pretty obvious that we just need to add 1, so:

1 + the base case

How to get the base case? Remember that in a recursion function, it always calls itself at least once. So:

1 + MY-LENGTH(L)

There is still a problem. This recursion does not get to the bottom or reach the base case. Once we are done with an element, or we are done with the current recursion layer, we need to let the function know that we are done by passing the rest of the elements.

So the correct version is:

1 + MY-LENGTH((CDR L))#CDR returns a new list that contains all of L's elements except the first element.

So the final function is:

(defun MY-LENGTH (L)
(COND ((NULL L) 0)
(T (+ 1 (MY-LENGTH (CDR L)))) #in Lisp, the format of calling a function is (function_name parameter(s)), so to compute 1 + 2 in Lisp is (+ 1 2).
)
)

To double-check, trace the function with simple test cases. When L is an empty list, it hits the first conditional statement and returns 0. When L has one element, it skips the first conditional statement, hits the second conditional statement ("T" in this case means "else" in Lisp), and executes (+ 1 (MY-LENGTH (CDR L))). It needs to know what (MY-LENGTH(CDR L)) is, so it first executes (CDR L), and returns an empty list. Then (MY-LENGTH empty_list) is executed, it hits the first conditional statement, and returns 0. Now (+ 1 (MY-LENGTH (CDR L))) becomes (+ 1 0); it returns 1. This function is correct.

To further check, trace the function with a list of length 2. Draw each layer mentally or physically; record the state of each layer. If a list of length 2 makes sense, the function should be correct, and the pattern should be clear.

用 Lisp 理解递归_1

递归一开始对于初学者而言通常比较难跟踪。可以先从最简单的情况——基本情况（base case）入手。下面是一个简单例子：

问题

定义一个函数 MY-LENGTH，它接收一个参数——一个规范列表（proper list）L，并返回 L 中顶层元素的个数。

示例（测试用例）：

(MY-LENGTH NIL)               → 0
(MY-LENGTH '(B (A B C)))      → 2
(MY-LENGTH '(A (((B))) C))    → 3
(MY-LENGTH '(A B C))          → 3
解题思路

最简单的情况是什么？
当列表 L 为空时（没有任何元素）。因此可以定义基本情况：

# 在 Lisp 中，定义函数的格式为：
# (defun 函数名 (参数) (函数体))

(defun MY-LENGTH (L)
   # COND 的格式：
   # (COND ((条件1) 返回值1)
   #       ((条件2) 返回值2)
   #       ...
   #       (T 默认返回值))
   (COND ((NULL L) 0)  # 如果 L 是空列表，返回 0
   )
)
递归情况的构造

接下来考虑稍微复杂一点的情况：当 L 只有一个元素时。

(defun MY-LENGTH (L)
   (COND ((NULL L) 0)  # 空列表返回 0
         # 伪代码：如果 L 只有一个元素，返回 1
   )
)

但 Lisp 没有直接判断“列表只有一个元素”的内建方法，因此我们需要用递归来解决。

递归思路

先思考结果：如何从基本情况（0）得到我们想要的结果（1）？

很明显：

1 + 基本情况

那么如何得到“基本情况”？
在递归函数中，函数会调用自身，因此可以写成：

1 + MY-LENGTH(L)

但这样有问题：递归不会收敛（不会接近基本情况）。

关键改进

每处理完一个元素，我们必须“缩小问题规模”，也就是把剩下的元素传递下去。

在 Lisp 中：

CDR 会返回去掉第一个元素后的剩余列表

所以正确写法是：

1 + MY-LENGTH(CDR L)
最终函数
(defun MY-LENGTH (L)
   (COND ((NULL L) 0)
         (T (+ 1 (MY-LENGTH (CDR L))))
         # Lisp 中函数调用格式为 (函数名 参数)
         # 例如：1 + 2 写作 (+ 1 2)
   )
)
验证函数

情况 1：空列表

直接命中 (NULL L)，返回 0

情况 2：一个元素的列表

不满足第一个条件，进入 (T ...)
计算：(+ 1 (MY-LENGTH (CDR L)))
(CDR L) 返回空列表
(MY-LENGTH NIL) → 0
最终结果：(+ 1 0) → 1

✔ 函数正确

进一步验证

可以用长度为 2 的列表手动跟踪执行过程：

逐层展开递归
记录每一层的状态（可以画图或写下来）

如果长度为 2 的情况能正确理解，那么这个递归模式基本就掌握了。