CODEWITHSUNDEEP
recursionschemeracket
Josh
Josh

Reputation: 519

general recursion in scheme

I am having a bit of problems with recursion. Just want to make sure I get better. Let's say I want to see if a n number is in a list. If it is, it returns true, otherwise, false. 

(define (contains? n lst)
  (cond
    [(empty? lst) false]
    [(cons? lst)
   .....  (first lst)
      (contains? (rest lst)

the recursion part always tricks me. Is it necessary to call cons? here? Because if you are just looking for the first of a list, it isn.t

(define (contains? n lst)
  (cond
    [(empty? lst) false]
   [(= n (first lst)) true]))

(check-expect (contains? 1 (list 1 2)) true)
(check-expect (contains? 1 empty) false)

Upvotes: 0

Views: 94

Answers (1)

Óscar López
Óscar López

Reputation: 235984

No, you don't have to use cons? in the case of a list of numbers (or in general: a list of atoms): either the list is empty or is non-empty. You'd only use cons? to check if the parameter is not a list, but in general you don't have to validate this: if it isn't a list, then the function fails (as it should).

A wholly different matter happens when you have a list of lists: in that case we have to use cons? (or equvalently: pair?) to test if the first element is a list itself, and also advance the recursion over it. But for the current example, what you do have to consider, is in these three cases:

(define (contains? n lst)
  (cond
    [(empty? lst) false]              ; the list is empty
    [(= (first lst) n) true]          ; current element is the one we're looking for
    [else (contains? n (rest lst))])) ; current element is not the one, keep looking

Upvotes: 2

Related Questions