9.1: What is recursion?

Recursion is a programming construct that solves a problem by breaking it into successively smaller problems, each of the smaller problems being implemented in a function that has the same functionality as the original problem, but is operating on a smaller universe of values. The reducing of the problem continues until some base or ending case is reached. The results of the base case are then returned to each of the functions, which compute results, and these results are then returned to the calling function.

One of the issues with teaching recursion is that it is not that useful for small problems that can be easily presented to students, and these small problems can be solved using procedural programming more easily and quickly than using recursion, which leads students to believe that recursion is not actually useful. However there are many problems that cannot be solved using procedural programming without the use of a stack, and those problems are almost always more easily solved using recursion rather than procedural programming. These types of problems will be examined in the problems at the end of the chapter. But for now, the principals of recursion will be presented, with the hope that the reader will understand the basic concept of recursion, and be able to apply it to more real world problems later.

The problem that will be presented to illustrate recursion is the summation problem. The problem is to sum all the numbers from 1 to n, and print out the result. So for example, if the user enters 5 into the program, the program will add \(0+1+2+3+4+5 = 15\). Mathematically this function can be specified as:

\(\displaystyle \sum_{i=0}^n i\)

This can be rewritten mathematically as:

f(n) = 0 when n == 0 
    else f(n) = f(n-1) + n

This corresponds to the following Java method:

public static int sum(int n) { 
    if (n == 0) return 0; 
    else return sum(n-1) + n; 
}

The rest of this section will translate this method into an assembly language program.

To begin creating the assembly function first create the structure for the function. Thus the first step is to define push and pop sections of the function. First for the push, the value of n is passed into the function using r0. Since r0 is needed in the function, convention holds that it must be saved, and so it is moved into r4. Since r4 is a preserved register, its original value is saved to the stack when the function is first entered, and restored when the function returns.

Next the standard block structure of the function must be maintained. Thus the return label is placed just before the pop. All paths that exit this function should use this return label to make sure the stack is correctly popped.

The format for the Summation function can form a template for implementing any recursive function. Initially looks as follows:

Summation: 
    #push stack. Save r0 (summation) in r4, 
    # so r4 has to be saved by callee convention 
    sub sp, sp, #8 
    str lr, [sp, #0] 
    str r4, [sp, #4] 
    mov r4, r0 
    
# pop stack and return 
    return: 
    ldr lr, [sp, #0] 
    ldr r10, [sp, #4] 
    add sp, sp, #8 
    mov pc, lr 
# END Summation

The next step in writing the code is filling in the code for the base and recursive conditions. First the base condition is “if (n ==0) return 0”. This is translated into the following assembly language code fragment:

MOV r1, #0 
CMP r0, r4 
    BNE recurse 
        MOV r0 #0 
        B return

The code for the recursive condition is “else return sum(n-1) + n”. This is translated into the following assembly language code fragment:

recurse: 
    SUB r0, r4, #1 
    BL sum 
    ADD r0, r0, r4 
    B return

Putting these pieces together, the following function is created. A main method is added to complete the program, and a working program to calculate a sum recursively is defined.

.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 
    beq return @ 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

This version of the program is basically equivalent to the Java version of this program that was implemented earlier. There really is nothing mystical or magical about implementing recursion in assembly language if recursion is understood at the HLL and the standards are followed. In fact the assembly language version should be more clear as the details of how the stack is used to implement assembly are fully transparent.

Difficulty with recursion in assembly arises when programmers decide they know better how to implement a program, and thus can dispense with the standard format for programming in assembly. These programs become hopelessly complex, and as will be seen in the next section, can result in erroneous programs that might compute the correct answer, but are simply wrong.