Fundamentals of Computer Programming with C# HTML version

Chapter 10. Recursion
In This Chapter
In this chapter we are going to get familiar with recursion and its
applications. Recursion represents a powerful programming technique in
which a method makes a call to itself from within its own method body. By
means of recursion we can solve complicated combinatorial problems, in
which we can easily exhaust different combinatorial configurations, e.g.
generating permutations and variations and simulating nested loops.
We are going to demonstrate many examples of correct and incorrect usage
of recursion and convince you how useful it can be.
What Is Recursion?
We call an object recursive if it contains itself, or if it is defined by itself.
Recursion is a programming technique in which a method makes a call to
itself to solve a particular problem. Such methods are called recursive.
Recursion is a programming technique whose correct usage leads to elegant
solutions to certain problems. Sometimes its usage could considerably
simplify the programming code and its readability.
Example of Recursion
Let’s consider the Fibonacci numbers. These are the elements of the
following sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Each element of the sequence is formed by the sum of the previous two
elements. The first two elements are equal to 1 by definition, i.e. the next two
rules apply:
F1 = F2 = 1
Fi = Fi-1 + Fi-2 (for i > 2)
Proceeding directly from the definition, we can implement the following
recursive method for finding the nth Fibonacci number:
static long Fib(int n)
if (n <= 2)