递归函数在Lisp中如何工作？

Question

所以我在Lisp中编写代码，我想出了一个函数来计算列表中的原子数目（没有子列表）。所以代码是这样的：

(defun num-atoms (list) 
    (cond 
    ((null list) 0) 
    ((atom list) 1) 
    (t (+ (num-atoms (car list)) 
      (num-atoms (cdr list)))))) 

这个工作，对我有意义。所以，如果我在参数调用此函数列表(1 2 3)它应该如下：

• （NUM原子“（1 2 3））
• 没有空
• 没有原子
• 数量 - 原子（1）
• 原子所以返回1
• NUM-原子（（2 3））
• 不是null
• 不原子
• NUM-原子（2）
• 返回1
• ....
• 等

但是，如果我写这样的代码：

(defun num-atoms (list) 
    (cond 
    ((null list) 0) 
    ((atom list) 1) 
    (t (+ (num-atoms (cdr list)) 
      (num-atoms (car list)))))) 

在这里我只是在最后一行切换了de car和cdr的位置。

它仍然有效！如果我做一个跟踪，它给了我同样顺序的原子数目！它在'（1 2 3）列表中首先计算1，依此类推。 有人可以向我解释第二版的代码仍然有效吗？我真的不明白这里的逻辑。

Answer 1

如果你trace这两个函数，你会看到他们有什么不同。

在您的第一个版本中，按顺序处理原子，因为该函数处理第一个元素（car），然后处理其余元素（cdr）。

在第二个版本中，原子以相反的顺序获取进程，因为该函数在处理第一个元素之前首先处理其余元素。所以找到的第一个原子是列表中的最后一个，然后堆栈展开。

但是当然结果在两种情况下都是相同的，因为加法是commutative。

* (defun num-atoms(list) 
    (cond 
    ((null list) 0) 
    ((atom list) 1) 
    (t (+ (num-atoms (car list)) (num-atoms (cdr list)))))) 

NUM-ATOMS 
* (trace num-atoms) 

(NUM-ATOMS) 
* (num-atoms '(1 2 3)) 
    0: (NUM-ATOMS (1 2 3)) 
    1: (NUM-ATOMS 1) 
    1: NUM-ATOMS returned 1 
    1: (NUM-ATOMS (2 3)) 
     2: (NUM-ATOMS 2) 
     2: NUM-ATOMS returned 1 
     2: (NUM-ATOMS (3)) 
     3: (NUM-ATOMS 3) 
     3: NUM-ATOMS returned 1 
     3: (NUM-ATOMS NIL) 
     3: NUM-ATOMS returned 0 
     2: NUM-ATOMS returned 1 
    1: NUM-ATOMS returned 2 
    0: NUM-ATOMS returned 3 
3 

和

* (defun num-atoms(list) 
    (cond 
    ((null list) 0) 
    ((atom list) 1) 
    (t (+ (num-atoms (cdr list)) (num-atoms (car list)))))) 

NUM-ATOMS 
* (num-atoms '(1 2 3)) 
    0: (NUM-ATOMS (1 2 3)) 
    1: (NUM-ATOMS (2 3)) 
     2: (NUM-ATOMS (3)) 
     3: (NUM-ATOMS NIL) 
     3: NUM-ATOMS returned 0 
     3: (NUM-ATOMS 3) 
     3: NUM-ATOMS returned 1 
     2: NUM-ATOMS returned 1 
     2: (NUM-ATOMS 2) 
     2: NUM-ATOMS returned 1 
    1: NUM-ATOMS returned 2 
    1: (NUM-ATOMS 1) 
    1: NUM-ATOMS returned 1 
    0: NUM-ATOMS returned 3 
3 
*