Main page
Course information
Class notes
Filled-out notes
Homework
Labs
Lab Write-Ups
SOE Forums
Lab 8: Recursion vs Iteration
Due date
Due Monday, June 17, 2009 at 8:00am
Lab Objective
This is the last lab in CE12L.
The Fibonacci sequence can be described in two ways: recursively with a recurrence relation, or iteratively by explaining how to obtain the next number in the sequence. Fibonacci, also known as Leonardo of Pisa (pictured in Figure 1), arguably invented the Fibonacci sequence while studying rabbit populations (although Indian mathematicians had known about the sequence for some time).
If there are two solutions to solving the same problem, you may ask: which solution is better? That depends what you mean by "better." Which one will yield a result faster? Which one is easier to implement? Therein lies the objective for this lab. You tell us: which one is better?
Figure 1: Fibonacci (c. 1170 - c. 1250)
Lab tutors: Go over these topics
Your lab tutor will cover the following topics in the first 40 minutes of lab.
- What this lab's all about
The Fibonacci sequence
Originally used to model the breeding of rabbits (see Figure 2), the Fibonacci sequence is one of the most famous and common sequences found in nature. A Fibonacci sequence is formed by adding the two previous Fibonacci numbers to obtain the next number: 1, 1, 2, 3, 5, 8, 13, ...
Figure 2: The Fibonacci sequence in rabbits
Lab 8: Recursion vs Iteration
When a function needs to call itself in order to solve a problem, this is called recursion.
For our programming purposes, we can define the Fibonacci sequence in one of two ways: recursively or iteratively. Both ways will be discussed in the sections below. You must implement both solutions in this lab.
Recursive Fibonacci
Fibonacci can be defined recursively as follows. Each number is the sum of the previous two numbers in the sequence. The nth Fibonacci number is
Fib(0) = 1,
Fib(1) = 1.
That is, the nth number is formed by adding the two previous numbers together. The equation for Fib(n) is said to be the recurrence relation and the terms for Fib(0) and Fib(1) are the base cases.
The code for the recursive Fibonacci sequence is provided in Figure 3 below.
int Fib (int n) {
if (n<=1)
return 0;
else
return ( Fib(n-1) + Fib(n-2) );
}
Figure 3: Fibonacci in C
To find Fib(n) you need to call Fib two more times: once for Fib(n-1) and once more for Fib(n-2); then you add the results. But to find Fib(n-1), you need to call Fib two more times: once for Fib(n-2) and once more for Fib(n-3); then you need to add the results. And so on! You can see the recursion tree for Fib(n) in Figure 4. The recursion tree shows each call to Fib() with different values for n.
For example, consider Fib(5), the fifth term in the sequence. To find Fib(5), you would need to find Fib(4) + Fib(3). But to find Fib(4), you would need to find Fib(3) + Fib(2). Luckily, Fib(2) is a base case; the answer to Fib(2) is 1. And so on. Look at Figure 5 for an example recursion tree for Fib(5) -- it lists all of the computations needed to carry out the calculation recursively.
It may help to visualize the nested instances of the series of recursive calls for Fib(5) in a sort of table. Figure 6 shows the recursive calls for Fib(5), with each call generating two subtables. The call to Fib() returns when both subtables have been worked down to their respective base cases, and the return value is propagated up the tree (down the table).
Fib(5) = Fib(4) + Fib(3)
Return 8 |
Figure 6: Nested calls to Fib for Fib(5)
Iterative Fibonacci
The Fibonacci sequence can be defined iteratively by describing how to obtain the next value in the sequence. That is, if you start at the base cases of Fib(0) = Fib(1) = 1, you can build the sequence up to Fib(n) without using recursive calls.
For example, calculating Fib(5) may go as follows.
- Fib(0) = 1
- Fib(1) = 1
- Fib(2) = Fib(1) + Fib(0) = 1 + 1 = 2
- Fib(3) = Fib(2) + Fib(1) = 2 + 1 = 3
- Fib(4) = Fib(3) + Fib(2) = 3 + 2 = 5
- Fib(5) = Fib(4) + Fib(3) = 5 + 3 = 8
All that is needed for this calculation is a while loop!
Lab 8: Recursion vs Iteration
Without any further ado, we present to you the last lab of the quarter.
In this lab, you will implement both recursive and iterative solutions to the Fibonacci sequence to find Fib(n) The input will be through the switches on the HC11 kit and the interrupt button; the output will be on the 2-line LCD and on the LEDs.
What's required
A checkoff, lab8.asm, and the write-up
More specifically, your program must...
- Be written in HC11 assembly language and run on the HC11 microkit
- Loop forever without crashing
- Accept the input n on the microkit's switches, and let the interrupt button be the "lock in" as described below
- Calculate Fib(n) for integers n ≥ 0 recursively and non-recursively (iteratively)
- Let the toggle between recursive and iterative solution be the input n=255 (all switches on)
- Display the result of the Fib(n) calculation on the microkit's LCD
Procedure
Here is how your program should run. Recall that you must implement both the iterative and the recursive solution for Fib().
- Let the iterative solution be the default one.
- Display on the LCD which algorithm is currently being used.
- Go into a spin-wait loop while you wait for user input.
- You can display a light pattern at this time, if you like. Though this is not required, it'll look pretty.
- The user will enter a number on the switches. When the number is selected, the user will press the interrupt button to "lock in" the number. This locked-in number is the one on which you will run your Fibonacci algorithm.
- You can display the value on the SWITCHES to the LCD, if you like, to make number selection easier. Though this is not required, it may make it easier to do integer input on the switches.
- When the interrupt button is pressed, the number on the switches is locked in -- that is, the Fibonacci algorithm will run on this number.
- The special input of 255 (all ones) indicates the change in algorithm. If the input is 255 (all ones), switch the algorithm and go to 2.
- Display the result of Fib() on the LCD.
- If necessary, wait a little bit of time before clearing or overwriting the LCD.
- Go to 3.
Extra credit
Please note that you will not receive extra credit if some or all of your basic requirements are incomplete or insufficient. The priority is to finish the basic requirements in the lab. Extra credit is not offered for late submissions.
In addition to basic requirements above, use the pulse accumulator to time how long it takes to calculate Fib(n) both iteratively and recursively. Display the time it took (in whatever units you like) to calculate Fib(n) for each input. This output may be on the console. In your write-up, compare and discuss the iterative and recursive solution with respect to amount of processing time needed. Which algorithm was faster for small n? For large n? How much faster: a little bit, or orders of magnitude? Propose conjectures: why do you think one algorithm was faster than the other?
A sample pulse accumulator program is provided. It's kind of like a pseudo-random number generator. After turning the pulse accumulator on by writing to PACTL (the pulse accumulator control register), the program waits for an interrupt. When the user presses the interrupt button, the program prints the value of PACNT (the pulse accumulator count register) to the console. Also, a dot ('.') is displayed every time the counter register PACNT overflows (that is, goes from 255 to 0).
Considerations
Some implementation details you may find useful...
Keep the interrupt service routine (ISR) short. You must exit the ISR (using RTI) as soon as possible. Do not do any computations inside the ISR. The ISR is only for setting flags.
Do not use any LCD routines inside an ISR. That includes LCDINT, LCDLINE, LCDCHAR, and any others. The LCD routines all rely on the system timer, which relies on interrupts. Using an LCD routine will clear the interrupt bit and will invite a flood of interrupts to come take over your system.
The interrupt button is not de-bounced. That is, one press of the interrupt button can generate multiple interrupts because the button "bounces" against the contact. You do not have to address this problem, but should you choose to do it, there are several methods. Two are enumerated below.
- Compare the current number entered on the switches against the most recent previous number. If they are the same, the user probably did not mean to press the button again and this press should be discarded (RTI right away). You will have to remember the previous value in a memory location.
- Use the pulse accumulator to set a timer. The button can only be pressed once in some amount of time. Each time the button is pressed, you enter the interrupt service routine and can lock in the pulse accumulator value corresponding to the first button pressed. If the next button press is within some amount of this number, it is an invalid button press and should be discarded.
We will only grade the output on the microkit's LCD. You can use the serial communications routines (CONSOLEINT, PUTCHAR, and others) for debugging; we will not grade based on your debugging output.
GETCHAR and others) for debugging; but you must remove the debugging input prior to receiving a checkoff and submitting your assignment.
References and other useful things
The Programmers' Reference Guide (PRG) will be your bread, and the Motorola Reference Manual (MRM) will be your butter for the rest of the CE12 class. Or the MRM will be your bread, and the PRG will be your butter. Or wait -- the PRG your bread, and the MRM your -- well, the PRG and MRM will be your various breads and butters.
Example code
This JavaScript Fibonacci calculator is released under the GNU General Public License (GPL) and requires JavaScript. Feel free to explore the code (view the source of this page -- it's at the bottom) if you would like a basis for your design.
Grading template
This is a suggested grading rubric. Your tutor may or may not use this rubric to grade by, but it is a good general guideline before submitting your code to check off these points.
Coding requirements
- (5 points) Function:
- Correctly assemble; contain comments; be readable; follow assembly programming convention
- Loop forever and do not crash
- Miscellaneous errors
- (15 points) Input and output:
- All relevant output must be on the microkit's LCD and LEDs.
- All relevant input must be with the switches and interrupt button.
- Display on the LCD which algorithm is currently being used.
- Accept user input on the switches, and "lock in" the number with the interrupt button.
- Allow input = 255 to be the special "toggle" command.
- Interrupt service routine must be minimal.
- Display the result of Fib() on the LCD.
- (20 points) Implementation:
- Correctly implement Fibonacci (Fib()) recursively.
- Correctly implement Fibonacci (Fib()) iteratively.
Total: 40 points
- Extra credit: (6 points) In addition to basic requirements above, use the pulse accumulator to time how long it takes to calculate Fib(n) both iteratively and recursively. Display the time it took (in whatever units you like) to calculate Fib(n) for each input. This output may be on the console. In your write-up, compare and discuss the iterative and recursive solution with respect to amount of processing time needed. Which algorithm was faster for small n? For large n? How much faster: a little bit, or orders of magnitude? Propose conjectures: why do you think one algorithm was faster than the other?
Lab write-up requirements
Don't forget about the write-up, which is still worth twelve points.
Answer the question posed at the beginning of this lab: If there are two solutions to solving the same problem, you may ask: which solution is better? That depends what you mean by "better." Which one will yield a result faster? Which one is easier to implement? Therein lies the objective for this lab. You tell us: which one is better?
Carefully explain the algorithms you used in your Fibonacci implementations. You may use pseudo-code or bulleted lists to describe the procedure. We are looking for a good understanding of recursion and recursive calls.
Explain whether your Fibonacci implementations return 8- or 16-bit values. Explain the limitations of your algorithm with respect to the number of bits allowed. If your algorithm only works on 8-bit results, explain why this may not be much of a limitation.
What is the largest number on which you can perform the recursive Fibonacci routine before the program crashes? What about the iterative routine? Why? After some point, the program crashes. Give an explanation of why the program would crash.