CODEWITHSUNDEEP
recursionschemetail-recursion
Henrik Hillestad Løvold
Henrik Hillestad Løvold

Reputation: 1301

Turn tail-recursive/iterative procedure into a fully recursive procedure

I am currently writing a simple program in Scheme which adds numbers together recursively and without using the + operator. Right now I have this program which does what I want to do:

(define (add1 x) (+ x 1))

(define (sub1 x) (- x 1))

(define (plus x y) 
  (if (zero? y)
      x
      (plus (add1 x) (sub1 y))
      )
  )

However, my tutor has asked me to drop the tail recursion/iteration and write the plus procedure fully recursive. Without telling me too much (this is, after all, a Uni exercise), can you point me in the right direction to figure out how to do that?

Thanks in advance!

Upvotes: 1

Views: 83

Answers (1)

Óscar López
Óscar López

Reputation: 236122

I agree with the comments, it's a silly exercise - your answer is quite fine as it is, it's already a tail-recursive solution, which is more efficient than the solution requested by the instructor (which is also recursive, but not tail recursive. Calling it fully recursive is a misnomer). Anyway, here's a hint:

(define (plus x y)
  (if (zero? y) ; the first part remains unchanged
      x
      <???>))   ; now, what do we put here?

You have to add1 at each recursive step, the idea is that you keep adding 1 exactly y times, and in the end you add this to x. Let me show this with an example, to add 4 plus 3 we do this:

(plus 4 3)

Which expands to this:

(add1 (plus 4 2))
(add1 (add1 (plus 4 1)))
(add1 (add1 (add1 (plus 4 0))))
(add1 (add1 (add1 4)))

In the above, 4 was bound to x and 3 to y at the beginning, and after executing the program we see that add1 was called three times, the first time we add 1 to 4, then 1 to 5 and finally 1 to 6, until we obtain 7. In other words: the recursive step must call add1 to the result of recursively invoking plus, where x remains unchanged and y is decremented by one unit until it reaches zero, and at this point we reach the base case and the recursion unwinds returning the correct result.

Upvotes: 2

Related Questions