problems with looping and recursion 
Author Message
 problems with looping and recursion

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")

; 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

; 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

Can someone suggest/comment where i'm going wrong?

--
Erol Asim
Computer Science Undergraduate
University of Western Ontario



Fri, 18 Apr 2003 03:52:17 GMT  
 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)



Fri, 18 Apr 2003 07:16:15 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. loop problems (recursion)

2. RECURSION RECURSION RECURSION ... AAARRGGHHHH

3. Problem with loop inside other loop

4. Tail recursion and complete recursion?

5. Memory consumption problem with recursion

6. tail recursion problem

7. problems with tree recursion.

8. Problem with recursion

9. I need help with recursion problem

10. Problem with recursion

11. RECURSION PROBLEM

12. Strange, but interesting recursion problem in PythonWin.

 

 
Powered by phpBB® Forum Software