How do recursive functions work in Lisp?

Question

So I'm coding in Lisp and I came up with a function that counts the number of atoms in a list (with no sub-lists). so the code is this:

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

and this works and makes sense to me. So if I call this function with the list (1 2 3) in argument it should go as follows:

(num-atoms '(1 2 3))
not null
not atom
num-atoms(1)
atom so returns 1
num-atoms ((2 3))
not null
not atom
num-atoms (2)
return 1
....
and so on

BUT, if I write the code like this:

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

here I just switched de car and cdr positions in the last line.

It still works ! and if I do a Trace, it gives me the number of atoms in the same order ! it counts the 1 first in the '(1 2 3) list and so on. Can someone explain to me how this 2nd version of the code still works ? I dont really understand the logic here.

Not an answer, but, you should be aware that (count-if #'atom …) would do this. FWIW. — BRPocock
– BRPocock, Commented Nov 2, 2015 at 16:25
@BRPocock As far as I see, that is wrong. count-if would count all top-level atoms in a sequence, whereas his version counts all atoms in a tree. — Frank Zalkow
– Frank Zalkow, Commented Nov 3, 2015 at 7:32
I'm assuming “list with no sub-lists” to not be a tree, but, point taken. — BRPocock
– BRPocock, Commented Nov 10, 2015 at 21:31

uselpa · Accepted Answer · 2015-11-01 14:45:39Z

4

If you trace both functions you'll see how hey differ.

In your first version, the atoms get processed in order because the function processes the first element (car) and then the remaining elements (cdr).

In the second version, the atoms get processes in reverse order because the function first processes the remaining elements before processing the first element. So the first atom that is found is the last in the list, and then the stack unwinds.

But of course the result is the same in both cases since addition is 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

and

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

edited Nov 1, 2015 at 14:45

answered Nov 1, 2015 at 13:57

uselpa

19k2 gold badges36 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Pedro Costa Over a year ago

thanks for your answer ! i understand what u tried to explain to me, it all makes sense now. What really confused me was how the lisp processed the code ( the order) but i think i got it now !

Collectives™ on Stack Overflow

How do recursive functions work in Lisp?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related