Lets review some recursion types.
- Tail Recursion: A call is tail-recursive if nothing has to be done after the call returns. I.e. when the call returns, the returned value is immediately returned from the calling function. More simply, tail recursion is when the recursive call is the last statement in the function. See Tail Recursion.
- Head Recursion: A call is head-recursive when the first statement of the function is the recursive call.
- Middle or Multi Recursion: A call is mid-recursive when the recursive call occurs in the middle of the function. I.e. there are other statements before and after the recursive call. If one or more of these statements is another recursive call, then the function is multi-recursive. There is no essential difference between Head Recursion, Middle Recursion and Multi Recursion from the standpoint of efficiency and algorithm theory.
- Mutual Recursion: Function X and Y are called mutually-recursive if function X calls function Y and function Y in turn calls function X. This is also called indirect recursion because the recursion occurs in two steps instead of directly. See Mutual Recursion.