Home > Software engineering >  Single test recursion - how to create the "no result found" return value?
Single test recursion - how to create the "no result found" return value?

Time:11-08

I am working on a recursive function that looks for the first odd number in a list. It works as expected.

But when there is NO odd number in a list, it returns an error. Id like to control this error with some sort of message that says "no odd values found".

Single Test Recursion Function

(defun find-first-odd (x)
  (cond ((oddp (first x)) (first x))
        (t (find-first-odd (rest x)))))


(find-first-odd '(2 2 10 3 4 6 4)) ; => 3

(find-first-odd '(2 2 10 4 6 4)) ;=> value nil is not an integer


(find-first-odd '(2 2 10 4 6 4 . 2)) ;=> 2 is not type list


CodePudding user response:

You need to test for the list being empty and do the appropriate thing. In general any function which searches a list recursively needs a termination test, and thus looks something like:

(defun search-list-for (l ...)
  (cond ((null l)
         ...)
        (<(first l) is what we're after>
         ...)
        (t
         (search-list-for (rest l) ...))))

and in this case:

(defun find-first-odd (l)
  (cond
   ((null l)
    nil)                                ;or whatever
   ((oddp (first l))
    (first l))
   (t
    (find-first-odd (rest l)))))

You are lucky that, for your particular function, while (first '()) is perfectly legal in CL, it is not a number and so you get an error. In general you'll get failure to terminate:

(defun contains-thing-p/broken (l thing)
  (cond
   ((eql (first l) thing)
    t)
   (t
    (contains-thing-p/broken (rest l) thing))))

will not terminate if thing is not in the list, and must be written using the above skeleton instead:

(defun contains-thing-p (l thing)
  (cond
   ((null l)
    nil)
   ((eql (first l) thing)
    t)
   (t
    (contains-thing-p (rest l) thing))))

CodePudding user response:

Let's do it in a strange way...

First I define a function which returns the first odd number, if there is one. If there is none, then there will be an error signalled.

(defun %find-first-odd (list)
  (etypecase list
    ((cons (satisfies oddp) list) (first list))
    ((cons T list)                (find-first-odd (rest list)))))

We have types CONS, (SATISFIES ODDP), LIST and T. The first clause is selected when there is a cons cell with an odd number as its car. The second clause is selected when it is a cons cell with a list as the cdr. If none of the above clauses are selected, then there will beautomagically an error signalled.

Now I define a function calling the above. If there is an error, it signals a new error with a specific error message saying that in this specific list there is no odd number.

(defun find-first-odd (list)
  (handler-case (%find-first-odd list)
    (error () (error "No odd number found in ~a" list))))

Testing it:

CL-USER > (find-first-odd '(2 4 6))

Error: No odd number found in (2 4 6)
  • Related