0

Hey i've been stuck on the following problem and cant seem to come up with the correct function.

Write a recursive function that, given a positive integer k, computes the product k: (1-1/2)(1-1/3)(1-1/k)... as k decreases by one.

I cant seem to come up with the correct function i the program usually runs till it has no more memory left. Here is my method:

(define (fraction-product k)
  (if (= k 0)
       0
       (* (- 1 (/ 1 (fraction-product (- k 1)))))))

thanks for any help in advance...

3 Answers 3

1

Do small cases by hand first.

Without trying to code it, hand-calculate what the answer should be for:

  • (fraction-product 1)
  • (fraction-product 2)
  • (fraction-product 3)

You should at least have three concrete examples in hand before you do these kinds of problems: not only does it help to clarify some confusion, but they can serve as sanity test cases when you get to actual code.

Is there a relationship between the answer you hand calculate between (fraction-product 1) and (fraction-product 2)? How about between (fraction-product 2) and (fraction-product 3)?

Do we have to worry about (fraction-product 0)? Check your problem statement.

Don't go straight to code when you see problems like this. Do small examples by hand first: compute what the answer should be. It will help kickstart your intuition on what the program is really trying to compute, and how to do it mechanically.

If you have time, see a book like How to Design Programs, which describes a systematic approach on designing these kinds of functions.

0

What are the arguments of the product? There is only one! The product is therefore useless, since (* n) == (* n 1) == n. This should tell you immediately that your algorithm doesn't do what you want.

A good strategy to find such bugs is to write all the parameters of function of separate lines…

Also, when k == 0, (fraction-product 0) returns 0. Then (fraction-product 1) will compute (/ 1 (fraction-product 0)) == (/ 1 0) which is probably not what you want to do again…

Actually, it seems that you want to compute something completely different from a product of fractions… rather a recursive fraction (I forgot the name of such things).

Anyway, to do (1 - 1/2) * (1 - 1/3) * ... * (1 - 1/k) you could do something like

(define (f-p k)
  (define (aux n) (- 1 (/ 1 n)))
  (let loop ((i 2))
    (if (> i k)
      1 ;; base case: multiply by 1, i.e. "do nothing"
      (* (aux i) (loop (+ i 1))))))

This can be optimised to use constant stack space, but it isn't the point, is it?

0

You got wrong the base case: it should state that if k is 1, then return 1 - when you're multiplying recursively you have to make sure that the recursion stops when the number 1 is reached, if you multiply by 0 the result will always be 0.

The recursive call is also mistaken, notice that you must multiply (- 1 (/ 1 k)) times the result of the recursion. Try something like this:

(define (fraction-product k)
  (if (<= k 1)
      1
      (* (- 1 (/ 1 k))
         (fraction-product (- k 1)))))

As suggested in @Axioplase's answer, the same procedure can be written in such a way that it uses constant stack space by using tail recursion - the recursive call is the last thing the procedure executes before returning and is thus in tail position:

(define (fraction-product k)
  (let loop ((acc 1)
             (k k))
    (if (<= k 1)
        acc
        (loop (* acc (- 1 (/ 1 k))) (- k 1)))))

And just for fun, it's easy to realize that the same procedure can be written as simple as this:

(define (fraction-product k)
  (/ 1 k))
2
  • There is no need to convert a tail-recursive function to an iterative function: The Lisp interpreter does that automatically.
    – Eyal
    Commented Sep 11, 2012 at 6:50
  • @Eyal but anyway you have to write the recursion in such a way that it uses a tail call, the first version of the procedure above will not be automatically transformed to the second one. And the second one is not an iterative function, is a tail-recursion written using a named let. Commented Sep 11, 2012 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.