23. Head and Tail Recursion

You now understand that recursion is the process by which a function calls itself during execution.

Further to this there are two types of recursion called 'head' and 'tail' recursion.

Tail Recursion

This is when the last statement in the function calls itself. An example is the factorial function we used earlier.

  fct(n) {
     if  (n==0) {
     fct = 1
 } else {
     fct = n * fct(n-1)
   }
 } 

The last statement

fct = n * fct(n-1)

is calling itself. This is 'tail' recursion.

Advantage of tail recursion

The advantage of writing a tail-recursive function is that the compiler can convert it into ordinary loop code - so avoiding the use of the stack.

Head Recursion

This is when the first statement in the function calls itself. Having to do this forces the use of the stack, but sometimes this is the only way to write a particular recursive function.