Section 7.19. Recursion

7.19. Recursion

It is sometimes useful for methods to call themselvesa recursive method is a method that calls itself either directly or indirectly (i.e., through another method). In this section, we present a simple example of recursion.

Let us first consider recursion conceptually. Recursive problem-solving approaches have a number of elements in common. A recursive method is called to solve a problem. The method actually knows how to solve only the simplest case(s)the base case(s). If the method is called with a base case, it returns a result. If the method is called with a more complex problem, it divides the problem into two conceptual piecesa piece that the method knows how to perform (i.e., base case), and a piece that it does not know how to perform. To make recursion feasible, the latter piece must resemble the original problem but be a slightly simpler or smaller version of it. The method invokes (calls) a fresh copy of itself to work on the smaller problemthis is referred to as a recursive call, or recursion step. The recursion step also normally includes the keyword Return, because its result will be combined with the portion of the problem that the method knew how to solve. Such a combination will form a result that will be passed back to the original caller.

The recursion step executes while the original call to the method is still "open" (i.e., has not finished executing). The recursion step can result in many more recursive calls, as the method divides each new subproblem into two conceptual pieces. As the method continues to call itself with slightly simpler versions of the original problem, the sequence of smaller and smaller problems must converge on a base case, so that the recursion can eventually terminate. At that point, the method recognizes the base case and returns a result to the previous copy of the method. A sequence of returns ensues up the line until the original method call returns the final result to the caller. As an example of these concepts, let us write a recursive program that performs a popular mathematical calculation.

Determining a Factorial Value Recursively

The factorial of a nonnegative integer n, written n! (and read "n factorial"), is the product

 n · (n - 1 ) · (n - 2 ) · ... · 1 

with 1! equal to 1, and 0! defined as 1. For example, 5! is the product 5·4·3·2·1, which is equal to 120.

The factorial of an integer number greater than or equal to 0 can be calculated iteratively (nonrecursively) using a For...Next statement, as follows:

 Dim counter, factorial As  Integer = 1 For counter = number To 1 Step -1    factorial *=  counter Next 

We arrive at a recursive definition of the factorial method by observing the following relationship:

 n! = n · (n - 1 )! 

For example, 5! is clearly equal to 5 · 4!, as is shown by the following:

 5! = 5 · 4 ·  3 · 2 · 1 5! = 5 · ( 4 ·  3 · 2 · 1 ) 5! = 5 · ( 4! ) 

A recursive evaluation of 5! would proceed as in Fig. 7.20. Figure 7.20(a) shows how the succession of recursive calls proceeds until 1! is evaluated to be 1, which terminates the recursion. Figure 7.20(b) depicts the values that are returned from each recursive call to its caller until the final value is calculated and returned.

Figure 7.20. Recursive evaluation of 5!.

(a) Procession of recursive calls.

(b) Values returned from each recursive call.

The program in Fig. 7.21 recursively calculates and prints factorials. The recursive method Factorial (lines 1925) first tests (line 20) to determine whether its terminating condition is true (i.e., number is less than or equal to 1). This determines whether the parameter is one of the base cases (0 or 1). If number is less than or equal to 1, Factorial returns 1, no further recursion is necessary and the method returns. If number is greater than 1, line 23 expresses the problem as the product of number and a recursive call to Factorial, evaluating the factorial of number - 1. Note that calculating Factorial(number - 1) is slightly simpler than the original calculation, Factorial(number).

Figure 7.21. Recursive factorial program.

  1  ' Fig. 7.21: Factorial.vb  2  ' Calculating factorials using recursion.  3  Public Class FrmFactorial  4     ' calculate factorial  5     Private Sub btnCalculate_Click(ByVal sender As System.Object, _  6        ByVal e As System.EventArgs) Handles btnCalculate.Click  7  8        ' convert text in TextBox to Integer  9        Dim value As Integer = Convert.ToInt32(txtInput.Text) 10        txtDisplay.Text = "" ' reset TextBox 11 12        ' call Factorial to perform calculation 13        For i As Integer = 0 To value 14           txtDisplay.Text &= i & "! = " & Factorial(i) & vbCrLf 15        Next 16     End Sub ' btnCalculate_Click 17 18     ' recursively generates factorial of number 19     Function Factorial(ByVal number As Integer) As Long 20        If number <= 1 Then ' base case 21           Return 1 22        Else 23           Return number * Factorial(number - 1) 24        End If 25     End Function ' Factorial 26  End Class ' FrmFactorial 

We have set the output TextBox's ScrollBars property to Vertical, to display a vertical scrollbar. This allows us to display more outputs than will fit in the space allocated for the TextBox. Method Factorial (line 19) receives a parameter of type Integer and returns a result of type Long. Type Long is designed to store integer values in a range much larger than that of type Integer. As is seen in the output window of Fig. 7.21, factorial values grow quickly. We choose type Long to enable the program to calculate factorials greater than 12!. Unfortunately, the values produced by the Factorial method increase at such a rate that the range of even the Long type is quickly exceeded. This points to a weakness in most programming languagesthey are not easily extended to handle the unique requirements of various applications, such as the evaluation of large factorials. Recall that Visual Basic is an extensible languageprogrammers with unique requirements can extend the language by defining new classes. You could create a HugeInteger class that would enable a program to calculate the factorials of arbitrarily large numberswe create a HugeInteger class in Chapter 22, Web Services.

Common Programming Error 7.12

Forgetting to return a value from a recursive method can result in logic errors.

Common Programming Error 7.13

Omitting the base case or writing the recursion step so that it does not converge on the base case will cause infinite recursion, eventually exhausting memory. This is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution.