problems with looping and recursion

Quote:

> I'm trying to filter out odd numbers in a list while keeping the even

> numbers. I'm trying to do this in two implementations; using iteration

> (loop) and recursion.

> (require-library "functio.ss")

You don't need this library for this elementary problem.

Quote:

> ; recursion - problem: won't return the list

> (define filter1 (lambda (l)

> (cond (

> ((odd? (first l)) remove (first l) l) ; if the

> first element is odd, remove it

> (filter1 rest (l)) )) )) ; call filter1 with all

> the elements except the first

First you got your parentheses wrong. Before first, try to think

recursively:

1) Removing all odd element of the empty list should return the empty list.

2) Removing all odd elements of a list whose first element is odd, is

obtained filtering the list of the remaining elements.

3) Removing all odd elements of a list whose first element is even, is

obtained by consing this even element to the list obtained by filtering the

list of remaining elements.

Your function should therefore have three cond alternatives:

(cond

((empty? l) empty) ; first (this one you missed)

((odd? (first l)) ...) ; second

(else ...)) ; third

The function should not modify the original list, I think, e.g:

(define some-list '(1 2 3 4 3 2 1))

(filter some-list) ---> (2 4 2))

some-list ---> (1 2 3 4 3 2 1) ; not affected.

Quote:

> ; iterative - problem: when it gets to the 5th iteration, the index no

> longer exists

> (define filter2 (lambda (list)

> (do ((c 0 (+ c 1))) ; do loop

> ((= c (length list)) ; perform until eof list

> ((odd? (list-ref list c)) (remove (list-ref list c)

> list) list))))) ; if odd, remove index position of list

It seems to me that you think in terms of imperatives that modify objects

such as lists. Try to forget that for a while. Remove does not remove any

element from a list. It returns a copy of the list while leaving out one

element. The original list is not affected. Anyway, you should not use

remove for homework like this. You might try to write remove yourself. It

looks pretty much the same (3 cond alternatives (else included)). Its like

(add1 x): it does not change the value of x. It uses the value of x to

compute another value, which is returned as the value of the expression.

(define x 3)

(add1 x) --> 4; just like (+ x 1) --> 4, but very unlike x:=x+1

x --> 3 ; not affected

I suggest that you forget about using a loop for this problem. The recursive

solution is simpler. By the time you master recursion, you might consider to

write loops. Furthermore, loops are nice for vectors, but on lists they have

the {*filter*} property of reversing the order:

(define reverse-list

(lambda (lst)

(do

((the-list lst (cdr the-list))

(result empty (cons (car the-list) result)))

((null? the-list) result))))

(reverse-list '(a b c d)) ---> (d c b a)

Recursion does not show this problem:

(define copy-list ; (for flat lists only)

(lambda (lst)

(cond

((empty? lst) empty)

(else (cons (first lst) (copy-list (rest lst)))))))

(copy-list '(a b c 1 2 3 a b c)) --> (a b c 1 2 3 a b c)

By the time you master both recursion and loops, you may consider to use

imperatives like set!, set-car! and set-cdr! for in situ modifications of

objects in imperative style. Austere recursive programming is much simpler

than you may think, very much simpler than set! and the like, which tend to

modify the behaviour of code all over the place, particularly where you dont

expect it. Hope this helps and does not sound too didactical:)

I like looping, provided its high up in an aeroplane.

Jacob J. A. Koot (Jos)