- 7.1 Introduction
- 7.2 Packaging Code in C#
- 7.3 static Methods, static Variables and Class Math
- 7.4 Methods with Multiple Parameters
- 7.5 Notes on Using Methods
- 7.6 Argument Promotion and Casting
- 7.7 The .NET Framework Class Library
- 7.8 Case Study: Random-Number Generation
- 7.9 Case Study: A Game of Chance; Introducing Enumerations
- 7.10 Scope of Declarations
- 7.11 Method-Call Stack and Activation Records
- 7.12 Method Overloading
- 7.13 Optional Parameters
- 7.14 Named Parameters
- 7.15 C# 6 Expression-Bodied Methods and Properties
- 7.16 Recursion
- 7.17 Value Types vs. Reference Types
- 7.18 Passing Arguments By Value and By Reference
- 7.19 Wrap-Up

## 7.16 Recursion

The apps we’ve discussed thus far are generally structured as methods that call one another in a disciplined, hierarchical manner. For some problems, however, it’s useful to have a method call itself. A **recursive method** is a method that calls itself, either *directly* or *indirectly through another method*. We consider recursion conceptually first. Then we examine an app containing a recursive method.

### 7.16.1 Base Cases and Recursive Calls

Recursive problem-solving approaches have a number of elements in common. When a recursive method is called to solve a problem, it actually is capable of solving *only* the simplest case(s), or **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 pieces (often called *divide and conquer*): a piece that the method knows how to do and a piece that it does not know how to do. To make recursion feasible, the latter piece must resemble the original problem, but be a slightly simpler or slightly smaller version of it. Because this new problem looks like the original problem, the method calls a fresh copy (or several fresh copies) of itself to work on the smaller problem; this is referred to as a **recursive call** and is also called the **recursion step**. The recursion step normally includes a `return` statement, because its result will be combined with the portion of the problem the method knew how to solve to 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 active (i.e., while it 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. For the recursion to *terminate* eventually, each time the method calls itself with a slightly simpler version of the original problem, the sequence of smaller and smaller problems must converge on the base case(s). 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 until the original method call returns the result to the caller. This process sounds complex compared with the conventional problem solving we’ve performed to this point.

### 7.16.2 Recursive Factorial Calculations

Let’s write a recursive app to perform a popular mathematical calculation. The factorial of a nonnegative integer *n*, written *n!* (and pronounced “*n* factorial”), is the product

n· (n– 1) · (n– 2) · ... · 1

1! is equal to 1 and 0! is defined to be 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 the `for` statement as follows:

long factorial = 1; for (long counter = number; counter >= 1; --counter) { factorial *= counter; }

A recursive declaration of the factorial method is arrived at by observing the following relationship:

n! =n· (n– 1)!

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

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

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

**Fig. 7.15** | Recursive evaluation of 5!.

### 7.16.3 Implementing Factorial Recursively

Figure 7.16 uses recursion to calculate and display the factorials of the integers from 0 to 10. The recursive method `Factorial` (lines 17–28) first tests to determine whether a terminating condition (line 20) is `true`. If `number` is less than or equal to `1` (the base case), `Factorial` returns `1` and no further recursion is necessary. If `number` is greater than `1`, line 26 expresses the problem as the product of `number` and a recursive call to `Factorial` evaluating the factorial of `number - 1`, which is a slightly simpler problem than the original calculation, `Factorial(number)`.

1// Fig. 7.16: FactorialTest.cs2// Recursive Factorial method.3using System;45class FactorialTest6{7static void Main()8{9// calculate the factorials of 0 through 1010for (long counter = 0; counter <= 10; ++counter)11{12Console.WriteLine($"{counter}! = {Factorial(counter)}");13}14}1516// recursive declaration of method Factorial17static long Factorial(long number)18{19// base case20if (number <= 1)21{22return 1;23}24else // recursion step25{26return number * Factorial(number - 1);27}28}29}

0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800

**Fig. 7.16** | Recursive `Factorial` method.

Method `Factorial` (lines 17–28) receives a parameter of type `long` and returns a result of type `long`. As you can see in Fig. 7.16, factorial values become large quickly. We chose type `long` (which can represent relatively large integers) so that the app could calculate factorials greater than 20!. Unfortunately, the `Factorial` method produces large values so quickly that factorial values soon exceed even the maximum value that can be stored in a `long` variable. Due to the restrictions on the integral types, variables of type `float`, `double` or `decimal` might ultimately be needed to calculate factorials of larger numbers. This situation points to a weakness in some programming languages—the languages are *not easily extended* to handle the unique requirements of various apps. As you know, C# allows you to create new types. For example, you could create a type `HugeInteger` for arbitrarily large integers. This class would enable an app to calculate the factorials of larger numbers. In fact, the .NET Framework’s `BigInteger` type (from namespace `System.Numerics`) supports arbitrarily large integers.