Types of Recursion

TYPES OF RECURSION

Recursion is a technique that breaks a problem into one or more sub-problems that are similar to the original problem. Any recursive function can be characterized based on:

• whether the function calls itself directly or indirectly (direct or indirect recursion),

• whether any operation is pending at each recursive call (tail-recursive or not), and

•the structure of the calling pattern (linear or tree- recursive).

In this section, we will discuss all these types of recursions.

Direct Recursion

A function is said to be directly recursive if it explicitly calls itself. For example, consider Figure 4.7.

Here, Func() calls itself for all positive values of n, so it is said to be a directly recursive function.

Indirect Recursion

A function is said to be indirectly recursive if it contains a call to another function which ultimately calls it. Look at the functions given in Figure 4.8. These two functions are indirectly recursive as they both call each other.

Tail Recursion

A recursive function is said to be tail recursive if no operations are pending to be performed when the recursive function returns to its caller. When the called function returns, the returned value is immediately returned from the calling function. Tail recursive functions are highly desirable because they are much more efficient to use as the amount of information that has to be stored on the system stack is independent of the number of recursive calls.

For example, the factorial function that we have written is a non-tail-recursive function (Figure 4.9), because there is a pending operation of multiplication to be performed on return from each recursive call.

Whenever there is a pending operation to be performed, the function becomes non-tail recursive. In such a non- tail recursive function (Figure 4.10), information about each pending operation must be stored, so the amount of information directly depends on the number of calls.

However, the same factorial function can be written in a tail-recursive manner as shown in Figure 4.10.

In the code, Fact1 function preserves the syntax of the Fact (n). Here the recursion occurs in the Fact1 function and not in Fact function. Carefully observe that Fact1 has no pending operation to be performed on return from recursive calls. The value computed by the recursive call is simply returned without any modification. So in this case, the amount of information to be stored on the system stack is constant (just the values of n and res need to be stored) and is independent of the number of recursive calls.

Converting Recursive Functions to Tail Recursive

A non-tail recursive function can be converted into a tail-recursive function by using an auxiliary parameter as we did in case of the Factorial function. The auxiliary parameter is used to form the result. When we use such a parameter, the pending operation is incorporated into the auxiliary parameter so that the recursive call no longer has a pending operation. We generally use an auxiliary function while using the auxiliary parameter. This is done to keep the syntax clean and to hide the fact that auxiliary parameters are needed.

Linear and Tree Recursion

Recursive functions can also be characterized depending on the way in which recursion grows, i.e., in a linear fashion or forming a tree structure (Figure 4.11).

In simple words, a recursive function is said to be linearly recursive when the pending operation (if any) does not make another recursive call to the function. For ex- ample, observe the last line of recursive factorial function. The factorial function is linearly recursive as the pending operation involves only multiplication to be performed and does not involve another recursive call to Fact.