18.4: Recursive Factorial Example

This section provides an example recursive function to compute the mathematical factorial¹ function. It is assumed the reader is familiar with the factorial function.

\[ n! = \prod_{k=1}^{n}k \nonumber \]

Or more familiarly, you might see \(5!\) as:

\[ n! = 5 \times 4 \times 3 \times 2 \times 1 \nonumber \]

For this example, the problem is divided into two parts, the main program and the recursive function.

The main program will handle the prompting and reading of the \(n\) value. This will include error checking and re-prompting as needed. The recursive function will compute and return the factorial value. Since the error checking is performed, the recursive function will assume valid input.

For more complex examples, the function itself may need to perform the error checking. As such, a simple helper function could be used to verify the input value or values before calling the recursive function.

Create the Algorithm

A typical recursive relation for factorial is as follows:

\[ factorial(n) = \begin{cases} 1 & \textit{if } n = 0 \\ n \times factorial(n-1) & \textit{if } n \geq 1 \end{cases} \nonumber \]

This definition assumes that the value of \(n\) is positive.

It must be noted that this function could easily be computed with a loop. However, the reason this is done recursively is to provide a simple example of how a recursive function is developed using a familiar mathematical function.

Implement the Program

Based on the recursive definition, a simple recursive function can be created. In order to demonstrate the recursive function, a main program is provided that will read the decimal value from user and ensure it is between 1 and 15, and then call the recursive routine.

The recursive function declaration uses an input argument, n, and a result argument, ans, in this example. The input argument must be declared as intent(in) in the standard manner. However, the result argument is an out by definition and will assume the type of the function itself, integer in this example.

For the recursive factorial function, the basic algorithm is provided as part of the recursive definition. The example main will read the n value from the user, call the factorial function, and display the results.

! Simple recursive function example.

program recursionExample
implicit none
integer :: num, numFact
    write (*,'(a/)') "Recursion Example"

    do
        write (*,'(a)', advance="no") "Enter N (1-15): "
        read (*,*) num
        if (num >= 1 .and. num <= 15) exit
        write (*,'(a)') "Error, N out of range."
        write (*,'(a)') "Please re-enter."
    end do

    numFact = fact(num)
    write (*,'(a, i2, a, i10,/)') "Factorial of ", num,    &
        " is ", numFact

contains

! *************************************************************
!  Factorial function

integer recursive function fact(n) result (ans)
implicit none
integer, intent(in) :: n

    if (n == 1) then
        ans = 1
    else
        ans = n * fact(n-1)
    end if

    return
end function fact

! *************************************************************

end program recursionExample

The spacing and indentation are not required, but help to make the program more readable. The main program ensures that the recursive routine is not called in invalid values (i.e., values \(\leq\) 0).

Test/Debug the Program

For this problem, the testing would involve executing the program, entering a number, and ensuring that the result is correct. The Windows calculator includes a factorial function which can be used to verify the result.

If the program does not provide the correct result, the input to the recursive function should be verified (via write statements). Next, some additional write statements in the recursive function can be added to provide insight into what is being done for each call.

---

1. For more information regarding factorial, refer to: http://en.Wikipedia.org/wiki/Factorial