[解決済み] Lispで再帰関数はどのように動作するのですか？

質問

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-atoms '(1 2 3))
• nullでない
• not atom
• num-atoms(1)
• アトムなので1を返す
• num-atoms ((2 3))
• nullでない
• not atom
• num-atoms (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が最初にカウントされ、以下同様です。 どなたか、この2番目のバージョンのコードがどのように動作するのか、説明していただけませんか？このロジックは本当に理解できません。

どのように解決するのですか？

もし、あなたが トレース の2つの関数がどのように異なるかがわかると思います。

最初のバージョンでは、この関数は最初の要素 ( car )、そして残りの要素( cdr ).

2番目のバージョンでは、関数はまず最初の要素を処理する前に残りの要素を処理するため、アトムは逆の順序で処理されます。つまり、最初に見つかったアトムはリストの最後となり、その後、スタックが巻き戻されます。

しかし、足し算はあくまで足し算なので、結果はもちろんどちらも同じです。 可換 .

* (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
*