RECURSION

LISP has this feature that allows a command to call itself. It is a method of using a result to prove or define itself.

Suppose that we want to make a function, and we call EXIST. It tells us if one atom a is in one list l, it implies that the function is going to have two parameters.

The implementation of the function can be done with some interactive control structure, but now we are going to try to do it with recursion.

The general idea will be to check if the atom is in the CAR of the list l, otherwise check if the atom a exists in the CDR of the list l.

Notice that here we just define the cases that we have to take care of:

If the atom is equal to the CAR of the list l.
If the atom is not equal to the CAR of the list l and is in the CDR of the list
If the atom is not in the list l.

This is one of the basics of defining a recursive function: first of all, you have to define all the different cases of the function.

Now, for each of those cases, define the solution, starting with the easy cases. Also, in each step suppose that the function can solve all the other cases, so you can use the function to define the solution of this case.

First case If the atom is the CAR of the list l.
Result = TRUE.
Second case if the atom is in the CDR of the list l.
Result = TRUE.
Notice that we know that we can use the function EXIST to check if the atom is in the CDR of the list l. The most important part is not to forget to advance at least one step into the solution.
Third case if the atom is in the CDR of the list l and is not equal to the CAR of the list l.
Result = FALSE.

If we express that in a natural language, the solution will look like:


FUNCTION EXIST ( a , l ) =
  if a = (CAR l)
     Return TRUE
  else
     if EXIST ( a  (CDR l) )
        Return TRUE
     else
        Return FALSE.

If we implement it in LISP, the best control structure that we have (at this point) is the COND and we are going to use it to implement the function:


(DEFUN EXIST ( a l )
    (COND 
         ((equal a (CAR l))    t)
         (  t)
         (ELSE                nil)))

INVOCATION:



= 
Answer (If you give up!)

It could be the way the function come out of our mind (maybe not!) but you can factor it out in such way that we have only two cases:

First case If the atom is the CAR of the list l.
Result = TRUE.
Second case if the atom is in the CDR of the list l.
Result = (EXIST a (CDR l)).

And it will look like:


FUNCTION EXIST ( a , l ) =
  if a = (CAR l)
     Return TRUE
  else
     Return EXIST ( a  (CDR l) )
     /* that return TRUE if a EXIST in the CDR of l */
     /* or FALSE otherwise                          */

try to implement it with this change:

Another example. Now we need to write a function to delete all the occurrences of an atom a in a list.

First of all, define the cases:

The atom is equal to the CAR of the list. Result = CDR of the list.
The atom is not equal to the CAR of the list. Result = CONS atom with the DELETE of the CDR of the list.

Expressing it in a pseudo-natural language will look like this.


FUNCTION DELETE ( a , l ) =
  if a = (CAR l)
     Return (CDR l)
  else
     Return  (CONS a  (DELETE a (CDR l)) )


(DEFUN DEL ( a l )
    (COND 
         (        )
         (        ) ))

(DEL 'sins '(the capital sins of everyday life) )

INVOCATION:

= 
Answer (If you give up!)

Again, it is not completely well done, because it does not take care of the null, nor does it take care of the situation when it does not receive an atom as a parameter.

try to include that part to the function and prove it.




(DEFUN DEL ( a l )
    (COND 
         (        )
         (        )))

(DEL 'sins   '(the capital sins of everyday) )
(DEL 'sins   '() )
(DEL '(sins) '(the capital sins of everyday) )

= 
Answer (If you give up!)