23. Recursion Fundamentals

---

Chapter 23. RECURSION FUNDAMENTALS

You will learn about the following in this chapter:

• Recursive methods and recursion

• The ability of C# to support pending method instances of the same method, and why this is an imperative ability when implementing recursive methods

• The key ingredients of a successful recursive method

• The fundamental reasons why recursion works

• Recursion versus iteration

• Binary search implemented using recursion instead of iteration

In this book, you have seen many examples of methods calling other methods. For example MethodA might, from within its method body, call MethodB to help MethodA accomplish a certain task. C# also allows a method to call itself. If MethodA's body contains a call to MethodA, MethodA is said to call itself. A method that calls itself is called a recursive method. The general concept of using recursive methods is called recursion.

Direct and Indirect Recursion

There are two kinds of recursion direct and indirect. When MethodA calls itself from within its own method body, we call it direct recursion. When MethodA calls itself by calling a different method (MethodB that calls MethodA), we call it indirect recursion. In this chapter, we will only look at direct recursion.

Even though recursion at first sounds like paradoxical circular logic, it is an important computer science topic. When applied correctly, recursion results in compact and clear algorithms that can be used to solve significant computational problems, such as sorting and searching.

---