How to implement the function will be easier once you clarify what needs to be done.
Input
Your input is a list, but not any kind of list.
Let's name that particular kind of list a node.
A node is either an empty list, or a list of 3 elements (v n1 n2), where:
- v is a number,
- n1 (resp. n2) is either a node or a number.
Output
When you call rec on a node, it should output either a number, or nil.
Outline
Let's define an auxiliary num function that takes either a number or a node and returns either a number or nil, by calling rec:
(num n) for a number n should return n(num n) for a node n should return (rec n)
Then, rec can be defined as follows:
(rec nil) should be nil(rec (v n1 n2)) should return (+ v (num n1) (num n2)), when (num n1) and (num n2) are equal numbers. In any other case, rec should return nil.
Example
The following is one possible way of implementing it, and relies on operators like local function definitions (FLET), switching based on a value's type (TYPECASE) and early return techniques. See also DESTRUCTURING-BIND. The use of logical operators (and/or) is useful to combine possible NIL intermediate results:
(defun rec (node)
(flet ((num-or-fail (n)
(or (typecase n
(number n)
(cons (rec n)))
(return-from rec))))
(and node
(destructuring-bind (v n1 n2) node
(let ((v1 (num-or-fail n1))
(v2 (num-or-fail n2)))
(and (= v1 v2)
(+ v v1 v2)))))))
In the REPL (command-line), you can activate tracing for rec:
CL-USER> (trace rec)
And then you can test:
CL-USER> (rec '(10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5))))
The above returns 70 and prints the following trace in SBCL:
0: (REC (10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5))))
1: (REC (12 (5 2 2) 9))
2: (REC (5 2 2))
2: REC returned 9
1: REC returned 30
1: (REC (2 14 (4 (3 1 1) 5)))
2: (REC (4 (3 1 1) 5))
3: (REC (3 1 1))
3: REC returned 5
2: REC returned 14
1: REC returned 30
0: REC returned 70
Early return can even escape from the outermost call since it implies the whole result is NIL (a bit like an exception). You could make rec a local function too, mutually recursive with num-or-fail, and name your main function differently:
(defun sumtree (node)
(labels ((num-or-fail (n)
(or (typecase n
(number n)
(cons (rec n)))
(return-from sumtree)))
(rec (node)
(and node
(destructuring-bind (v n1 n2) node
(let ((v1 (num-or-fail n1))
(v2 (num-or-fail n2)))
(and (= v1 v2)
(+ v v1 v2)))))))
(rec node)))
Here above, when one of the intermediate result is nil, the return-from unwinds the whole stack of recursive calls and directly returns nil.
