Mon, 6th Nov 2017, 02:49 Some stuff on Recursion
My students,
I have written most of a section on Recursion which will be part of the 3rd
edition of the textbook. Given last Wednesday's lecture, I hope you will find
this a useful addition to the lecture.
In the interest of getting this to you quickly, I will admit that I have not
yet had a chance to check to see if the code shown below is bug free. If you
find an error in it, please let me or one of my TAs know so I can let the rest
of the class know.
See you later today!
Yale Patt
=====================
8.3.6. Recursion, a powerful technique that requires a stack
Recursion is a mechanism for expressing a function in terms of itself. Some
have referred to it as picking oneself up by one's bootstraps, since at first
blush, it looks like magic -- which, of course, it isn't.
The simplest example to illustrate recursion is the function: factorial. The
equation
n! = n * (n-1)!
says it all. We are expressing factorial in terms of factorial. How we can
write a program to do this we will see momentarily.
For now, it is important to understand that recursion is a powerful technique
for expressing the structure of an algorithm efficiently. Where useful, it
can help the programmer by removing a lot of detail that the programmer would
otherwise have to keep track of. When used capriciously, it can cause the
resulting program to run much more slowly than is necessary. In this chapter,
we will show three examples, the first two use recursion when it would be
better not to; the third example uses recursion judiciously. To implement
recursion, we will need a partner we have just recently discussed: a stack.
We start our discussion of recursion with two bad uses of recursion that are
often used in the classroom to explain the concept even though they incur very
costly penalties in execution time.
8.3.6.1. Bad example Number 1: Factorial.
As stated above, n! = n * (n-1)!
Assume the subroutine FACT (Factorial) is supplied with a value n in R0, and
returns with the value n! in R0.
The basic structure of a subroutine to do this is shown below:
FACT ST R1, SAVE_R1; R1 is needed in the subroutine
ADD R1,R0,#-1 ; Test if R0=1
BRz DONE ; If R0=1, R0=(1)!
ADD R1,R0,#0 ; Save n, to be used after we compute (n-1)!
ADD R0,R1, #-1 ; R0 is set to n-1, preparatory to calling FACT
B JSR FACT ; On RET, R0 will contain (n-1)!
MUL R0,R0,R1 ; Now R0 should contain n!
DONE LD R1, SAVE_R1; Restore R1
RET
SAVE_R1 .BLKW 1
The subroutine first tests to see if n=1. If so, we are essentially done,
since (1)! =1. Note we did save R1 before our test since the calling program
has every right to expect that after returning, R1 has not changed as a result
of executing the subroutine FACT. So, if n=1, we branch to DONE where we
restore R1, and then RET to the calling program.
We must emphasize that every recursive subroutine must have such an
initial test to see if we should execute the recursive JSR FACT. Without
this test, the subroutine would call itself an infinite number of times!
Clearly, that can not be correct. The answer is to provide a test before the
recursive JSR instruction. In the current case, the test is whether R0
contains the value 1. If yes, we do not execute a JSR FACT, and instead
set R0 to 1 (since 1! = 1) and RET.
If n is not equal 1, we save n in R1, load R0 with n-1 and JSR FACT. When
FACT returns with (n-1)! in R0, we multiply it by n (which was saved in R1),
producing n!, which we load into R0, restore R1 to the value expected by the
calling program, and RET.
We are assuming that our ISA has a MUL instruction. Since the LC-3 does not
have a MUL instruction, this will require another subroutine call, but we are
ignoring that here in order to focus on the recursion.
We call the subroutine recursive because inside the FACT subroutine is an
instruction JSR FACT.
Unfortunately, the code we have written will not work. To see why it will not
work, Figure New.11 shows the flow of instruction execution. The main program
calls the subroutine with a JSR instruction at address A. This causes the
code labeled #1 to excute. At address B, the subroutine FACT calls itself
with the instruction JSR FACT. This causes the code labeled #2 to execute,
and so forth.
Note that when the main program executes the instruction JSR FACT, the
return linkage A+1 is saved in R7. In the block of code labeled #1, the
instruction at address B (JSR FACT) stores its return linkage B+1 in R7,
destroying A+1, so there is no way to get back to the main program. Bad!
We can solve this problem by pushing the address A+1 onto a stack before
executing JSR FACT at address B. After we subsequently return to
address B+1, we can then pop the stack, and load the address A+1 into R7
before we execute the instruction RET back to the main program.
Furthermore, note that the instruction ADD R1,R0,#0 in (1) loads the value n
into R1, and in (2), the instruction ADD R1,R0,#0 loads the value n-1 into
R1, thereby wiping out the value n that had been put there by the code in #1.
Thus, when the instruction flow gets back to (1) where the value n is needed
by the instruction MUL R0,R0,R1, it is no longer there. It was previously
wiped out. Bad!
We can solve this problem with a stack also. That is, instead of moving the
value n to R1 before loading n-1 into R0, we push n onto the stack, and then
pop it when we need it after returning from the subroutine with (n-1)! in R0.
Finally, we note that the first instruction in our subroutine saves R1 in
SAVE_R1 and the last instruction before the RET restores it to R1. We do this
so that from the standpoint of the calling program, the value in R1 before the
subroutine is the same as the value in R1 after the subroutine, even though
the subroutine used R1 in performing its job. However, since our subroutine
is recursive, when FACT is called by the JSR instruction at address B, R1 does
not contain the value it had in the main program, but instead it has the value
last stored in R1 by the ADD R1,R0,#0 instruction. Thus after the JSR FACT
instruction is executed, the first instruction of the recursively called
subroutine FACT will save that value, wiping out all information about the
value in R1 when the main program called FACT.
We can solve this problem with a stack also. We simply replace the
ST R1,SAVE_R1 with a push and LD R1,SAVE_R1 with a pop.
If we make these changes (and if the LC-3 had a MUL opcode), the recursive
subroutine would work as we would like it to. The resulting subroutine is
as shown below (with almost all instructions explained via comments):
FACT ST R1,SAVE_R1 ; We temporarily save R1 in SAVE_R1.
ADD R1,R0,#-1 ; As before, we test for the case n=1.
BRz NO_RECURSE
ADD R1,R0,#0 ; We move n to R1 to free R0 for PUSH subroutine
ADD R0,R7,#0 ; We move the return linkage to R0, ...
JSR PUSH ; and push it onto the stack
LD R0,SAVE_R! ; We move temporarily saved R1 into R0, ...
JSR PUSH ; and push it onto the stack
ADD R0,R1,#0 ; We move n from R1 to R0, ...
JSR PUSH ; and push it onto the stack
ADD R0,R1,#-1 ; R0 = n-1
JSR FACT ; The subroutine FACT will return R0 = (n-1)!
ADD R1,R0,#0 ; moves (n-1)! to R1
JSR POP ; pops n into R0
MUL R1,R1,R0 ; R1 now contains n!
JSR POP ; pops the calling program's R1, ...
ST R0,SAVE_R1 ; and stores it in SAVE_R1
JSR POP ; pops the return linkage, ...
ADD R7,R0,#0 ; and stores it in R7
ADD R0,R1,#0 ; moves n! (the result of the subroutine) to R0
NO_RECURSE LD R1,SAVE_R1
RET
SAVE_R1 .BLKW 1
As we said, Figure New-11 shows the execution flow of the recursive subroutine
call. The main program calls FACT with R0=n. The code in (1) executes, with
JSR FACT being called with R0 = n-1. At this point, the stack contains the
three entries pushed, as shown in Figure New-12a. When the JSR FACT
instruction in (3) executes, with R0 = n-3, the contents of the stack
contains the nine entries as shown in Figure New-12b.
The obvious question you should ask at this point is, "Why is this such a
bad use of recursion, particularly when its representation n! = n * (n-1)!
is so elegant?" To answer this question, we first note how many
instructions are executed and how much time is wasted pushing and popping
elements off the stack. AND, the second question you should ask is "Is there
a better way to compute n!?
Consider this alternative:
FACT ST R1,SAVE_R1
ADD R1,R0,#0
ADD R0,R0, #-1
AGAIN MUL R1,R1,R0
ADD R0,R0,#-1
BRnp AGAIN
ADD R0,R1,#0
LD R1,SAVE_R1
RET
SAVE_R1 .BLKW 1
8.3.6.2. Fibonacci, an even worse example
>> I will add this code when I get a chance<<
8.3.6.3. The maze, a good example.
>>and this one also<<