Programming Forums > Community Forums > Coder's Corner Lounge

Fall Back Son · May 12th, 2008, 5:10 PM

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

You are. I see you viewing this.

Jimbo · May 13th, 2008, 8:48 PM

"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

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

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

(Toggle Plain Text)

int CallMySelfAgain(int i)
{
    if (SomeResult(i))
         return some_value;
    return CallMySelfAgain(SomeTransformation(i));
}

is tail recursive.

derzok · May 15th, 2008, 10:10 AM

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:

(Toggle Plain Text)

; 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

Quote:

Originally Posted by grumpy

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

(Toggle Plain Text)

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

Quote:

Originally Posted by derzok

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:

(Toggle Plain Text)

; 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

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

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.

May 12th, 2008, 5:10 PM	#1
Fall Back Son Hobbyist Programmer Join Date: Oct 2006 Posts: 203 Rep Power: 2	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.

May 13th, 2008, 4:00 PM	#2
Fall Back Son Hobbyist Programmer Join Date: Oct 2006 Posts: 203 Rep Power: 2	Re: Anyone a genius? You are. I see you viewing this.

May 13th, 2008, 8:48 PM	#3
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 748 Rep Power: 3	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? __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

May 14th, 2008, 9:18 PM	#4
Fall Back Son Hobbyist Programmer Join Date: Oct 2006 Posts: 203 Rep Power: 2	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();

May 15th, 2008, 4:47 AM	#5
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,198 Rep Power: 5	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; (Toggle Plain Text) int CallMySelfAgain(int i) { if (SomeResult(i)) return some_value; return CallMySelfAgain(SomeTransformation(i)); } int CallMySelfAgain(int i) { if (SomeResult(i)) return some_value; return CallMySelfAgain(SomeTransformation(i)); } is tail recursive.

May 15th, 2008, 10:10 AM	#6
derzok Newbie Join Date: Jan 2008 Posts: 3 Rep Power: 0	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: (Toggle Plain Text) ; 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)))))))) ; 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))))))))

May 15th, 2008, 1:45 PM	#9
derzok Newbie Join Date: Jan 2008 Posts: 3 Rep Power: 0	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

May 15th, 2008, 5:32 PM	#10
Fall Back Son Hobbyist Programmer Join Date: Oct 2006 Posts: 203 Rep Power: 2	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.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Falling Ball (Game) Using C and Allegro	CIRCLE	Show Off Your Open Source Projects	10	Sep 20th, 2007 10:00 AM
I need a math genius to help me	sagedavis	Other Programming Languages	17	May 5th, 2007 12:08 PM

Programming Forums > Community Forums > Coder's Corner Lounge

Anyone a genius?