Back to Questions
1.1k
views4
comments
tail call in functional and procedural languages
f#functional

Is there a reason why F# (probably functional languages, in general) is more sensitive to stack overflows in recursive algorithms than procedural languages?

I've written recursive algorithms in: Java, C, C++, and others, and I can say that I was never mindful to make them tail recursive.

Is it just because the natural style in procedural languages lends itself to tailcall optimization? Is tailcall optimization just less necessary? Is the C optimizer better here?

.

My general notion (which is based on mostly fourth-hand information) is that

  • if the language is not functional, likely none of its compilers will ever do general tailcall elimination (and few will even eliminate the more specific case of direct tail recursion)

which means that a recursive algorithm (with enough iterations/depth) will blow the stack in every language <i>except <i>for functional languages. The rare case where people write recursive algorithms in non-functional languages involve either <UL><li>small amounts of data, or</LI><li>trees, whose height is typically log(N)</LI></UL> whereas in functional languages people will use recursion for all manner of stuff.

By on 4/23/2009 3:05 PM ()

When I asked this question, I had _no idea_ that is was such a hotly debated topic! After doing a bunch of searching around and reading some internet flamewars, I'm very thankful tail-call was included in the CLR, because it makes my life easier.

Thanks.

By on 4/24/2009 6:55 AM ()

I believe the difference resides in the fact that you use recursion in functional language in places where you use loops in procedural languages. For instance, one seldom uses recursion to iterate over a list in C, but when you do, you are very likely to run out of stack too.
Recursion is often used to iterate over nodes in a tree, and typical tree depths are often an order of magnitude smaller than that of lists.

By on 4/23/2009 1:03 PM ()

Wow, I guess I should have run a test before I assumed it was tailcall. I guess either the C stack is bigger or the frames are smaller. leading me to believe that tailcall was happening when it wasn't.

Both of these overflow in VS at less than 5000 iterations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

int recSum( int i )

{

    if( i < LIST_SIZE )

    {

        return g_list[ i ] + recSum( i+1 );

    }

    else

    {

        return 0;

    }

}

int tailRecSum( int i, int acc )

{

    if( i >= LIST_SIZE )

        return acc;

   

    return tailRecSum( i+1, g_list[ i ] );

}
By on 4/23/2009 1:54 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper