CODEWITHSUNDEEP
recursionracket
kaminey
kaminey

Reputation: 23

Stuck in racket structural recursion exercise?

So I was doing some exercise after learning racket pure structural recursion(beginner). I am unable to get proper solution,

I had to Write a function, list-evens that consumes start and end, two integers where start <=end and produces a list of all even integers from start to end inclusive. For example, (list-evens −4 3) produces (list −4 −2 0 2)

So here is my code 

            ;;list-evens consumwes two integers and
            ;;produces a list of all even integers from start to end
            ;;list-evens: Int Int -> list-of-even-integers
            ;;requires: Start <= end

            (define(list-evens start end)
               (cond
                  [(= start end)(cons end empty)]
                  [else (cons start(list-evens(add1(add1 start))end))]))

     (list-evens -4 2)-->Produces (cons -4 (cons -2 (cons 0 (cons 2 empty))))

But when I change number for test like (list-evens -4 3)instead of (list-evens -4 2) then it goes on loop. And never stops.

Also (list-evens -4 2) produces (cons -4 (cons -2 (cons 0 (cons 2 empty))))It should produce(list-evens -4 -2 0 2)

Upvotes: 0

Views: 505

Answers (3)

serendipity0217
serendipity0217

Reputation: 149

(define (one first second)
  (if (> first second) empty (cons first (one (+ 2 first) second)))
)

(define (list-evens start end)
  (if (odd? start) (one (+ 1 start) end) (one start end))
)

I use cons instead of append this time because basically I want the function to return a list.

  1. (list-evens 1 1) --> (one 2 1) --> '()
  2. (list-evens 2 2) --> (cons 2 (one 4 2)) --> (cons 2 '()) --> '(2)
  3. (list-evens -4 0) --> (cons -4 (one -2 2)) --> (cons -4 (cons -2 (one (0 2))) --> (cons -4 (cons -2 (cons 0 (one 2 2)))) --> (cons -4 (cons -2 (cons 0 (cons 2 '())))) --> '(-4 -2 0 2)

Thank you ad absurdum for pointing out my mistake! I looked at Renzo's solution to get some inspirations.

Upvotes: 0

rnso
rnso

Reputation: 24535

The OPs function can be modified as follows: 

(define(list-evens2 start end (ol '()))
  (cond
    [(> start end)        ; output reversed list and end function
     (reverse ol)]

    [(even? start)        ; add start to output list and recurse with start+2
     (list-evens2 (+ 2 start) end (cons start ol))]

    [else                 ; recurse with start+1 without adding to output list
     (list-evens2 (+ 1 start) end ol)]  ))

A default argument (ol '()) is used to initiate output list.

Testing: 

(list-evens2 -4 2)
(list-evens2 -4 3)
(list-evens2 -3 3)
(list-evens2 0 3)
(list-evens2 -3 0)
(list-evens2 -3 4)

Output: 

'(-4 -2 0 2)
'(-4 -2 0 2)
'(-2 0 2)
'(0 2)
'(-2 0)
'(-2 0 2 4)

Upvotes: 1

Renzo
Renzo

Reputation: 27424

Your solution has several problems: the function should check if the starting value is even or odd; it should check for the termination not with equal, but with a greater than or greater or equal-then (otherwise the function could loop); the recursion is such that in certain cases it add a empty list at the end of the result.

Here is a possible solution:

(define (list-evens start end)
  (define (aux even-start)
    (if (> even-start end)
        empty
        (cons even-start (aux (+ 2 even-start)))))
  (aux (if (even? start) start (add1 start))))

The function uses an auxiliary function to change the starting value when it is not even; it terminates when the starting value is greater than ending value, and in this way it produces correctly the empty list when the start is greater than the end at the beginning.

Upvotes: 1

Related Questions