0
votes

I have to make a function in Scheme (R5RS) that works as follow : (power-close-to b n) And it has to return a integer that I call "e" that is : b^e > n With b, e and n integers.

So if we do : (power-close-to 2 10) It has to return 4, because 4 is the first integer for which b^e > n I've made this function in an iterative way but I have to make it in an recursive form. So this is my code:

(define e 0)
(define (power-close-to b n)
  (for ((e (< (expt b e) n))
    (+ e 1))
    e))

But when I try it, Scheme gives following error : "for: undefined;" So it seems my Scheme don't know the procedure "for", but I saw it in multiple Scheme codes on the internet, so I don't understand why in my case he says he don't know "for".

Thanks for your help!

EDIT : I tried making it recursive, this is how i did it, but i think it still is iterative, and i really don't have any idea how i could make it recursive.

(define e 0)
(define (power-close-to b n)
  (if (< (expt b e) n)
    (and (set! e (+ e 1)) (power-close-to b n)) 
    e))

I also tried this, but when i try it, it never prints anything and never ends (but this is recursive (i think))

(define e 0)
(define (power-close-to b n)
  (if (< (expt b e) n)
    (* b (power-close-to b n)) 
    e))
2
You're confounding what "iterative" and "recursive" mean. In Scheme it's common to write recursive solutions, but some of those recursive solutions behave iteratively, when written as tail recursions. The first implementation in the question won't work, for doesn't exist in your interpreter - Óscar López
What Scheme implementation are you using? - uselpa

2 Answers

2
votes

When someone asks you to transform a recursive procedure in Scheme into an iterative one, it generally means that you have to use tail recursion, not that you should use the looping constructs of the language.

Notice that not all Scheme interpreters provide a for loop (most will provide a do loop, but I don't think that's the point of the exercise). The error you're reporting means that your interpreter doesn't have a for construct, so it's quite possible that you're expected to rewrite the procedure in a tail recursive fashion. I'll give you an example of what I mean, this is a recursive factorial:

(define (fac n)
  (if (zero? n)
      1
      (* n (fac (sub1 n)))))

(fac 10)
=> 3628800

Now the same procedure can be written in such a way that it generates an iterative process (even though syntactically, it still uses recursion):

(define (fac n acc) ; now the result is stored in the accumulator parameter
  (if (zero? n)     ; when recursion ends
      acc           ; return accumulator
      (fac (sub1 n) (* n acc)))) ; else update accumulator in each iteration

(fac 10 1) ; initialize the accumulator in the right value
=> 3628800

What's the point, you ask? that the second version of the procedure is written in tail-recursive form (notice that there's nothing left to do after the recursive call ends), so a compiler trick called tail call optimization kicks in and the procedure runs in constant stack space, just as efficient as a loop in other non-functional languages - making recursive calls very cheap. Now try to write your power-close-to implementation so it uses a tail call.

0
votes

What comes closest (and handiest) to the traditional loop is the named let (search for "named let" here). That would look like this:

(define (power-close-to b n)
  (let loop ((e 0))
    (if (<= (expt b e) n)
        (loop (+ e 1))
        e)))

(display (power-close-to 2 10))

The loop variable is defined at the let level, so it is local to the loop (at not global as in your example). Other than that the code looks pretty similar to yours.

A named let creates an inner function, so you could also express it as follows:

(define (power-close-to b n)

  (define (loop e)
    (if (<= (expt b e) n)
        (loop (+ e 1))
        e))

  (loop 0))

Unfortunately, R5RS does not support default values for arguments, but if you want to avoid the inner function you could go for:

(define (power-close-to b n e)
  (if (<= (expt b e) n)
      (power-close-to b n (+ e 1))
      e))

but then you'd have to call it with an additional 0 like

(power-close-to 2 10 0)