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.
For instance, "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.
The idea of this example is to calculate 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):
Program TestItA
Implicit None
Integer :: R, Combo, M, N
Print *, 'We are computing C(M, N).'
Print *, 'Please provide two integers M and N, M >= N >= 0:'
Read *, M, N
If ((M < 0) .OR. (N > M)) Then
Print *, 'Oops! Bad input values'
Else
R = Combo(M, N)
50 Format(A11, I1, A2, I1, A4, I3)
Print 50, 'Answer: C(', M, ', ', N, ') = ', R
End If
End Program TestItA
Recursive Function Combo(M, N) Result(C)
Implicit None
Integer :: M, N, C
If ((N == 0) .OR. (M == N)) Then
C = 1
Else
C = Combo(M-1, N) + Combo(M-1, N-1)
End If
End Function Combo
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 later 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:
Program TestItD
Implicit None
Integer :: R, Combo, M, N, Level
20 Format(A)
Print 20, 'We are computing C(M, N).'
Print 20, 'Please provide two integers M and N, M >= N >= 0:'
Read *, M, N
If ((M < 0) .OR. (N > M)) Then
Print *, 'Oops! Bad input values'
Else
Level = 1
R = Combo(M, N, Level)
50 Format(A11, I1, A2, I1, A4, I3)
Print 50, 'Answer: C(', M, ', ', N, ') = ', R
End If
End Program TestItD
Recursive Function Combo(M, N, Level) Result(C)
Implicit None
Integer :: M, N, Level, C
Character(20), Parameter :: Space = ' '
If ((N == 0) .OR. (M == N)) Then
100 Format(A, A8, I1, T30, A14, I1, A2, I1, A1, T55, A)
Print 100, Space(1:2*Level-1), 'Level = ', Level, &
' Computing C(', M, ', ', N, ')', &
'Recursion is not needed.'
C = 1
200 Format(A, A8, I1, T30, A4, I1, A2, I1, A4, I3, T55, A)
Print 200, Space(1:2*Level-1), 'Level = ', Level, &
' C(', M, ', ', N, ') = ', C, 'This call ends.'
Else
Print 100, Space(1:2*Level-1), 'Level = ', Level, &
' Computing C(', M, ', ', N, ')', &
'Recursion is needed.'
C = Combo(M-1, N, Level+1) + Combo(M-1, N-1, Level+1)
Print 200, Space(1:2*Level-1), 'Level = ', Level, &
' C(', M, ', ', N, ') = ', C, 'This call ends.'
End If
End Function Combo
Here is the output from this fancier version once:
We are computing C(M, N).
Please provide two integers M and N, 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. We inform the compiler about this by using the keyword "Recursive" in front of the word "Function".
The value computed by Combo is returned by assigning a value to the variable C, which is identified as serving this purpose by the keyword "Result". We do not assign any value to the name "Combo" itself.
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