ch05.htm

vc的电子书

times, the inline code is copied into the calling functions each of those 10 times.
The tiny improvement in speed you might achieve is more than swamped by the increase
in size of the executable program. Even the speed increase might be illusory. First,
today's optimizing compilers do a terrific job on their own, and there is almost
never a big gain from declaring a function <TT>inline</TT>. More important, the increased
size brings its own performance cost.</P>
<P>What's the rule of thumb? If you have a small function, one or two statements,
it is a candidate for <TT>inline</TT>. When in doubt, though, leave it out. Listing
5.9 demonstrates an <TT>inline</TT> function.</P>
<P><A NAME="Heading41"></A><FONT SIZE="4" COLOR="#000077"><B>Listing 5.9. Demonstrates
an inline function.</B></FONT></P>
<PRE><FONT COLOR="#0066FF">1:   // Listing 5.9 - demonstrates inline functions
2:
3:   #include &lt;iostream.h&gt;
4:
5:   inline int Double(int);
6:
7:   int main()
8:   {
9:     int target;
10:
11:    cout &lt;&lt; &quot;Enter a number to work with: &quot;;
12:    cin &gt;&gt; target;
13:    cout &lt;&lt; &quot;\n&quot;;
14:
15:    target = Double(target);
16:    cout &lt;&lt; &quot;Target: &quot; &lt;&lt; target &lt;&lt; endl;
17:
18:    target = Double(target);
19:    cout &lt;&lt; &quot;Target: &quot; &lt;&lt; target &lt;&lt; endl;
20:
21:
22:    target = Double(target);
23:    cout &lt;&lt; &quot;Target: &quot; &lt;&lt; target &lt;&lt; endl;
24:       return 0;
25:  }
26:
27:  int Double(int target)
28:  {
29:    return 2*target;
<TT>30: }</TT>
Output: Enter a number to work with: 20

Target: 40
Target: 80
Target: 160
</FONT></PRE>

<DL>
	<DD>
<HR>
<FONT COLOR="#000077"><B>Analysis:</B></FONT><B> </B>On line 5, <TT>Double()</TT>
	is declared to be an inline function taking an <TT>int</TT> parameter and returning
	an <TT>int</TT>. The declaration is just like any other prototype except that the
	keyword <TT>inline</TT> is prepended just before the return value.
	<P>This compiles into code that is the same as if you had written the following:</P>
	<PRE><FONT COLOR="#0066FF">target = 2 * target;</FONT></PRE>
	<DD><FONT COLOR="#0066FF"></FONT>
	<P>everywhere you entered</P>
	<PRE><FONT COLOR="#0066FF">target = Double(target);</FONT></PRE>
	<DD><FONT COLOR="#0066FF"></FONT>
	<P>By the time your program executes, the instructions are already in place, compiled
	into the OBJ file. This saves a jump in the execution of the code, at the cost of
	a larger program. 
<HR>

</DL>



<BLOCKQUOTE>
	<P>
<HR>
<FONT COLOR="#000077"><B>NOTE:</B></FONT><B> </B>Inline is a hint to the compiler
	that you would like the function to be inlined. The compiler is free to ignore the
	hint and make a real function call. 
<HR>


</BLOCKQUOTE>

<H4 ALIGN="CENTER"><A NAME="Heading43"></A><FONT COLOR="#000077">Recursion</FONT></H4>
<P>A function can call itself. This is called recursion, and recursion can be direct
or indirect. It is direct when a function calls itself; it is indirect recursion
when a function calls another function that then calls the first function.</P>
<P>Some problems are most easily solved by recursion, usually those in which you
act on data and then act in the same way on the result. Both types of recursion,
direct and indirect, come in two varieties: those that eventually end and produce
an answer, and those that never end and produce a runtime failure. Programmers think
that the latter is quite funny (when it happens to someone else).</P>
<P>It is important to note that when a function calls itself, a new copy of that
function is run. The local variables in the second version are independent of the
local variables in the first, and they cannot affect one another directly, any more
than the local variables in <TT>main()</TT> can affect the local variables in any
function it calls, as was illustrated in Listing 5.4.</P>
<P>To illustrate solving a problem using recursion, consider the Fibonacci series:</P>
<PRE><FONT COLOR="#0066FF">1,1,2,3,5,8,13,21,34...
</FONT></PRE>
<P>Each number, after the second, is the sum of the two numbers before it. A Fibonacci
problem might be to determine what the 12th number in the series is.</P>
<P>One way to solve this problem is to examine the series carefully. The first two
numbers are 1. Each subsequent number is the sum of the previous two numbers. Thus,
the seventh number is the sum of the sixth and fifth numbers. More generally, the
nth number is the sum of n - 2 and n - 1, as long as n &gt; 2.</P>
<P>Recursive functions need a stop condition. Something must happen to cause the
program to stop recursing, or it will never end. In the Fibonacci series, n &lt;
3 is a stop condition.</P>
<P>The algorithm to use is this:

<DL>
	<DD><B>1.</B> Ask the user for a position in the series.<BR>
	<B><BR>
	2.</B> Call the <TT>fib()</TT> function with that position, passing in the value
	the user entered.<BR>
	<B><BR>
	3. </B>The <TT>fib()</TT> function examines the argument (<TT>n</TT>). If <TT>n &lt;
	3</TT> it returns 1; otherwise, <TT>fib()</TT> calls itself (recursively) passing
	in <TT>n-2</TT>, calls itself again passing in <TT>n-1</TT>, and returns the sum.
</DL>

<P>If you call <TT>fib(1)</TT>, it returns <TT>1</TT>. If you call <TT>fib(2)</TT>,
it returns <TT>1</TT>. If you call <TT>fib(3)</TT>, it returns the sum of calling
<TT>fib(2)</TT> and <TT>fib(1)</TT>. Because <TT>fib(2)</TT> returns <TT>1</TT> and
<TT>fib(1)</TT> returns <TT>1</TT>, <TT>fib(3)</TT> will return <TT>2</TT>.</P>
<P>If you call <TT>fib(4)</TT>, it returns the sum of calling <TT>fib(3)</TT> and
<TT>fib(2)</TT>. We've established that <TT>fib(3)</TT> returns <TT>2</TT> (by calling
<TT>fib(2)</TT> and <TT>fib(1)</TT>) and that <TT>fib(2)</TT> returns <TT>1</TT>,
so <TT>fib(4)</TT> will sum these numbers and return <TT>3</TT>, which is the fourth
number in the series.</P>
<P>Taking this one more step, if you call <TT>fib(5)</TT>, it will return the sum
of <TT>fib(4)</TT> and <TT>fib(3)</TT>. We've established that <TT>fib(4)</TT> returns
<TT>3</TT> and <TT>fib(3)</TT> returns <TT>2</TT>, so the sum returned will be <TT>5</TT>.</P>
<P>This method is not the most efficient way to solve this problem (in <TT>fib(20)</TT>
the<TT> fib()</TT> function is called 13,529 times!), but it does work. Be careful:
if you feed in too large a number, you'll run out of memory. Every time <TT>fib()</TT>
is called, memory is set aside. When it returns, memory is freed. With recursion,
memory continues to be set aside before it is freed, and this system can eat memory
very quickly. Listing 5.10 implements the <TT>fib()</TT> function.


<BLOCKQUOTE>
	<P>
<HR>
<FONT COLOR="#000077"><B>WARNING:</B></FONT><B> </B>When you run Listing 5.10, use
	a small number (less than 15). Because this uses recursion, it can consume a lot
	of memory. 
<HR>


</BLOCKQUOTE>

<P><A NAME="Heading44"></A><FONT SIZE="4" COLOR="#000077"><B>Listing 5.10. Demonstrates
recursion using the Fibonacci series</B></FONT><FONT SIZE="2" COLOR="#000077"><B>.</B></FONT></P>
<PRE><FONT COLOR="#0066FF">1:     // Listing 5.10 - demonstrates recursion
2:     // Fibonacci find.
3:     // Finds the nth Fibonacci number
4:     // Uses this algorithm: Fib(n) = fib(n-1) + fib(n-2)
5:     // Stop conditions: n = 2 || n = 1
6:
7:     #include &lt;iostream.h&gt;
8:
9:     int fib(int n);
10:
11:    int main()
12:    {
13:
14:      int n, answer;
15:      cout &lt;&lt; &quot;Enter number to find: &quot;;
16:      cin &gt;&gt; n;
17:
18:      cout &lt;&lt; &quot;\n\n&quot;;
19:
20:      answer = fib(n);
21:
22:      cout &lt;&lt; answer &lt;&lt; &quot; is the &quot; &lt;&lt; n &lt;&lt; &quot;th Fibonacci number\n&quot;;
23:         return 0;
24:    }
25:
26:    int fib (int n)
27:    {
28:      cout &lt;&lt; &quot;Processing fib(&quot; &lt;&lt; n &lt;&lt; &quot;)... &quot;;
29:
30:      if (n &lt; 3 )
31:      {
32:         cout &lt;&lt; &quot;Return 1!\n&quot;;
33:         return (1);
34:      }
35:      else
36:      {
37:        cout &lt;&lt; &quot;Call fib(&quot; &lt;&lt; n-2 &lt;&lt; &quot;) and fib(&quot; &lt;&lt; n-1 &lt;&lt; &quot;).\n&quot;;
38:        return( fib(n-2) + fib(n-1));
39:      } 
<TT>40: }</TT></FONT>
<FONT COLOR="#0066FF">
Output: Enter number to find:  5

Processing fib(5)... Call fib(3) and fib(4).
Processing fib(3)... Call fib(1) and fib(2).
Processing fib(1)... Return 1!
Processing fib(2)... Return 1!
Processing fib(4)... Call fib(2) and fib(3).
Processing fib(2)... Return 1!
Processing fib(3)... Call fib(1) and fib(2).
Processing fib(1)... Return 1!
Processing fib(2)... Return 1!
5 is the 5th Fibonacci number
</FONT></PRE>
<P><FONT COLOR="#000077"><B>Analysis:</B></FONT><B> </B>The program asks for a number
to find on line 15 and assigns that number to <TT>target</TT>. It then calls <TT>fib()</TT>
with the <TT>target</TT>. Execution branches to the <TT>fib()</TT> function, where,
on line 28, it prints its argument.<BR>
The argument <TT>n</TT> is tested to see whether it equals <TT>1</TT> or <TT>2</TT>
on line 30; if so, <TT>fib()</TT> returns. Otherwise, it returns the sums of the
values returned by calling <TT>fib()</TT> on <TT>n-2</TT> and <TT>n-1</TT>.</P>
<P>In the example, <TT>n</TT> is 5 so <TT>fib(5)</TT> is called from <TT>main()</TT>.
Execution jumps to the <TT>fib()</TT> function, and <TT>n</TT> is tested for a value
less than 3 on line 30. The test fails, so <TT>fib(5)</TT> returns the sum of the
values returned by <TT>fib(3)</TT> and <TT>fib(4)</TT>. That is, <TT>fib()</TT> is
called on <TT>n-2</TT> (5 - 2 = 3) and <TT>n-1</TT> (5 - 1 = 4). <TT>fib(4)</TT>
will return <TT>3</TT> and <TT>fib(3)</TT> will return <TT>2</TT>, so the final answer
will be 5.</P>
<P>Because <TT>fib(4)</TT> passes in an argument that is not less than 3, <TT>fib()</TT>
will be called again, this time with 3 and 2. <TT>fib(3)</TT> will in turn call <TT>fib(2)</TT>
and <TT>fib(1)</TT>. Finally, the calls to <TT>fib(2)</TT> and <TT>fib(1)</TT> will
both return <TT>1</TT>, because these are the stop conditions.</P>
<P>The output traces these calls and the return values. Compile, link, and run this
program, entering first 1, then 2, then 3, building up to 6, and watch the output
carefully. Then, just for fun, try the number 20. If you don't run out of memory,
it makes quite a show! <BR>
<BR>
Recursion is not used often in C++ programming, but it can be a powerful and elegant
tool for certain needs.


<BLOCKQUOTE>
	<P>
<HR>
<FONT COLOR="#000077"><B>NOTE:</B></FONT><B> </B>Recursion is a very tricky part
	of advanced programming. It is presented here because it can be very useful to understand
	the fundamentals of how it works, but don't worry too much if you don't fully understand
	all the details. 
<HR>


</BLOCKQUOTE>

<H3 ALIGN="CENTER"><A NAME="Heading46"></A><FONT COLOR="#000077">How Functions WorkA
Look Under the Hood</FONT></H3>
<H3 ALIGN="CENTER"><FONT COLOR="#000077"></FONT></H3>
<P>When you call a function, the code branches to the called function, parameters
are passed in, and the body of the function is executed. When the function completes,
a value is returned (unless the function returns <TT>void</TT>), and control returns
to the calling function.</P>
<P>How is this task accomplished? How does the code know where to branch to? Where
are the variables kept when they are passed in? What happens to variables that are
declared in the body of the function? How is the return value passed back out? How
does the code know where to resume?</P>
<P>Most introductory books don't try to answer these questions, but without understanding
this information, you'll find that programming remains a fuzzy mystery. The explanation
requires a brief tangent into a discussion of computer memory.
<H4 ALIGN="CENTER"><A NAME="Heading48"></A><FONT COLOR="#000077">Levels of Abstraction</FONT></H4>
<P>One of the principal hurdle