Introduction
c++， 2question，program1，2question，，program1
Requirement
CS 172 Winter 2015
pre-Lab 5 Exercise: Recursion, Iterators, Using the VC++ Debugger
Written: JL Popyack, Apr. 1995
Revised: Hoi-Man Chang, Jan. 1998,
JL Popyack, Feb. 1998, Apr. 1998, Apr. 1999,
P Zoski, Dec. 1999, Mar. 2000, Mar. 2001,
JL Popyack, Mar. 2002, April 2003, April 2004, April 2006
Due: Wednesday, February 4, 2015, 11:55 PM
Programs:
program1.cpp
RecursionExamples.cpp
fastPower.cpp
Reading:
Chapter 14
Course Notes:
Recursion
Iterators
Algorithms
Related Links:
Towers of Hanoi, Math Forum
PURPOSE:
The purpose of this lab is to study recursion, iterators, and the Visual C++ Debugger. The purpose of this pre-lab exercise is to prepare for study of recursion.
THE ASSIGNMENT:
Students with Bb Learn accounts should complete this lab by filling out the Quiz Form. for this lab. If you do not have a Bb Learn account, you should notify your TA so we can get one for you!
NOTE: Upon leaving the lab, be certain to remove all files containing any personal/account information, logout from any servers that have made use of your password, and close software connected to any of your accounts.
Contents:
Tracing Recursive Subprograms
Summary
Question 1:
Click here to return to table of Contents.
I. Tracing Recursive Subprograms:
Step 1: For this exercise, you are to trace some programs that call recursive subprograms.
For each of the given programs, you are to examine the code and draw diagrams that trace the execution of the diagram. The diagrams do not need to be recorded on your lab sheet. When you are finished, you should then check your answer by running the program. If your answers disagree, you should figure out why, then re-do the problem. On your lab sheet, you should summarize your results.
The rules for your diagrams are similar to those used in our study of subprograms -
As each program unit or block of code is activated, draw a rectangle that depicts its memory configuration. A block is any section of code that starts with an opening curly brace ({) and ends with the matching closing curly brace (}). For instance, your main program and subprograms are program units, and a program unit contains a block. Likewise, a group of statements surrounded by braces following an if statement is a block.
Any local variables and constants are drawn inside the block where they are declared, with boxes for the values. For instance, the program shown below would correspond to the given diagram.
As you trace the steps of your main program, blocks and/or program units should appear when they are called, then disappear after they are done executing. Initially, only your main program exists and so a diagram should be drawn for it.
When a subprogram is called, the following steps transpire:
space allocation for the subprogram: a diagram is drawn for the subprogram, with local variables as appropriate.
argument matching: draw a line connecting each argument in the subprogram call to each argument in the subprogram diagram. The subprogram’s formal arguments should be depicted as attached to the edge of the subprogram diagram as shown in the example below - arguments passed by value should show a local copy created inside the subprogram; arguments passed by reference should show no local copy made, but an arrow showing a direct connection to the actual argument:
argument passing: For arguments passed by value, copy the value of the actual argument into the location given for the formal argument (as in the example above). No additional work is done for arguments passed by reference.
execution of the subprogram: Keep track of where you were in the calling program unit before executing the subprogram. Then execute the statements in the subprogram.
return value sent back to the calling unit (if applicable): if the subprogram is a function, a value is returned.
space de-allocation for the subprogram: the diagram should be erased (or at least crossed out), to depict that the subprogram no longer exists.
Because you are unlikely to be able to draw a diagram such as the one above on your lab sheet, follow these steps for the exercises below:
Trace the function calls on paper
On your lab sheet, show the sequence of functions called and exited, along with values of arguments. For instance, here is a sample trace for the example above:
main: x=?, w=7
f : a=7
b=a/2 =3
return b*b = 9
main: x=9, w=7
Step 2: Palindrome. Palindrome.cpp () Use the following inputs: Palindrome, radar, repeater, noon.
Question 2:
Step 3: Fast Power. fastPower.cpp () Trace the computations of 210, 215.
End of Questions
Click here to return to table of Contents.
II. Summary:
This exercise provided some experience with how recursive routines are executed. The process of allocation and deallocation from the stack is the same for all subprograms, recursive or not. Understanding how recursive subprograms are executed is the first step towards designing and implementing recursive subprograms.
Contents:
Tracing Recursive Subprograms
Summary