Wednesday 12 October 2011

Tail recursion–in detail

“The beauty of recursion is that!!.. - the beauty of recursion.”

Author speaks

  Sorry for not publishing any post nowadays. Tied up with lots of personal work. Now, would love to continue the series without gaps at least for some time. This promise is Without any GURANTEE, WARENTEE or any BONDS. :)

Metaphor

  If you catch something by tail, it tries to attack you using its head. :D

I think the below image will make you remember very well what is tail recursion.

python

Introduction

   Tail recursion is something that is more native to functional programming languages. In Maths, a tail recursive function is a function that expands itself.

Say, g(x) = f(x)

Then, tail recursion happens like this formula,        f(x) = f(g(x))

This means, f(x) = f(f(x)) = g(f(f(x)) = f(f(f(x))) … it goes on

This is purely useful for writing an mathematical logic which has a specific end condition. But this kind of recursion is majorly used in optimization of stack space in C++ and similar languages. Even some dynamic languages support this recursion type. But python doesn’t support it because of simple inherent problems for developers while using tail recursion.

Concept

   As i explained, tail recursion is mostly used for optimization & mathematical problem and widely popular in functional programming. The most and the perfect way a tail recursion works is really good for designing mathematically a computer program. But if you are normal novice software engineer, you just use this for optimization and only when its necessary because of its demerits:

  • Stack doesn’t contain any footprint of the recursion happening. Compiler tries to expand the cycling recursion into instructions without using stack
  • As there is no stack data, no way to debug such programs easily.
  • Compilers might sometime fail to make the right jumps and data corruption can never be captured.

Already developers fight with pointers when this havoc adds more headache to it.

Programmers can think tail recursion as, just processing things using arguments itself and keep the returned value as the recursive call to the function. This makes the compiler to process the return value which expands the recursive calls in the single stack frame!!

Code

#include <iostream>
 
int fib(int n)
{
    if(n==0)
        return 0;
    else if(n==1)
        return 1;
    else 
        return fib(n-1) + fib(n-2);
}
 
 
int main()
{
    std::cout<<fib(7);
    return 0;
}
  • Assembly is generated with tail optimization only when release mode is selected with Visual Studio C++.
  • You can note that there is no stack footprint by the executable created by this, by tracing the disassembly.

Conclusion

Is it good or bad? based on the need and stack space savings requirement.

2 comments:

jkff said...

I'm afraid you're seriously misunderstanding underestimating the nature and the value of tail calls (tail recursion is just a trivial special case; perhaps the *least* useful and interesting case of tail calls).

I am not sure whether this is because of the insufficiently clear formulation in your blog post (no offense, I'm not a native English speaker either, but I didn't get a clear understanding of what exactly you mean) or because you really do have some misconceptions.

Shortly speaking, a "tail call" is a function call whose continuation in the context of its caller at the time of the call is the identity function.

Speaking less formally, a tail call is when you *substitute* one computational problem with another, instead of *expressing* it in terms of another (e.g. compare binary search with computing the height of a binary tree, though both are indeed cases of tail recursion, not general tail calls).

Tail calls are useful for much more.
* Implementing state automata (used very extensively in the Erlang language), especially in a modular fashion
* Doing anything at all in continuation-passing style (which may often emerge from EDSLs, especially with asynchronous programming)
* See more in referenced blog posts.

You're also wrong in saying that tail call optimization causes loss of debugging information. Please remember that in your examples, the alternative is to use loops - in which case there is also no debugging information preserved! And besides, there *are* ways to preserve useful stack frame info with tail calls (see links).

I recommend you to read the excellent writeup on the topic here:

http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html

http://funcall.blogspot.com/2009/04/you-knew-id-say-something-part-ii.html

http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iii.html

http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iv.html

http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-v.html

vprajan said...

ooh.. this is a cool explanation about tail calls.. thanks for the links..

didn't experiment much about tail calls before writing this post. Btw, am no way near functional programming yet!!.. may be after trying out my hands in functional i will get to know the power of it.. for now blindly having this misconception.. i too read thru Guido van Rossum post to get this. :)

thanks for ur suggestions.

Post a Comment