Tail Recursion

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Tail Recursion

Postby M.qrius » Wed Apr 16, 2008 6:00 pm UTC

[Topic split from here]

bridge wrote:But this is relative to the language you're using, for example tail recursion is not supported by all languages

If I'm not mistaken, tail recursion is 'supported' by any language that has loops and functions. Which is basically any language which is useful to code in.

On an unrelated note: I like how you can tail-recurse quicktime to reduce the maximum recursion depth from n to log(n).

User avatar
bridge
Posts: 195
Joined: Sun Feb 03, 2008 2:24 pm UTC
Location: Zurich < x < Rome

Re: suggestions for computer science books

Postby bridge » Wed Apr 16, 2008 6:14 pm UTC

M.qrius wrote:
bridge wrote:But this is relative to the language you're using, for example tail recursion is not supported by all languages

If I'm not mistaken, tail recursion is 'supported' by any language that has loops and functions. Which is basically any language which is useful to code in.

C/C++ tail recursive? i don't think so...

Edit: also Java and Ruby are not tail recursive, to name two
Excuse my Super Mario accent

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: suggestions for computer science books

Postby M.qrius » Wed Apr 16, 2008 6:26 pm UTC

bridge wrote:
M.qrius wrote:
bridge wrote:But this is relative to the language you're using, for example tail recursion is not supported by all languages

If I'm not mistaken, tail recursion is 'supported' by any language that has loops and functions. Which is basically any language which is useful to code in.

C/C++ tail recursive? i don't think so...

Edit: also Java and Ruby are not tail recursive, to name two

I may not know a lot of languages, but take java:

Code: Select all

public string func(){
  if(condition) return "something";
  //do stuff
  return func();
}

Can be rewritten as:

Code: Select all

public string func(){
  while(!condition){
    //do stuff
  }
  return "something";
}

My point being that tail recursion is not something that is in the language, but something you build yourself.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: suggestions for computer science books

Postby EvanED » Wed Apr 16, 2008 6:33 pm UTC

bridge wrote:C/C++ tail recursive? i don't think so...

What sort of crappy compiler are you using? Tail recursion is a standard optimization even for C and C++.

To illustrate:

Code: Select all

3060. ~/delete : cat delete.c
int x;

void overflow()
{
  x = 6;
  overflow();
}

int main()
{
  overflow();
}
3061. ~/delete : gcc delete.c
3062. ~/delete : ./a.out
zsh: segmentation fault  ./a.out    <--- as expected... stack overflow
3063. ~/delete : gcc -O2 delete.c
3064. ~/delete : ./a.out         
                                    <--- no stack overflow, because program is an infinite loop


We can see this if we look at the generated code:

Code: Select all

overflow:
        pushl   %ebp
        movl    %esp, %ebp
.L3:
        jmp     .L3              <--- *

Hey, that's a loop on the starred line, not a function call.

(Incidentally, if the global variable x and assignment to it aren't present, either GCC bugs out or takes advantage of laxness in the standard and produces "incorrect" code that simply exits:

Code: Select all

overflow:
        pushl   %ebp
        movl    %esp, %ebp
        popl    %ebp
        ret
)

Edit: I *was* going to say that we can even show this with sort of the traditional example of turning a non-tail-recursive function into a tail-recursive one:
Spoiler:

Code: Select all

#include <stdio.h>

int fact_r(int n)
{
  if(n == 0) return 1;
  return n * fact_r(n-1);
}

int fact_tr_aux(int n, int accum)
{
  if(n == 0) return accum;
  return fact_tr_aux(n-1, n*accum);
}

int fact_tr(int n)
{
  return fact_tr_aux(n, 1);
}

int main()
{
  for(int i=0 ; i<10 ; ++i) {
    printf("%d!=%d by fact_r and %d by fact_tr\n", i, fact_r(i), fact_tr(i));
  }
  return 0;
}


Except that looking at the assembly GCC -O2 produces for fact_r:
Spoiler:

Code: Select all

fact_r:
        pushl   %ebp
        movl    $1, %eax
        movl    %esp, %ebp
        movl    8(%ebp), %edx
        testl   %edx, %edx
        je      .L6
        .p2align 4,,7
.L5:
        imull   %edx, %eax
        subl    $1, %edx
        jne     .L5                 <--- loop, not recursion
.L6:
        popl    %ebp
        ret

shows that not only did it make fact_tr_aux tail-recursive, but it made fact_r tail-recursive also! (This surprises even me, and is actually a little annoying for illustration purposes. ;-) With -O1 it doesn't do any tail recursion.)

Rysto
Posts: 1460
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: suggestions for computer science books

Postby Rysto » Wed Apr 16, 2008 7:01 pm UTC

gcc only optimizes simple cases of tail recursion. For example, the following code overflows the stack:

Code: Select all

void recursive2(int a);

void recursive1(int a, int b)
{
    x = 5;
    recursive2(5);
}

void recursive2(int a)
{
    x = 6;
    recursive1(4, 5);
}

int main(int argc, char ** argv)
{
    recursive1(3, 4);

    return 0;
}


So basically gcc's implementation is a microoptimization that you can't depend on in useful code.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Tail recursion

Postby EvanED » Wed Apr 16, 2008 7:05 pm UTC

In fairness to GCC, that is mutual recursion between two functions. Can you show an example of a single tail-recursive function that you think GCC "should" be able to pick up but it doesn't?

User avatar
bridge
Posts: 195
Joined: Sun Feb 03, 2008 2:24 pm UTC
Location: Zurich < x < Rome

Re: suggestions for computer science books

Postby bridge » Wed Apr 16, 2008 7:35 pm UTC

Tail recursion: if the last statement of a function is a function call, then the stack record of the caller routine is reused for the called routine

Code: Select all

fun() {
  switch(...) {
    case x:
      //do something
      fun_r1();
    case y:
      //do something else
      fun_r2();
  }
}

funr_r1() {
  //do something
  fun_r2();
}

funr_r2() {
  //do something else
  fun();
}

A language that can execute this in an infinite loop allocating not more than 1 stack record is tail recursive
Anything else is not.

GCC may be able to transform some single-function recursive calls into a loop but this is a totally different story IMO

Edit: i'm actually curious on how gcc would handle that.. EvanED?

@M.qrius: recursion != tail recursion
Excuse my Super Mario accent

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: suggestions for computer science books

Postby M.qrius » Wed Apr 16, 2008 8:56 pm UTC

bridge wrote:@M.qrius: recursion != tail recursion

My example kinda sucked, but yeah :P My point was kind of that even for languages without built-in compiler tail recursion, you can always do it yourself. For some advanced forms, like properly tail-recursing quicksort, you have to do it yourself.

User avatar
bridge
Posts: 195
Joined: Sun Feb 03, 2008 2:24 pm UTC
Location: Zurich < x < Rome

Re: suggestions for computer science books

Postby bridge » Wed Apr 16, 2008 9:13 pm UTC

M.qrius wrote:even for languages without built-in compiler tail recursion, you can always do it yourself

Sorry but no, you can't.
You have to find a way to avoid recursion (for, while, etc) or accept that your function will grow very inefficiently on the stack
Excuse my Super Mario accent

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: suggestions for computer science books

Postby M.qrius » Wed Apr 16, 2008 9:25 pm UTC

bridge wrote:
M.qrius wrote:even for languages without built-in compiler tail recursion, you can always do it yourself

Sorry but no, you can't.
You have to find a way to avoid recursion (for, while, etc) or accept that your function will grow very inefficiently on the stack

Since when does a while loop make your stack grow?

Could you give me an example where it is impossible to do it yourself?

User avatar
bridge
Posts: 195
Joined: Sun Feb 03, 2008 2:24 pm UTC
Location: Zurich < x < Rome

Re: suggestions for computer science books

Postby bridge » Wed Apr 16, 2008 9:40 pm UTC

M.qrius wrote:Since when does a while loop make your stack grow?
Could you give me an example where it is impossible to do it yourself?

I said that you need to use a while/for loop if you want to be stack efficient.

An example? The pseudo code i gave above.
The call stack will grow to infinity in any non-tail recursive language.
While in a tail-recursive language (i.e. Erlang) it will always use a single stack entry
Excuse my Super Mario accent

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: suggestions for computer science books

Postby EvanED » Wed Apr 16, 2008 9:48 pm UTC

Editing because I figured something out. Blue text is added.

bridge wrote:A language that can execute this in an infinite loop allocating not more than 1 stack record is tail recursive
Anything else is not.
You're still getting language and implementation confused. Some languages (read: Scheme) make a statement about tail recursion and an implementation that doesn't do that optimization isn't compliant with R#RS. Most languages are silent on the issue. I don't know any that prohibit it by edict. And it wouldn't be impossible to write a compiler that does Scheme-quality tail call elimination for C. (You just would have to be sure that you don't optimize away stack frames that the program may pass pointers to the callee.)

Edit: i'm actually curious on how gcc would handle that.. EvanED?


Modified slightly to (1) actually compile and (2) not trigger the GCC "bug" and (3) adding a 'break' after the first case in the switch, I mentioned above, GCC appears to optimize all but one of the tail calls.

Code: Select all

void funr_r2();
void funr_r1();

// I don't want other optimizations (const propagation) to interfere with the tail call, hence the volatile
volatile int x;

void fun() {
  switch(x) {
    case 1:
      //do something
      x = 1;
      funr_r1();
      break               <------  added at the edit
    default:
      //do something else
      x = 1;
      funr_r2();
  }
}

void funr_r1() {
  x = 1;
  funr_r2();
}

void funr_r2() {
  x = 1;
  fun();
}

int main() {
  fun();
  return 0;
}


Assembly:

Code: Select all

funr_r2:
        pushl   %ebp
        movl    %esp, %ebp
        popl    %ebp
        movl    $1, x
        jmp     fun                  <--- not call

funr_r1:
        pushl   %ebp
        movl    %esp, %ebp
        popl    %ebp
        movl    $1, x
        jmp     funr_r2        <--- not call

fun:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        movl    x, %eax
        subl    $1, %eax
        je      .L10            <--- this is the switch(x)
        movl    $1, x          <--- this is the default branch (calls funr_r2)
        leave
        jmp     funr_r2       <--- not call
.L10:
        popl    %ebp         <--- this is case 1: in the switch
        movl    $1, x
        jmp     funr_r1      <--- not call


// the following was the original code before I figured out I was missing a break
.L10:
        movl    $1, x          <--- case 1
        call    funr_r1        <--- call instead of jmp; this is not treated as a tail call
        movl    $1, x          <--- ?!
        leave
        jmp     funr_r2        <--- ?!


I have no clue why the call to funr_r2() within fun() was not optimized. I'm sure it has to do with the fact that there is an extra movl after the call (as that's an operation after the function return), but I have no idea WTF that is doing there. I also have no idea what is going on with the leave then jmp. (leave doesn't return, just resets the stack and frame pointers.)

Okay, so in case it isn't clear now, the call that wasn't being optimized away before was the call to funr_r1, not funr_r2 like I said above. It wasn't being optimized away because after it returns, control fell through into the default case, where it set x to 1 again and called funr_r2 (which was being optimized).

BTW, this is all done with -O2 with GCC version 4.1.2.

User avatar
M.qrius
Rainbow Brite
Posts: 519
Joined: Sat Nov 10, 2007 12:54 am UTC
Location: Rainbow's end
Contact:

Re: suggestions for computer science books

Postby M.qrius » Wed Apr 16, 2008 9:50 pm UTC

bridge wrote:I said that you need to use a while/for loop if you want to be stack efficient.

Ah, okay, I read is as if you meant the fors and whiles were the recursion (ambiguity! We should use lojban! Except I don't know that).
But do you not agree then that what you are doing has the same effect as what the compiler is doing, but on a higher level than the compiler?

Prepost-edit: Except doing what you did with the psuedocode would be a bit more complex and ugly. But still possible.

Edit: Nevermind, I give up :) I guess you can't use my way when there's not actually a loop, but merely calling one function at the end of another once. That would be tail recursion as well, right?

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Tail Recursion

Postby Berengal » Thu Apr 17, 2008 7:16 am UTC

Not sure if it would technically be recursion (recursion being a function that is defined in terms of itself), but it should be possible to optimize away the same way tail recursion is. I don't have gcc in front of me right now, so I wouldn't be able to test it, but try:

Code: Select all

int func1(int arg){ return func2(arg + 1);}
int func2(int arg){return arg + 1;}
Or something similar. This could easily be rewritten as a series of goto statements, and it should therefore be possible to optimize away the call.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
evilbeanfiend
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: suggestions for computer science books

Postby evilbeanfiend » Thu Apr 17, 2008 7:29 am UTC

M.qrius wrote:
bridge wrote:
M.qrius wrote:even for languages without built-in compiler tail recursion, you can always do it yourself

Sorry but no, you can't.
You have to find a way to avoid recursion (for, while, etc) or accept that your function will grow very inefficiently on the stack

Since when does a while loop make your stack grow?

Could you give me an example where it is impossible to do it yourself?


see, the thing here is that doing it yourself isn't the same as having tail recursion optimization, if it was then any turing tarpit could be said to have the features of any other programming language, this is simple not a useful measure of a language if all programming languages are equal. or do you write all your code in asembler?
in ur beanz makin u eveel

User avatar
bridge
Posts: 195
Joined: Sun Feb 03, 2008 2:24 pm UTC
Location: Zurich < x < Rome

Re: suggestions for computer science books

Postby bridge » Thu Apr 17, 2008 7:36 am UTC

EvanED wrote:You're still getting language and implementation confused.

I was just trying to be simple, i know it's an implementation thing. You could find a tail-recursive Java VM, in practice i don't think it exists.
EvanED wrote:

Code: Select all

void funr_r2();
void funr_r1();

void fun() {
  switch(x) {
    case 1:
      //do something
      x = 1;
...


Ok, you're right gcc can figure out tail recursion optimizations, i should have looked up before saying it doesn't

M.qrius wrote:Calling one function at the end of another once. That would be tail recursion as well, right?

It is if your compiler/interpreter/whatever does optimize it in stack terms, then it is. Otherwise it's just normal recursion.
In Erlang, the requirement for the T.R. to apply is that the last statement of a function is a call from which we expect no return value, in other languages/implementations this may be different

Factorial example (Erlang)

Code: Select all

% BAD! Non tail-recursive
fact(N) ->
  N * fact(N-1).

% GOOD! Tail recursive
fact(N) ->
  rec_fact(N, 1).

rec_fac(1, Partial) ->
  Partial;
rec_fac(Left, Partial) ->
  rec_fac(Left-1, (Partial*Left)).
Excuse my Super Mario accent

User avatar
bridge
Posts: 195
Joined: Sun Feb 03, 2008 2:24 pm UTC
Location: Zurich < x < Rome

Re: Tail Recursion

Postby bridge » Thu Apr 17, 2008 1:35 pm UTC

(Sorry for the double-post but editing 6 hours later does not seem a good idea, also since the edit would be bigger than the original message :mrgreen:)

@EvanED
Actually my pseudocode and your implementation were a little simplistic, no callee was using values returned,
all functions were arguments and return-value free.
Sure this is easy to compile for gcc as a series of jump.

I tried to progressively modify until the point it not able to tail-recurse

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int funr_r1(int x, int y);
int funr_r2(int x, int y, int z);

int get_random() {
   return (int)random() % 100;
}

// I don't want other optimizations (const propagation) to interfere with the tail call, hence the volatile
volatile int x;

int fun(int n) {
   printf("n is %d\n", n);
   int x = get_random();
   int y = get_random();
   // printf("%d\n", x);

   if (x < 50) {
         //do something
      return funr_r1(x, y);
   } else {
         //do something else
      int z = get_random();
      return funr_r2(x, y, z);
   }
}

int funr_r1(int x, int y) {
   int n = x + y;
   return funr_r2(x, y, n);
}

int funr_r2(int x, int y, int z) {
   int n = x+y+z;
   return fun(n);
}

int main() {
   return fun(0);
}

gcc is not able to do tail-recursion on that
(gcc tr.c -c -S -O2)

Code: Select all

_fun:
   ...
   call   L9

L9:
   ...
   jg   L4              <--first if branch
   ...
   call   _funr_r1   <--'else' if branch

L4:
   ...
   call   _funr_r2

_funr_r2:
   ...
   jmp   _fun

_funr_r1:
   ...
   call   _funr_r2

as you can see the only call executed as jump is from 'fun_r2' to 'fun' but this won't prevent the stack to grow.
Erlang handles that same code without problems,
that's why i initially said C is not a tail recursive language and i'm still convinced that this is true.
Excuse my Super Mario accent

rabuf
Posts: 15
Joined: Thu Mar 20, 2008 2:30 pm UTC

Re: Tail Recursion

Postby rabuf » Thu Apr 17, 2008 8:23 pm UTC

Recursive functions are functions defined in terms of themselves. Tail recursion is a special case where the recursive call is the last operation in the instruction. C/C++/Java all allow for tail recursion. What their compilers may not do is optimize those into iterative routines rather than recursive routines for the benefits described above, but that doesn't mean the languages do not have tail recursion.

User avatar
bridge
Posts: 195
Joined: Sun Feb 03, 2008 2:24 pm UTC
Location: Zurich < x < Rome

Re: Tail Recursion

Postby bridge » Thu Apr 17, 2008 10:03 pm UTC

tail recursion:
A function is tail recursive if it either
  • returns a value without making a recursive call, or
  • returns directly the result of a recursive call.
All possible branches of the function must satisfy one of these conditions.
http://www.stanford.edu/class/cs242/rea ... ulary.html


I agree you can do that in basically any language.

However the code you write is not exactly the same code executed (both C and Java)
So what looks tail recursive at language level, may not be at execution level.
Excuse my Super Mario accent


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests