Programming Forums - Anyone a genius?

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Coder's Corner Lounge (http://www.programmingforums.org/forum11.html)

- - Anyone a genius? (http://www.programmingforums.org/showthread.php?t=15820)

Fall Back Son

May 12th, 2008 5:10 PM

Anyone a genius?

linearly recursive functions can always be transformed into tail recursive functions.

Then disprove ^. After hours of scouring the intrawebs, I am no closer to any hope of answering that question. In fact, most of the websites I encountered contradict each other. But I can rattle off the advantages and disadvantages of each, and how modern compilers should implement ways to get rid of tail recursion. And yes, this is homework.

Fall Back Son

May 13th, 2008 4:00 PM

Re: Anyone a genius?

You are. I see you viewing this.

Jimbo

May 13th, 2008 8:48 PM

Re: Anyone a genius?

"linearly recursive functions" is a term I'm not familiar with. Is this a special form of recursive functions, similar to how tail recursive functions are?

Fall Back Son

May 14th, 2008 9:18 PM

Re: Anyone a genius?

A linearly recursive function is one in which one recursive call is made, but the function that makes the recursive call has to wait to return its value. One example would be if the return looked like

n * ICalledMyselfAgain();

In the above example, the function cannot immediately return because it has to wait for its recursive call to return so that it can multiply by n. This takes up more stack space the more recursive calls are made.

Tail recursion only makes one recursive call, like linear recursion. But the return value in tail recursion is the result... there is no other operation on it. So tail recursion would look like

ICalledMyselfAgain();

grumpy

May 15th, 2008 4:47 AM

Re: Anyone a genius?

Not quite so, Fallback Son. Tail recursion simply means that the last operation in a function is a call to itself. So;

int CallMySelfAgain(int i)

{

    if (SomeResult(i))

         return some_value;

    return CallMySelfAgain(SomeTransformation(i));

}

is tail recursive.

derzok

May 15th, 2008 10:10 AM

Re: Anyone a genius?

After having just completed two semesters of Scheme programming, I can tell you that it is indeed possible to transform any algorithm into Tail-Recursion if you use the Continuation Passing Style algorithm.

http://lambda-the-ultimate.org/node/2673#comment-40136

Notes from one of my class's lectures:

; Basics:

; - initial value of k is (lambda (v) v)

; - apply k to base case value

; - new value of k is (lambda (v) (k (doSomething v)))

; - Imagine that the result of your recursive call (say, for n-1) is v.  

;   What should be done to get the proper result for this call (say, for n)?

;   That's what "doSomething" is.



(define length-cps

  (lambda (ls)

    (let loop ((ls ls)

               (k (lambda (v) v)))

      (if (null? ls)

          (k 0)

          (loop (cdr ls)

                (lambda (cdrLen) (k (add1 cdrLen))))))))

Fall Back Son

May 15th, 2008 10:55 AM

Re: Anyone a genius?

Quote:

Originally Posted by grumpy (Post 145205)

Not quite so, Fallback Son. Tail recursion simply means that the last operation in a function is a call to itself. So;

int CallMySelfAgain(int i)

{

    if (SomeResult(i))

         return some_value;

    return CallMySelfAgain(SomeTransformation(i));

}

is tail recursive.

I was trying to indicate that tail recursion means there are no "pending operations" (mult, add, printing something, whatever else) on a recursive call after it returns. But you are right to clear up the misleading examples.

Also, I'm glad you gave that example in particular, I never considered whether a linearly recursive function which calls another function can always be written tail recursively. But I imagine those can also.

Fall Back Son

May 15th, 2008 10:59 AM

Re: Anyone a genius?

Quote:

Originally Posted by derzok (Post 145217)

; Basics:

; - initial value of k is (lambda (v) v)

; - apply k to base case value

; - new value of k is (lambda (v) (k (doSomething v)))

; - Imagine that the result of your recursive call (say, for n-1) is v.  

;   What should be done to get the proper result for this call (say, for n)?

;   That's what "doSomething" is.



(define length-cps

  (lambda (ls)

    (let loop ((ls ls)

               (k (lambda (v) v)))

      (if (null? ls)

          (k 0)

          (loop (cdr ls)

                (lambda (cdrLen) (k (add1 cdrLen))))))))

This is interesting. From all indications, any function can be written tail recursively. But my professor indicated that there are cases where this is impossible. I have been unable to find any so far. His exact wording was that "oftentimes linear recursion can be changed to tail recursion" which doesn't explicitly say its not always possible, but it does hint at it. Hmm.

derzok

May 15th, 2008 1:45 PM

Re: Anyone a genius?

Like I said, all recursive algorithms can be written in continuation passing style - which is similar to tail recursion (and often achieves the same effects in terms of efficiency). Not everything can be written in straight tail recursion (that I know of). There's a whole field of study called Lambda Calculus - it's used to prove attributes of algorithms like this.

http://en.wikipedia.org/wiki/Lambda_calculus

Fall Back Son

May 15th, 2008 5:32 PM

Re: Anyone a genius?

No... your first post said that it is possible to transform any algorithm into tail recursion using CPS. Your second post said its possible to transform any algorithm into something "similar" to tail recursion using CPS. Those are different. Also, from my study of CPS, I vaguely recall it saying that CPS transforms linear recursion into tail recursion THEN into iteration. So this would indicate that your first post was, in fact, correct.

All times are GMT -5. The time now is 12:51 AM.