9.2: An Erroneous implementation of Recursion

The example program in this section is the same summation problem and sum function from the previous section. However now a very intelligent programmer notices that the values of r0 and lr has not been modified when the base condition is called. This programmer decides that there is thus no need to branch to the return label in the program, thus saving a few instructions. This programmer now feels good that they have made the program faster, and see it as a job well done.

.text 
    .global main 
    
main: 
# Save return to os on stack 
    sub sp, sp, #4 
    str lr, [sp, #0] 
    
    mov r0, #10 
    bl Summation 
    mov r1, r0 
    ldr r0, =output 
    bl printf 
    
# Return to the OS 
    ldr lr, [sp, #0] 
    add sp, sp, #4 
    mov pc, lr 
    
.data 
    output: .asciz "Summation is %d\n" 
    
.text 
# Note: Summation is NOT a global symbol! 
# It is a static function 
Summation: 
    #push stack. Save r0 (summation) in r10, 
    # so r10 has to be saved by callee convention 
    sub sp, sp, #8 
    str lr, [sp, #0] 
    str r4, [sp, #4] 
    mov r4, r0
    
    # if r0 is 0, return 0 
    mov r1, #0 
    cmp r1, r4 
    moveq pc, lr @ return 0 in r0 
    
    add r0, r4, #-1 
    bl Summation @ return value in r0
    add r0, r4, r0 @ return summation in r0 
    b return @ not really needed 
    
# pop stack and return 
    return: 
    ldr lr, [sp, #0] 
    ldr r4, [sp, #4] 
    add sp, sp, #8 
    mov pc, lr 
#END Summation

There are two problems with this analysis. First, the program looks like it is a few instructions faster, but the amount is speed up is beyond the ability of the computer to measured, and many orders of magnitude smaller than anything on a human time scale. But worse, the programmer unintentionally added more executable statements to the program, and does not even realize it.

Second, the program has made the program erroneous. When the program is tested, it produces the correct result, so the programmer believes it is correct. But the program produces this result in a way that the programmer making the changes does not understand, and a subtle incorrect behavior has been added.

To see this incorrect behavior, consider an even more intelligent programmer who realizes the sum from 0...n is the same as 1...n, and so the base condition can be changed from 0 to 1 to save a few clock cycles. This is shown in the following program.

.text 
    .global main 

main: 
# Save return to os on stack 
    sub sp, sp, #4 
    str lr, [sp, #0] 
    
    mov r0, #10 
    bl Summation 
    mov r1, r0
    ldr r0, =output 
    bl printf
    
# Return to the OS 
    ldr lr, [sp, #0] 
    add sp, sp, #4 
    mov pc, lr
    
.data 
    output: .asciz "Summation is %d\n"
    
.text 
# Note: Summation is NOT a global symbol! 
# It is a static function 
Summation: 
    #push stack. Save r0 (summation) in r10, 
    # so r10 has to be saved by callee convention 
    sub sp, sp, #8 
    str lr, [sp, #0] 
    str r4, [sp, #4] 
    mov r4, r0 
    
    # if r0 is 0, return 0 
    mov r1, #1 
    cmp r1, r4 
    moveq pc, lr @ return 0 in r0 
    
    add r0, r4, #-1 
    bl Summation @ return value in r0 
    add r0, r4, r0 @ return summation in r0 
    b return @ not really needed 
    
# pop stack and return 
    return: 
    ldr lr, [sp, #0] 
    ldr r4, [sp, #4] 
    add sp, sp, #8 
    mov pc, lr 
#END Summation

The problem now is that there is an off-by-one bug. The value returned from the summation program is one too large. So did the new programmer create the off-by-one condition? NO! The condition was created by the first programmer not following the standards for writing recursion. The second programmer simply allowed the presence of the bug to become apparent.

Why? When the first programmer returned without branching to return, that programmer did not pop the stack. This left the stack record with the value n=0 on the stack. Thus when the program returned a 0, the n=0 stack record was unintentionally not popped. The next return was the result of 0+0, or just 0, which is the correct answer, but that answer was achieved incorrectly.

When the second programmer now made the base condition 1, the stack record with n=1 was again incorrectly popped. However now the result is 1+1, which is incorrect. The program modified by the first programmer was always incorrect, but it was not until the modification was introduced that the problem became apparent.

This illustrates an important point for the reader to realize; the bug was introduced in the first modification, not the second modification. The fact that the program worked (or rather, produced the correct result) does not change the fact that the modification made the program erroneous (or in this case, simply wrong).

This program also illustrates why programmers often think recursion is difficult to implement in general, and even more so in assembly language. As has been stressed in this textbook from the beginning, programmers are taught or in some fashion come to believe that programs are products of logic, and implementing correct logic produces good programs. When implementing the recursion using a non-standard technique, the results are even more convoluted in assembly, where the possibility of unrestricted branching allows programmers imaginations to run amok. In the long run this produces spaghetti like logic even the person implementing the program loses track of what is actually being done.

The truth is good structure produces good (and correct) programs. Implementing logic in a standard format is the path to creating good programs. Starting with a good structure will lead to more simple and correct solutions, and that is true in whatever language the programmer uses.