Recursive function in Scheme

Question

I need to make a recursive function that takes an object and a vector and returns a list of all the objects that preceded my object parameter.

I did it using iteration like this:

(define (precedes obj vec)
  (do ((i 1 (+ i 1))
      (list '() (if (eqv? obj (vector-ref vec i))
            (cons(vector-ref vec (- i 1)) list)
            list)))
    ((= i (vector-length vec)) list))
)

but I'm having a lot of trouble trying to figure out how to do the same thing using recursion. I'm confused how I can keep incrementing through the vector as I recursively call. So far, all I have is this:

(define (precedes2 obj vec)
  (define list '())
  (if (eqv? obj (vector-ref vec i))
      (cons(vector-ref vec(- i 1)) list)
      list)))

I figured I would use the same logic I used before in terms of the if statement, but I'm not sure how to now call the same function with the updated vector. Any help would be great.

Joshua Taylor · Accepted Answer · 2014-11-16 00:53:54Z

2

You're in the interesting position of moving from an iterative implementation to a recursive one; usually people go in the other direction. Fortunately, moving from a do-loop to recursion is pretty easy. In general, a do loop can be rewritten as follows:

(do ((i i-init i-step)
     (j j-init j-step)
     ...)
    (test result)
  body)

becomes

(define f (i j ...)
  (cond
    (test result)
    (else body (f i-step j-step ...))))

(f i-init j-init ...)

That translation is usually written using a named let, though:

(let f ((i i-init)
        (j j-init)
        ...)
  (cond
    (test result)
    (else body (f i-step j-step ...))))

So (and I haven't tested the code) your original function

(define (precedes obj vec)
  (do ((i 1 (+ i 1))
      (list '() (if (eqv? obj (vector-ref vec i))
            (cons(vector-ref vec (- i 1)) list)
            list)))
    ((= i (vector-length vec)) list))
)

would turn into

(define (precedes obj vec)
  (let loop ((i 1)
             (list '()))
    (cond
      ((= i (vector-length vec)) list)
      (else (loop (+ i 1)
                  (if (eqv? obj (vector-ref vec i))
                      (cons (vector-ref vec (- i 1)) list)
                      list))))))

answered Nov 16, 2014 at 0:53

Joshua Taylor

86.2k9 gold badges164 silver badges379 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ganda Over a year ago

Thank you for the details on the logic as well. Really helped me understand the language a lot better. Only just started coding in Scheme like 2 weeks ago.

Joshua Taylor Over a year ago

@Ganda As I mentioned at the beginning, this is a rather interesting case because it's often easier to write the recursive version, and then (in Common Lisp, which doesn't necessarily have tail call elimination) write a version using do. It's less common to go in the other direction, I think.

Collectives™ on Stack Overflow

Recursive function in Scheme

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related