CODEWITHSUNDEEP
listrecursionlisp
newlearner
newlearner

Reputation: 149

How to write a recursion in lisp?

I need your huge help. I want to write a function in Lisp called rec, the function receives a list like this: (rec '(10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5)))) my code should check if the sum of the inner list is equal to the number of the outer list (5+2+2= 9 it's equal to 9, then I go further 9+9+12 = 30, 3+3+1= 5 it's equal to 5, then 5+5+4=14 it's equal to 14, 14+14+2=30 and 30 is equal to 30, at least I add 10 to 30+30 and my sum of the whole list is 70. If my sum is equal to the numbers I'll return the sum of the whole list else I'll return Nil. I hope you understand what I mean… now I want to solve it with recursion, I tried some things but I can't solve it, I hope someone can help me further...

(defun rec(list)

)

(rec '(10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5))))

Upvotes: 1

Views: 136

Answers (2)

Sylwester
Sylwester

Reputation: 48745

For me it seems like the only way this will work is if all lists has 3 elements. Lets call it triples.

(defun triplep (e)
  (and (listp e)
       (= 3 (length e)))

;; test
(triplep 5)        ; ==> nil
(triplep '(3 4 5)) ; ==> t

I don't like the name rec so I'll call it sum-triple. I'm guessing:

(sum-triple 5) ; ==> 5
(sum-triple '(3 1 1)) ; ==> 
(let ((x2 (sum-triple 1))
      (x3 (sum-triple 1))
  (if (= x2 x3)
      (+ (sum-triple 3) x2 x3)
      0))

Now to get it to return '() you need to wrap it. The first call needs to be different than all the others so that you can jump out of the helper and do something completely different at need:

(defun my-fun (x)
  (labels ((helper (x acc) ; acc here is just to show you can hold state
             ;; actual implementation that calls itself
             ;; if it finds a bad value it can short cut with
             (return-from my-fun '()))
    (helper x '())))

Upvotes: 2

coredump
coredump

Reputation: 38789

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.

Upvotes: 3

Related Questions