Nested square root recursion

Question

Let's assume you have the following numerical output pattern for a function

(function 0) = sqrt(6)

(function 1) = sqrt(6 + (2 * sqrt(7)))

(function 2) = sqrt(6 + (2 * sqrt(7 + (3 * sqrt(8)))))

etc...

In scheme I have the following recursive function to calculate this pattern

(define (function depth)
    (cond
        ((= depth 0) (sqrt 6))
        (else (+ (function (- depth 1)) (* (+ depth 1) (sqrt (+ depth 6)))))
        )
    )

I can't figure out how to write the else case so that the square root is nested. Can someone give me a suggestion?

Óscar López · Accepted Answer · 2014-09-15 04:08:19Z

3

The formula is a bit tricky to implement, but this should work using a named let (this is just for avoiding the creation of another procedure):

(define (function n)
  (let helper ((a 2))
    (if (= (- a 2) n)
        (sqrt (+ a 4))
        (sqrt (+ a 4 (* a (helper (+ a 1))))))))

If the named let bothers you, here's a completely equivalent solution, using a nested helper procedure:

(define (function n)
  (define (helper a)
    (if (= (- a 2) n)
        (sqrt (+ a 4))
        (sqrt (+ a 4 (* a (helper (+ a 1)))))))
  (helper 2))

If nested procedures are also a problem, then extract the helper as a completely independent procedure:

(define (helper a n)
  (if (= (- a 2) n)
      (sqrt (+ a 4))
      (sqrt (+ a 4 (* a (helper (+ a 1) n))))))

(define (function n)
  (helper 2 n))

Anyway, the results are as expected:

(function 0)
=> 2.449489742783178

(function 1)
=> 3.360283116365224

(function 2)
=> 3.724280930782559

edited Sep 15, 2014 at 4:08

answered Sep 15, 2014 at 3:30

Óscar López

237k38 gold badges321 silver badges391 bronze badges

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

5 Comments

user3277752 Over a year ago

This is a wonderful solution, but I should have added I need to avoid using assignments or loops as well.

Óscar López Over a year ago

@user3277752 the solution is not using loops, only recursion. I edited my answer to make it more explicit

user3277752 Over a year ago

How would you convert this to an iterative process?

Óscar López Over a year ago

@user3277752 That's tricky for this case. We would have to convert the recursive call into a tail recursion. My guess is that it's possible, but it's not obvious how.

Óscar López Over a year ago

@user3277752 another possibility would be using continuation-passing style, which can turn any recursive process into an iterative process. Again, it'll be a bit tricky to implement and harder to understand

uselpa · Accepted Answer · 2014-09-15 10:40:52Z

0

Here's how I would implement it. Compared to @Oscar's version

it covers erroneous input values of n (Oscar's solution will loop indefinitely for negative values)
has no redundant expression

Code:

(define (function n)
  (if (negative? n)
      (error "n is negative")
      (let recur ((n n) (a 1))
        (if (= -1 n)
            0
            (* a (sqrt (+ a 5 (recur (sub1 n) (add1 a)))))))))

Testing:

> (for ((i (in-range 10))) (printf "~a ~a\n" i (function i)))
0 2.449489742783178
1 3.360283116365224
2 3.7242809307825593
3 3.8777446879222386
4 3.9447403174010236
5 3.9746786776817733
6 3.988278318778271
7 3.994530823306873
8 3.997431999017166
9 3.998787961199304

> (function -2)
n is negative

answered Sep 15, 2014 at 10:40

uselpa

19k2 gold badges36 silver badges53 bronze badges

Collectives™ on Stack Overflow

Nested square root recursion

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related