2

I am learning recursion and was reading about head and tail recursion. It is told that head recursion does recursive call first and then does the calculation on the result. The tail recursion on the other hand does all the processing before doing the recursive call first.

The head recursion can reduce the data passed to the recursive calls, while the tail recursion can result in passing additional data to the recursive calls.

So, basically I want to know is there any benefit I get by using one over another? and how to get to know which one is used in a given function.

AFAIK the below power function (defined for whole numbers) is using head recursion:

def power(num, exponent):
  if exponent <= 1:
    return num
  else:
    return num * power(num, exponent-1)

Note:

The real reason we would use recursion is for a simple way of storing values on a 'path' for future use. Recursion store's the state of the algorithm at each level and allows the user to come back to that exact state later on. We will see this in use when using the tree traversal routines.

It will be good if someone can shed some light on the above statement as I perceive it as a very important for getting a deeper insight.

CodeYogi
  • 1,352
  • 1
  • 18
  • 41
  • 1
    Possible duplicate of [What is tail recursion?](http://stackoverflow.com/questions/33923/what-is-tail-recursion) – Ian Mercer Oct 19 '15 at 05:46
  • In Python's case, trying out tail recursion wouldn't do any good b/c it does not support it and, according to [this SO](https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion), it never will. – code_dredd Oct 19 '15 at 05:48
  • 1
    @IanMercer I think my question is quite different I have already defined what a tail and head recursion is. I am asking when one is preferred over other in general. – CodeYogi Oct 19 '15 at 06:14
  • The thing about tail recursion is, if tail call optimization is involved, the interpreter does NOT record the state of the algorithm as soon as it reaches the return line, and it does NOT record this because it does NOT need to. – lingxiao Oct 19 '15 at 06:29
  • @IanMercer I don't see it as a duplicate question at all. Please see the question details before flagging it, it may cause a possibly good question to remain unanswered. – vivek Oct 19 '15 at 06:46
  • Try reading the *answers* that explain in depth both forms of recursion and how tail recursion can be optimized. – Ian Mercer Oct 19 '15 at 07:01
  • Or see this http://stackoverflow.com/questions/21426688/the-difference-between-head-tail-recursion?lq=1 which is itself a duplicate. – Ian Mercer Oct 19 '15 at 07:03
  • @IanMercer hmm, you see I am not asking what is `xx` but rather why `xx`? – CodeYogi Oct 19 '15 at 07:25
  • Which is answered there: tail recursion is better because some compilers can optimize it and eliminate a stack frame. And your example is tail recursion not 'head' recursion - the recursive call to `power` is the last thing in the function. "Head recursion" is itself a rather ill-defined term: there's "tail recursion" and "recursion". Whether your call is at the top, or in the middle doesn't matter, but being at the tail does. @CodeYogi – Ian Mercer Oct 19 '15 at 07:39
  • @IanMercer you seem to be quite confused, the power function is not tail recursive in any way. The call to the `power` function is not the last thing in the function call (after call the result needs to be multiplied by num). Please correct your theory before doing any comments. – CodeYogi Nov 21 '15 at 05:33

1 Answers1

0

There is this thing called tail call optimization which is important for functional programming. I think for that one you need tail recursion. But then for python it's like blah blah. Although just for argument sake it looks probable that head recursion could be transformed into tail recursion.

Head:

def power(num, exponent):
    if exponent <= 1:
        return num
    else:
        temp = power(num, exponent-1)
    return temp*num

Tail:

def power(num, exponent,init = 1):
    if exponent <= 1:
        return num*init
    else:
        init = num*init
    return power(num, exponent-1, init)

If this is always possible and if the interpreter is smart enough, as far as optimization is concerned, it shouldn't matter which recursion you do.

lingxiao
  • 1,214
  • 17
  • 33