CODEWITHSUNDEEP
recursionscheme
user_163417
user_163417

Reputation: 101

Intermediate recursive function value in Scheme

Suppose we want to implement the following recursive function in Scheme:

f(n) = f(n-1) + 1/f(n-1) [n>0] f(n) = 1 [n=0]

A simple way to this is by something like this:

(define (f n) (if (zero? n) 1 (+ (f (- n 1)) (/ 1 (f (- n 1))))))

But, as (f (- n 1)) subexpression is repeated, this code is not that much elegant. Is there any way to improve this code by binding a name to this intermediate value?

Note that a let construct can't be used here, as theoretically this causes the function to recurse forever. Practically it causes an Scheme error.

UPDATE:

Here is my code with let:

(define (afunc s n)
    (if (> n 0)
        (* .5
            (let ((next (afunc s (- n 1)))
                (+ next (/ s next))))
                s)))

It breaks with an Ill-formed special form: (let (... ...)) error.

Upvotes: 0

Views: 65

Answers (1)

chriopp
chriopp

Reputation: 957

You are on the right track, let does not impose a problem, the following works as expected.

(define (f n)
  (if (zero? n)
      1
      (let ((next (f (- n 1))))
        (+ next (/ 1 next)))))

Upvotes: 2

Related Questions