18.2: Recursive Print Binary Example

This section provides an example recursive subroutine to accept a decimal number and print that number in binary (i.e., using 1's and 0').

It is assumed the reader has a basic understanding of binary¹ representation. This information is summarized in the chapter on Computer Organization. Additionally, there are many references available on the Internet.

Understand the Problem

For this example, the problem is divided into two parts, the main program and the recursive subroutine. The main program will handle the prompting and reading of the decimal number including error checking and re-prompting as needed. The recursive subroutine will display the binary value. Since the error checking is already performed, the recursive subroutine will assume valid input. For more complex examples, the routine may need to perform basic error checking.

Create the Algorithm

One basic algorithm to convert a decimal number into a binary number, is successive integer division by 2. For example, given the number 13, 13 divided by 2 is 6 with a remainder of 1. Next, the 6 is divided by 2 giving 3 with a remainder of 0. Again, the 3 is divided by 2 providing a 1 with a remainder of 1. The final 1 is divided by 2 resulting in a 0 with a remainder of 1. With a final result of 0, the algorithm is completed. The process is shown as follows:

\[ \frac{13}{2} = 6 \quad \textit{remainder } 1 \nonumber \]

\[ \frac{6}{2} = 3 \quad \textit{remainder } 0 \nonumber \]

\[ \frac{3}{2} = 1 \quad \textit{remainder } 1 \nonumber \]

\[ \frac{1}{2} = 0 \quad \textit{remainder } 1 \nonumber \]

The remainders, always 0 or 1, represent the binary value. However, the resulting remainders are generated in backwards order. As such, the resulting remainders 1, 0, 1, and 1 in this example must be reversed for a final value of \(1101_2\) (as noted in chapter 2).

This process can be converted into a recursive relation as follows:

\[ printBinary(n) = \begin{cases} \textit{if } n \leq 1 & n \\ \textit{if } n > 1 & printBinary(n/2) \\ & \text{output } mod(num,2) \end{cases} \nonumber \]

This definition assumes that the value of \(n\) is positive. The recursive relation can be used by directly converting the algorithm into code.

Implement the Program

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

! Simple recursive program to print a decimal number in binary

program binary
implicit none
integer :: decimalNumber

    write (*,'(a/)') "Decimal to Binary Conversion Example"

    do
        write (*,'(a)', advance="no")                    &
            "Enter Decimal Number (0 - 1,000,000): "
        read (*,*) decimalNumber
        if (decimalNumber >= 0 .and.                     &
            decimalNumber <= 1000000) exit

        write (*,'(a)') "Error, decimal value out of range."
        write (*,'(a)') "Please re-enter."
    end do

    write (*,'(/a, i7, a)', advance="no")                &
        "The decimal value of ", decimalNumber, " is "

    call printBinary(decimalNumber)
    write (*,'(/)')

contains

! ************************************************************
!  Print binary subroutine.

recursive subroutine printBinary(num)
integer, intent(in) :: num

    if (num > 1) call printBinary(num/2)

    write (*,'(i1)', advance="no") mod(num,2)

    return
end subroutine printBinary

! ************************************************************
end program binary

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 and entering a series of decimal values and ensure that the results are correct. The Windows calculator provides simple convert-to- binary function that can be used for verification.

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

---

1. For more information regarding binary representation, refer to: http://en.Wikipedia.org/wiki/Binary_number