The idea of recursion is that a subroutine or function can call itself. In mathematics, this is not an unusual way to define some kinds of functions.
Very simple example
A function caled "N factorial", which is denoted as N!, is defined for nonnegative integers like this:
If N is 0, the value is 1.
Otherwise the value is N * (N-1)!
It is easy to calculate N! without recursion, but in some situations, recursion is the right tool to use.
A slightly fancier example
A slightly fancier example is the calculation of a function C(M, N). This is known as "the number of N-element subsets of a set of M things". It only makes sense if 0 <= N and N <= M.
C(M, N) is defined as follows (for our purposes):
C(M, 0) = 1 for all values of M.
C(M, N) = C(M - 1, N) + C(M - 1, N - 1) for all M > 1.
It is possible to calculate C(M, N) by using the factorial function instead, and therefore we could calculate it without recursion, but we are interested in recursion here.
First version of the example
Here is A program to calculate C(M, N):
#includeusing std::cin; using std::cout; using std::endl; int Combo(int, int); int main() { int R, M, N; cout << "We are computing C(M, N)." << endl; cout << "Please provide two integers M and N with M >= N >= 0" << endl; cin >> M >> N; if (M < 0 || N > M) cout<< "Oops! Bad input values: M = " << M << " and N = " << N << endl; else { R = Combo(M, N); cout << "Answer: C(" << M << ", " << N << ") = " << R << endl; } return 0; } int Combo(int M, int N) { int C; if (N == 0 || M == N) C = 1; else C = Combo(M-1, N) + Combo(M-1, N-1); return C; }
Here is the output from running this once:
We are computing C(M, N). Please provide two integers M and N, M >= N >= 0 Answer: C(4, 2) = 6
A second version of the example
As this does not tell us much, here is a fancier program which is intended to do the same thing and also print a lot information about what it is doing:
#includeusing std::cin; using std::cout; using std::endl; int Combo(int, int, int); int main() { int R, M, N, Level; cout << "We are computing C(M, N)." << endl; cout << "Please provide two integers M and N with M >= N >= 0" << endl; cin >> M >> N; if (M < 0 || N > M) cout<< "Oops! Bad input values: M = " << M << " and N = " << N << endl; else { Level = 1; R = Combo(M, N, Level); cout << "Answer: C(" << M << ", " << N << ") = " << R << endl; } return 0; } int Combo(int M, int N, int Level) { int C, J; if (N == 0 || M == N) { for (J = 0; J < 2*Level -1; J++) cout << ' '; cout << "Level = " << Level << " Computing C(" << M << ", " << N << ") Recursion is not needed." << endl; C = 1; } else { for (J = 0; J < 2*Level -1; J++) cout << ' '; cout << "Level = " << Level << " Computing C(" << M << ", " << N << ") Recursion is needed. " << endl; C = Combo(M-1, N, Level+1) + Combo(M-1, N-1, Level+1); } for (J = 0; J < 2*Level -1; J++) cout << ' '; cout << "Level = " << Level << " C(" << M << ", " << N << ") = " << C << " This call ends." << endl; return C; }
Here is the output from this second version once:
We are computing C(M, N).
Please provide two integers M and N with M >= N >= 0
Level = 1 Computing C(4, 2) Recursion is needed.
Level = 2 Computing C(3, 2) Recursion is needed.
Level = 3 Computing C(2, 2) Recursion is not needed.
Level = 3 C(2, 2) = 1 This call ends.
Level = 3 Computing C(2, 1) Recursion is needed.
Level = 4 Computing C(1, 1) Recursion is not needed.
Level = 4 C(1, 1) = 1 This call ends.
Level = 4 Computing C(1, 0) Recursion is not needed.
Level = 4 C(1, 0) = 1 This call ends.
Level = 3 C(2, 1) = 2 This call ends.
Level = 2 C(3, 2) = 3 This call ends.
Level = 2 Computing C(3, 1) Recursion is needed.
Level = 3 Computing C(2, 1) Recursion is needed.
Level = 4 Computing C(1, 1) Recursion is not needed.
Level = 4 C(1, 1) = 1 This call ends.
Level = 4 Computing C(1, 0) Recursion is not needed.
Level = 4 C(1, 0) = 1 This call ends.
Level = 3 C(2, 1) = 2 This call ends.
Level = 3 Computing C(2, 0) Recursion is not needed.
Level = 3 C(2, 0) = 1 This call ends.
Level = 2 C(3, 1) = 3 This call ends.
Level = 1 C(4, 2) = 6 This call ends.
Answer: C(4, 2) = 6
Some things to notice
It is the function Combo which is actually doing the recursion.
Aside from how much data is printed, the only real difference between the two versions of this program is the argument Level. It is used to count the depth of the recursion. Thus, Level = 1 means we are in Combo as called by the main program, and Level = 2 means we are in Combo as called by itself at Level 1. The program indents some of the output corresponding to the value of Level.
The first thing Combo does is look for the easy case in which the value is 1 and does not require recursion. When Combo calls itself, it does so with smaller value of the arguments. In general, a recursive function is coded like this:
If (this is the simplest case) Then
Return the value for the simplest case
Else
Do other things, including one or more recursive calls
involving smaller values of arguments
End If
Linked-list examples of recursion
Suppose we have a struct:
struct Link
{
int X;
Link * Next;
};
and we have a Link * variable called Head which points to the first Link in a linked list.
We would like to have a function to find the number of Links in the list. One way to do this is to use recursion:
int Length(Link * P)
{
if (P == 0)
return 0;
else
return 1 + Length(P->Next);
}
We call this function with (for example):
cout << " Length = " << Length(Head) << endl;
Of course, this could easily be done without recursion. Many tasks involving linked list are easy to code with recursion and are not always easy to do without recursion. Here's another one:
void PrintReverse(Link * P)
{
if (P != 0)
{
if (P->Next != 0)
PrintReverse(P->Next);
cout << P->X;
}
}
We call this function with (for example):
PrintReverse(Head);
and it should print out the list in reverse order.