In the GetFactorial() method we discussed previously, traditional recursion is used to calculate the factorial number. This recursion model performs the recursive call first and returns the value, and then it calculates the result. Using this recursion model, we won't get the result until the recursive call is finished.
Besides the traditional recursion model, we have another recursion called tail recursion. The tail call becomes the last thing in the function and it doesn't do anything after the recursion at all. Let's look at the following code, which we can find in the TailRecursion.csproj project:
public partial class Program
{
public static void TailCall(int iTotalRecursion)
{
Console.WriteLine("Value: " + iTotalRecursion);
if (iTotalRecursion == 0)
{
Console.WriteLine("The tail is executed");
return;
}
TailCall(iTotalRecursion - 1);
}
}
From the preceding code, the tail is executed when iTotalRecursion has reached 0, as shown in the following code snippet:
if (iTotalRecursion == 0)
{
Console.WriteLine("The tail is executed");
return;
}
If we run the preceding TailCall() method and pass 5 for the iTotalRecursion argument, we will get the following output on the console:
Now, let's examine the state change every time the function is called recursively in this code:
TailCall(5)
(iTotalRecursion = 5) != 0
TailCall(4)
(iTotalRecursion = 4) != 0
TailCall(3)
iTotalRecursion = 3) != 0
TailCall(2)
iTotalRecursion = 2) != 0
TailCall(1)
iTotalRecursion = 1) != 0
TailCall(0)
iTotalRecursion = 0) == 0
Execute the process in tail
TailCall(1) => nothing happens
TailCall(2) => nothing happens
TailCall(3) => nothing happens
TailCall(4) => nothing happens
TailCall(5) => nothing happens
From the preceding flow of recursion, the process is only run in the last recursion call. After that, nothing happens to the other recursive calls. In other words, we can conclude that the flow will actually be as follows:
TailCall(5)
(iTotalRecursion = 5) != 0
TailCall(4)
(iTotalRecursion = 4) != 0
TailCall(3)
iTotalRecursion = 3) != 0
TailCall(2)
iTotalRecursion = 2) != 0
TailCall(1)
iTotalRecursion = 1) != 0
TailCall(0)
iTotalRecursion = 0) == 0
Execute the process in tail
Finish!
Now, the flow of our tail recursion is obvious and clear. The idea of tail recursion is to minimize the use of the stack that is sometimes the expensive resource we have. Using tail recursion, the code doesn't need to remember the last state it has to come back to when the next step returns, since it has the temporary result in the accumulator parameter in this case. The following topic is the two styles that follow tail recursion; they are accumulator-passing style (APS) and continuation-passing style (CPS).
In the accumulator-passing style (APS), the recursion performs the calculation first, executes the recursive call, and then passes the result of the current step to the next recursive step. Let's take a look at the following accumulator passing style of the tail recursive code we refactor from the GetFactorial() method, which we can find in the AccumulatorPassingStyle.csproj project:
public partial class Program
{
public static int GetFactorialAPS(int intNumber,
int accumulator = 1)
{
if (intNumber == 0)
{
return accumulator;
}
return GetFactorialAPS(intNumber - 1,
intNumber * accumulator);
}
}
Compared to the GetFactorial() method, we now have a second parameter named accumulator in the GetFactorialAPS() method. Since the result of the factorial 0 is 1, we give the default value of 1 to the accumulator parameter. Instead of just returning a value, it now returns the calculation of the factorial every time the recursive function is called. To prove this, consider that we have the following code in order to invoke the GetFactorialAPS() method:
public partial class Program
{
private static void GetFactorialOfFiveUsingAPS()
{
int i = GetFactorialAPS(5);
Console.WriteLine(
"5! (using GetFactorialAPS) is {0}",i);
}
}
If we run the preceding method, we will get the following output on the console:
Now, let's examine every call of the GetFactorialAPS() method to see the state change inside the method from the following flow of the program:
int i = GetFactorialAPS(5, 1)
accumulator = 1
(intNumber = 5) != 0
return GetFactorialAPS(4, 5 * 1)
accumulator = 5 * 1 = 5
(intNumber = 4) != 0
return GetFactorialAPS(3, 4 * 5)
accumulator = 4 * 5 = 20
(intNumber = 3) != 0
return GetFactorialAPS(2, 3 * 20)
accumulator = 3 * 20 = 60
(intNumber = 2) != 0
return GetFactorialAPS(1, 2 * 60)
accumulator = 2 * 60 = 120
(intNumber = 1) != 0
return GetFactorialAPS(0, 1 * 120)
accumulator = 1 * 120 = 120
(intNumber = 0) == 0
return accumulator
return 120
return 120
return 120
return 120
return 120
i = 120
As we can see from the preceding flow, since it performs the calculation every time it's called, we now have the result of the calculation in the last call of the function, when the intNumber parameter has reached 0, as shown in the following code snippet:
return GetFactorialTailRecursion(0, 1 * 120) accumulator = 1 * 120 = 120 (intNumber = 0) == 0 return accumulator return 120
We can also refactor the preceding GetFactorialAPS() method into the GetFactorialAPS2() method in order to not return any value, so it will become more obvious how the APS of tail recursion works. The code will be as follows:
public partial class Program
{
public static void GetFactorialAPS2(
int intNumber,int accumulator = 1)
{
if (intNumber == 0)
{
Console.WriteLine("The result is " + accumulator);
return;
}
GetFactorialAPS2(intNumber - 1, intNumber * accumulator);
}
}
Suppose we have the following GetFactorialOfFiveUsingAPS2() method to call the GetFactorialAPS2() method:
public partial class Program
{
private static void GetFactorialOfFiveUsingAPS2()
{
Console.WriteLine("5! (using GetFactorialAPS2)");
GetFactorialAPS2(5);
}
}
So, we will get the following output on the console if we invoke the preceding GetFactorialOfFiveUsingAPS2() method:
Now, the flow of the GetFactorialAPS2() method becomes clearer, as shown in the following flow of the program:
GetFactorialAPS2(5, 1)
accumulator = 1
(intNumber = 5) != 0
GetFactorialAPS2(4, 5 * 1)
accumulator = 5 * 1 = 5
(intNumber = 4) != 0
GetFactorialAPS2(3, 4 * 5)
accumulator = 4 * 5 = 20
(intNumber = 3) != 0
GetFactorialAPS2(2, 3 * 20)
accumulator = 3 * 20 = 60
(intNumber = 2) != 0
GetFactorialAPS2(1, 2 * 60)
accumulator = 2 * 60 = 120
(intNumber = 1) != 0
GetFactorialAPS2(0, 1 * 120)
accumulator = 1 * 120 = 120
(intNumber = 0) == 0
Show the accumulator value
Finish!
From the preceding flow, we can see that we calculate the accumulator every time the GetFactorialAPS2() method is invoked. The result of this recursion type is that we do not need to use the stack anymore since the function doesn't need to memorize its start position when it calls the function itself.
The continuation-passing style (CPS) has the same purpose as APS in implementing the recursive function using a tail call, but it has explicit continuation in processing the operation. The return of the CPS function will be passed on to the continuation function.
Now, let's refactor the GetFactorial() method into the following GetFactorialCPS() method, which we can find in the ContinuationPassingStyle.csproj project:
public partial class Program
{
public static void GetFactorialCPS(int intNumber, Action<int>
actCont)
{
if (intNumber == 0)
actCont(1);
else
GetFactorialCPS(intNumber - 1,x => actCont(intNumber * x));
}
}
As we can see, instead of using the accumulator, as we did in the GetFactorialAPS() method, we now use Action<T> to delegate an anonymous method, which we use as a continuation. Suppose we have the following code to invoke the GetFactorialCPS() method:
public partial class Program
{
private static void GetFactorialOfFiveUsingCPS()
{
Console.Write("5! (using GetFactorialCPS) is ");
GetFactorialCPS(5, x => Console.WriteLine(x));
}
}
If we run the preceding GetFactorialOfFiveUsingCPS() method, we will get the following output on the console:
Indeed, we get the same result compared to the GetFactorial() method or the GetFactorialAPS2() method. However, the flow of recursion now becomes a little bit different, as shown in the following explanation:
GetFactorialCPS(5, Console.WriteLine(x))
(intNumber = 5) != 0
GetFactorialCPS(4, (5 * x))
(intNumber = 4) != 0
GetFactorialCPS(3, (4 * x))
(intNumber = 3) != 0
GetFactorialCPS(2, (3 * x))
(intNumber = 2) != 0
GetFactorialCPS(1, (2 * x))
(intNumber = 1) != 0
GetFactorialCPS(0, (1 * x))
(intNumber = 0) != 0
GetFactorialCPS(0, (1 * 1))
(1 * 1 = 1)
(2 * 1 = 2)
(3 * 2 = 6)
(4 * 6 = 24)
(5 * 24 = 120)
Console.WriteLine(120)
The return of each recursion now is passed to the continuation process, in this case, the Console.WriteLine() function.
We have discussed recursion methods earlier. Actually, in our previous discussion, we applied direct recursion since we only dealt with a single method and we invoked it over and over again until the base case was executed. However, there's another recursive type, which is called indirect recursion. Indirect recursion involves at least two functions, for instance, function A and function B. In the application of an indirect recursion, function A calls function B, and then function B makes a call back to function A. It's considered a recursion because when method B calls method A, function A is actually active when it calls function B. In other words, the invocation of function A has not finished when function B calls function A again. Let's take a look at the following code, which demonstrates the indirect recursion that we can find in the IndirectRecursion.csproj project:
public partial class Program
{
private static bool IsOdd(int targetNumber)
{
if (targetNumber == 0)
{
return false;
}
else
{
return IsEven(targetNumber - 1);
}
}
private static bool IsEven(int targetNumber)
{
if (targetNumber == 0)
{
return true;
}
else
{
return IsOdd(targetNumber - 1);
}
}
}
We have two functions in the preceding code: IsOdd() and IsEven(). Each function calls the other function every time the comparison results false. The IsOdd() function will call IsEven() when targetNumber is not zero and so will the IsEven() function. The logic of each function is simple. For instance, the IsOdd() method decides whether or not targetNumber is odd by investigating whether or not the previous number, which is targetNumber - 1, is even. Likewise, the IsEven() method decides whether or not targetNumber is even by investigating whether or not the previous number is odd. They all subtract targetNumber by one until it becomes zero, and since zero is an even number, it's now quite easy to determine whether targetNumber is odd or even. Now, we add the following code to examine whether the number 5 is even or not:
public partial class Program
{
private static void CheckNumberFive()
{
Console.WriteLine("Is 5 even number? {0}", IsEven(5));
}
}
If we run the preceding CheckNumberFive() method, we will get the following output on the console:
Now, to make this clearer, let's take a look at the following indirect recursion flow involving the IsOdd() and IsEven() methods:
IsEven(5)
(targetNumber = 5) != 0
IsOdd(4)
(targetNumber = 4) != 0
IsEven(3)
(targetNumber = 3) != 0
IsOdd(2)
(targetNumber = 2) != 0
IsEven(1)
(targetNumber = 1) != 0
IsOdd(0)
(targetNumber = 0) == 0
Result = False
From the preceding flow, we can see that when we check whether number 5 is even or not, we move down to number 4 and check whether it is odd. We then check number 3 and so on, until we reach 0. By reaching 0, we can easily determine whether it's odd or even.