Simple recursion

1. The following file contains a program which does exponentiation as described in exercise 5.22. Please read the exercise. (There's one typo in the exercise; the fraction 1/xⁿ should be 1/x^-n.) Copy the lab files to a called, say, recursion, using the following command:

   cp -r ~mc38/labs/recursion/files recursion
   

2. cd to this directory, and type make -k. You'll get one warning. Try running ./power in the shell; you should notice that there is a bug. You'll explore this bug in the first portion of the lab; please don't try to fix the bug until instructed to do so below.

Stack frames

As you work through this problem, please ask if you have any questions. Be sure you grasp all the concepts.

1. Set a breakpoint at the top of the int_power. (As always, you can either type C-x SPC in the code buffer, or by typing b int_power to gdb.)

2. Run your program to compute 2¹⁴. Gdb should stop at your breakpoint, and report the arguments to int_power (2 and 14).

3. Hit n or next until int_power is called recursively. Observe that the breakpoint was hit again, and the arguments are now 2 and 7.

4. Hit c or cont several more times until the arguments are 2 and 0. (If you hit c once too many, the program will output the wrong answer. In this case, I recommend you kill the gdb buffer and start over.)

5. Type where or bt or backtrace. This shows you the execution stack with 8 stack frames numbered 0 through 7. Notice that main called int_power, which called int_power, and so forth.

6. Type up and down to go up and down the stack frames. You can go all the way back up to main. Each stack frame has its own copy of all the local variables in your program. Note that you aren't executing your program as you do this, you are merely looking at what procedure calls are currently active.

7. Try inspecting the local variables in some of the stack frames with the gdb command info locals. See if the values of the variables makes sense. Notice that uninitialized variables have arbitrary values. Notice also how static variables are the same in all stack frames.

8. Go back down to the next-to-lowest stack frame (frame 1 with arguments 2 and 1). Hit bt or where once more to remind yourself what the stack looks like.

9. Type fin or finish. This asks the program to continue execution until it returns from the stack frame you are currently in. It also reports the return value from the procedure call. Now, if you do a bt or backtrace or where, you'll see that there are two fewer stack frames active. Make sense? (If not, stop and ask.)

10. Type fin one more time. You should notice the incorrect return value of 0. This is our bug!

11. We'd like to rerun the program, and quickly get to the place where the program stopped. Type cond 1 exp == 2. This says, "Break at breakpoint number 1 only if the value of variable exp is 2."

12. Type the command info break lists all your breakpoints.

13. By the way, you can also type dis 1 or disable 1 to disable a breakpoint and ena 1 or enable 1 to cause it to start working again. You might want to try these, and type info break to see what happens. In any event, leave the breakpoint in the enable state before going on.

14. Now, type run to run the program from the top. Again, enter the arguments 2 and 14.

15. Use n or next to single step through the program and see if you can figure out what went wrong. Inspect each local variable at each step.

16. Check-off Report the bug and explain how to fix it. Be sure to have your gdb buffer on the screen for our perusal.

17. For your reference, power-better.cc contains a reasonable version of the program. Although the program addresses exercise 5.22, it still has a flaw. You may wish to think about what this flaw is.

Draw a ruler

1. Complete the code in ruler.cc to draw a ruler. You can run the sample solution in

     ~mc38/labs/recursion/ruler

2. Check-off Don't forget to get checked off. Be sure the code is well documented and clear.