In the first announcement of functional programming, many functional languages didn't have the loop feature to iterate the sequence. All we had to do was construct the recursion process to iterate the sequence. Although C# has iteration features such as for and while, it is better if we discuss recursion in the functional approach. Recursion will also simplify our code. To do that, in this chapter, we will discuss the following topics:
- Understanding how the recursive routine works
- Refactoring an iteration into a recursion
- Distinguishing tail recursion between the accumulator-passing style and the continuation-passing style
- Understanding indirect recursion over direct recursion
- Applying recursion in the functional approach using the Aggregate LINQ operator
A recursive function is a function that calls itself. Like the iteration loop, for instance, the while and for loop--it is used to solve a complicated task one piece at a time and combine the results. However, there is a difference between the for loop and while loop. The iteration will keep repeating until the task is done, while the recursion will break the task up into smaller pieces in order to solve the larger problem and then combine the result. In the functional approach, the recursion is closer to the mathematical approach since it is often shorter than iteration, although it's somehow more difficult to design and test.
In Chapter 1, Tasting Functional Style in C#, we were acquainted with recursive functions, when we discussed the concepts of functional programming. There, we analyzed the factorial function named GetFactorial() in the imperative and functional approach. To refresh our memory, following is the GetFactorial() function implementation, which we can find in the SimpleRecursion.csproj project:
public partial class Program
{
private static int GetFactorial(int intNumber)
{
if (intNumber == 0)
{
return 1;
}
return intNumber * GetFactorial(intNumber - 1);
}
}
From our discussion in Chapter 1, Tasting Functional Style in C# we know that the factorial of the non-negative integer N is the multiplication of all positive integers less than or equal to N. So, suppose we have the following function to calculate the factorial of five:
private static void GetFactorialOfFive()
{
int i = GetFactorial(5);
Console.WriteLine("5! is {0}",i);
}
As we can predict, if we invoke the preceding GetFactorialOfFive() method, we will get the following output on the console:
Back to the GetFactorial() method again; we see in the implementation of this method there is code that will end the recursion, as shown in the following code snippet:
if (intNumber == 0)
{
return 1;
}
We can see that the preceding code is the base case of the recursion and the recursion usually has the base case. This base case will define the end of the recursion chain since, in this case, the method will change the state of intNumber every time the recursion is run, and the chain will be stopped if intNumber is zero.
In order to understand how the recursive routine works, let's examine the state of intNumber if we find the factorial of five, as shown in the following flow of the program:
int i = GetFactorial(5)
(intNumber = 5) != 0
return (5 * GetFactorial(4))
(intNumber = 4) != 0
return (4 * GetFactorial(3))
(intNumber = 3) != 0
return (3 * GetFactorial(2))
(intNumber = 2) != 0
return (2 * GetFactorial(1))
(intNumber = 1) != 0
return (1 * GetFactorial(0))
(intNumber = 0) == 0
return 1
return (1 * 1 = 1)
return (2 * 1 = 2)
return (3 * 2 = 6)
return (4 * 6 = 24)
return (5 * 24 = 120)
i = 120
Using the preceding flow, it becomes clearer how the recursion works. The base case we have defines the end of the recursion chain. A programming language compiler converts the specific case of recursion into an iteration when applicable because a loop-based implementation becomes more efficient by eliminating the need for a function call.
Recursion makes our programs more readable, and it is essential in the functional programming approach. Here, we are going to refactor the for loop iteration to the recursion method. Let's take a look at the following code, which we can find in the RefactoringIterationToRecursion.csproj project:
public partial class Program
{
public static int FindMaxIteration(
int[] intArray)
{
int iMax = 0;
for (int i = 0; i < intArray.Length; i++)
{
if (intArray[i] > iMax)
{
iMax = intArray[i];
}
}
return iMax;
}
}
The preceding FindMaxIteration() method is used to pick the maximum number in the array of numbers. Consider that we have the following code in order to run the FindMaxIteration() method:
public partial class Program
{
static void Main(string[] args)
{
int[] intDataArray =
{8, 10, 24, -1, 98, 47, -101, 39 };
int iMaxNumber = FindMaxIteration(intDataArray);
Console.WriteLine(
"Max Number (using FindMaxRecursive) = " +
iMaxNumber);
}
}
As we can expect, we will have the following output in the console window:
Now, let's refactor the FindMaxIteration() method to the recursive function. The following is the implementation of the FindMaxRecursive() method, which is the recursion version of the FindMaxIteration() method:
public partial class Program
{
public static int FindMaxRecursive(
int[] intArray,
int iStartIndex = 0)
{
if (iStartIndex == intArray.Length - 1)
{
return intArray[iStartIndex];
}
else
{
return Math.Max(intArray[iStartIndex],
FindMaxRecursive(intArray,iStartIndex + 1));
}
}
}
We can invoke the preceding FindMaxRecursive() method using the same code as we did in the FindMaxIteration() method, as follows:
public partial class Program
{
static void Main(string[] args)
{
int[] intDataArray = {8, 10, 24, -1, 98, 47, -101, 39 };
int iMaxNumber = FindMaxRecursive(intDataArray);
Console.WriteLine"Max Number(using FindMaxRecursive) = " +
iMaxNumber);
}
}
As we can see in the preceding method, we have the following base case to define the end of the recursion chain:
if (iStartIndex == intArray.Length - 1)
{
return intArray[iStartIndex];
}
If we run the preceding code, we will get the same result as the one we got in our previous method, as shown in the following console screenshot:
Now, let's take a look at the following flow to know how we can get this result when we use the recursion function:
Array = { 8, 10, 24, -1, 98, 47, -101, 39 };
Array.Length - 1 = 7
int iMaxNumber = FindMaxRecursive(Array, 0)
(iStartIndex = 0) != 7
return Max(8, FindMaxRecursive(Array, 1))
(iStartIndex = 1) != 7
return Max(10, FindMaxRecursive(Array, 2))
(iStartIndex = 2) != 7
return Max(24, FindMaxRecursive(Array, 3))
(iStartIndex = 3) != 7
return Max(-1, FindMaxRecursive(Array, 4))
(iStartIndex = 4) != 7
return Max(98, FindMaxRecursive(Array, 5))
(iStartIndex = 5) != 7
return Max(47, FindMaxRecursive(Array, 6))
(iStartIndex = 6) != 7
return Max(-101, FindMaxRecursive(Array, 7))
(iStartIndex = 7) == 7
return 39
return Max(-101, 39) = 39
return Max(47, 39) = 47
return Max(98, 47) = 98
return Max(-1, 98) = 98
return Max(24, 98) = 98
return Max(10, 98) = 98
return Max(8, 98) = 98
iMaxNumber = 98
Using the preceding flow, we can distinguish every state change in the maximum number we get every time the FindMaxRecursive() method is called. Then, we can prove that the maximum number in the given array is 98.