Explain tail-recursive

I don't get it.

wikipedia

i meant read sicp

SICP says nothing about it.

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html#%_sec_5.4.2

Don't be retarded.

Basically, whenever a function call to itself occurs as the final instruction(s) of that function, it can be transformed into an iterative version for performance gain. These sorts of functions are called tail-recursive, as the recursion occurs at the ``tail'' of the function.

So show me an example of a Scheme function that is not til-recursive, please.

>>7
`The' standard functional wankery factorial.

The (define (fact x) if (= x 1) 1 (* (fact (- x 1)) x))? I don't see how it isn't tail-recursive.

>>9
During the last call (when x = 1) the function returns 1 to its caller, also fact, which now multiplies the result by x and so on. You can make it tail-recursive by using a counter argument.

>>9
it isnt tail recursive because fact still has to multiply the value returned by the recursive call by x, which means the stack has to be preserved.

but if you define fact to be

(define (fact n)
  (fact-iter 1 1 n))

(define (fact-iter x i n)
  (if (> i n)
      x
      (fact-iter (* i x) (+ i 1) n)
   )
)

then notice that once the recursive call returns, all fact-iter has to do is return that value. After the recursive call, fact-iter does nothing unique that it has to take up a whole stack frame. There is no reason to keep stack-iter on the call stack just to it can be immediately popped off once the recursive call returns; so it is optimized so that the the top of the call stack is replaced by the recursive call. In a sense, the interpreter is able to pop off fact-iter before it makes the recursive call to itself, this is not the case with the non-tail recursive fact, which still does work (the multiplication) after its recursive call.

tail recursive makes functions look like loops.
It's really simple, for example:


int x = 0;
while(x < 10)
  do-whatever
This is equivalent to this code

int f(int x) {
    if(x < 10) {
       do-whatever
       f(x+1);
    }
    return x;
}
(well, almost. while loops are not expresions in C)

If we look at the assembled code, the first simply jmp's if a condition is not satisfied.
The second however, even if it would be the same to jmp, it pushes elements onto the stack.

tail-recursion is the technique of simply jmp'ing instead of further pushing elements onto the stack.

read SICP

>>11
LEARN TO INDENT

>>14
Shut up, Guido.

>>15
shut up dropout

The major advantage of the tail recursion is that it operates in constant space, recursion has the disadvantage of taking a shit ton of space and can often blow the top off the stack.

It can also be significantly faster depending on how the interpreter optimization is implemented, but that isn't really the theoretical advantage.

>>17
DONT HELP HIM!!!!!!!!!!!!!!

Tail recursion is like recursion, but you get more pussy from groupies.

23 Name: Anonymous 2010-12-25 18:23

24 Name: Anonymous 2011-02-04 17:33

Newer Posts

---

Don't change these.

Name:		Email:
Entire Thread Thread List

All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -