Scheme (DrRacket) - cond statement does not work with recursion

Question

I am learning Scheme using DrRacket R5RS. I thought that I was nailing down the concepts, but I cannot get this simple recursion exercise to work. I think that it is a bug in DrRacket, but I'm not sure.

Can someone see the problem and, hopefully, explain why my code does not work? I really want to learn this functional language.

This code will produce #T and #F correctly:

(define three (lambda (L target1 target2 target3 sum)
    (cond
        ((= target1 0) (three L (car L) (cadr L) (caddr L) 0))
        ((NULL? L) (= (- sum (+ target1 (+ target2 target3))) (+ target1 (+ target2 target3))))  ; sum minus targets = targets
        (else (three (cdr L) target1 target2 target3 (+ sum (car L))))       ; return true if branch returns true
)))

When I launch the program with (three '(1 2 3 6) 0 0 0 0), it returns #T since 1+2+3=6. When I launch the program with (three '(1 2 3 5) 0 0 0 0), it returns #F since 1+2+3!=5.

Now, here is the problem. I want to do multi-branch recursion. However, this code returns #T every single time! Since I cannot get it to return #F, I cannot get it to skip to the next branch of my recursion.

(define three (lambda (L target1 target2 target3 sum)
    (cond
        ((= target1 0) (three L (car L) (cadr L) (caddr L) 0))
        ((NULL? L) (= (- sum (+ target1 (+ target2 target3))) (+ target1 (+ target2 target3))))  ; sum minus targets = targets
        ((three (cdr L) target1 target2 target3 (+ sum (car L))) #T)       ; return true if branch returns true                  
        (else 'hit_the_bottom)  ; IT NEVER HITS THIS STATEMENT!                  
)))

Any ideas?

Quick answer: replace the last line with (else #f) and it'll work. To see why, take a look at my answer below. — Óscar López

Óscar López Óscar López · Accepted Answer · 2013-04-22T01:10:43

The solution is too complicated, if you only want to check if the sum of the first three numbers in a list equals the fourth number, a simpler non-recursive approach will work better:

(define (three lst)
  (= (+ (first lst) (second lst) (third lst))
     (fourth lst)))

Other than that, why don't you stick with the first approach? it works for you, and it's not clear what do you mean with "multi-branch recursion", and why is it necessary for the second approach - isn't the first approach "multi-branch"? after all, it's already recursively calling three in two parts. Regarding the reason why the second approach is always returning #t - this line:

(else 'hit_the_bottom)

... will indeed get executed, but because it's part of a recursive call, it will get returned to this line:

((three (cdr L) target1 target2 target3 (+ sum (car L))) #t)

And the value 'hit_the_bottom is #t, so the whole procedure will return #t in the end. Be aware that in Scheme everything that is not #f is #t, and in this case in particular, 'hit_the_bottom will be interpreted as #t. Just to be clear that the else part is really being executed, run this code and you'll see 'hit_the_bottom printed on the screen exactly once:

(define three
  (lambda (L target1 target2 target3 sum)
    (cond ((= target1 0)
           (three L (car L) (cadr L) (caddr L) 0))
          ((null? L)
           (= (- sum (+ target1 target2 target3))
              (+ target1 target2 target3)))
          ((three (cdr L) target1 target2 target3 (+ sum (car L)))
           #t)
          (else (display 'hit_the_bottom) 'hit_the_bottom))))

(three '(1 2 3 6) 0 0 0 0)
=> #t
(three '(1 2 3 5) 0 0 0 0)
=> hit_the_bottom #t

Finally, to correct the second approach, replace the last line with (else #f) and it'll work as expected.

Scheme (DrRacket) - cond statement does not work with recursion

1 Answers