Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
1.2, Question 4
#1
Quote:4. TQ: What kind of process does the following function implement?
   
Code:
(define (f x y z)
       (cond
           ((= x 0) (* y z))
           ((< x 5) (f y z (+ x 7))
           ((< x 10) (+ y (* 2 z) (f (- x 1) y z)))
           (else x)
           )
       )

This is a real piece of work. If I put in any x 10 or greater, I just get back x. If x is less than 10 I do I weird combinations of jumping between an expression that looks tail recursive and an expression that looks non-tail recursive. What's going on here?

*Also, does *TQ* stand for *Tough Question*?
UA ACM Vice President
ACM has bi-weekly meetings Tuesdays at 5:15pm
We're UA's best organization for CS majors (website)
Join us on Slack for all kinds of discussion channels (including one for CS403)
Reply
#2
TQ stands for trick question.
Reply
#3
Was stumped on what "TQ" meant for hours!

I think I may have an answer to the other half of your question...

The example here helped clear things up: https://stackoverflow.com/questions/3392...-recursion

I believe any time we have to "do something with the current parameters in addition to a recursive call", then the process is overall recursive since we have to "hang on" to some value in addition to the next function call.

So in this example, I believe the (< x 10) condition makes the function recursive, since we need to add "whatever y and z is right now" in addition to the next call.
If that condition wasn't there, and there was just that test for (< x 5), I believe the function would then be iterative. In such case, the value we return is solely the result of the next function call. (and now we are all done with this function call, which is why it executes in constant space)

My answer is that the function is syntactically tail and non-tail recursive, overall recursive.

Follow-up question:

Exactly what does "tail and non-tail" recursive mean? That there are some cases that exhibit an iterative function call and some that exhibit a recursive one? Wouldn't that mean that all functions with "tail and non-tail" recursion are an overall recursive procedure?
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)