chapter05.html

think like a computer scientist

course on the Theory of Computation, you will have a chance to see the proof.
</P>

<P>To give you an idea of what you can do with the tools we have learned so 
far, we'll evaluate a few recursively-defined mathematical functions.  A 
recursive definition is similar to a circular definition, in the sense that the
definition contains a reference to the thing being defined.  A truly circular 
definition is typically not very useful:</P>

<DL>
  <DT>frabjuous:</DT><DD> an adjective used to describe something that is 
  frabjuous.</DD>
</DL>

<P>If you saw that definition in the dictionary, you might be annoyed. On the 
other hand, if you looked up the definition of the mathematical function 
<B>factorial</B>, you might get something like:</P>

<PRE>
      0! = 1
      n! = n &#183; (n-1)!
</PRE>

<P>(Factorial is usually denoted with the symbol <TT>!</TT>, which is not to be
confused with the C++ logical operator <TT>!</TT> which means NOT.)  This 
definition says that the factorial of 0 is 1, and the factorial of any other 
value, <TT>n</TT>, is <TT>n</TT> multiplied by the factorial of <TT>n-1</TT>. 
So <TT>3!</TT> is 3 times <TT>2!</TT>, which is 2 times <TT>1!</TT>, which is 1
times 0!. Putting it all together, we get <TT>3!</TT> equal to 3 times 2 times 
1 times 1, which is 6.</P>

<P>If you can write a recursive definition of something, you can usually write 
a C++ program to evaluate it.  The first step is to decide what the parameters 
are for this function, and what the return type is. With a little thought, you 
should conclude that factorial takes an integer as a parameter and returns an 
integer:</P>

<PRE>
int factorial (int n)
{
}
</PRE>

<P>If the argument happens to be zero, all we have to do is return 1:</P>

<PRE>
int factorial (int n)
{
  if (n == 0) {
    return 1;
  }
}
</PRE>

<P>Otherwise, and this is the interesting part, we have to make a recursive 
call to find the factorial of $n-1$, and then multiply it by <TT>n</TT>.

<PRE>
int factorial (int n)
{
  if (n == 0) {
    return 1;
  } else {
    int recurse = factorial (n-1);
    int result = n * recurse;
    return result;
  }
}
</PRE>

<P>If we look at the flow of execution for this program, it is similar to 
<TT>nLines</TT> from the previous chapter. If we call <TT>factorial</TT> with 
the value 3:</P>

<P>Since 3 is not zero, we take the second branch and calculate the factorial 
of <TT>n-1</TT>...</P>

  <BLOCKQUOTE>
  Since 2 is not zero, we take the second branch and calculate the factorial of
  <TT>n-1</TT>...

    <BLOCKQUOTE>
    Since 1 is not zero, we take the second branch and calculate the factorial 
    of <TT>n-1</TT>...

      <BLOCKQUOTE>
      Since 0 <I>is</I> zero, we take the first branch and return the value 1 
      immediately without making any more recursive calls.
      </BLOCKQUOTE>

    The return value (1) gets multiplied by <TT>n</TT>, which is 1, and the 
    result is returned.
    </BLOCKQUOTE>

  The return value (1) gets multiplied by <TT>n</TT>, which is 2, and the 
  result is returned.
  </BLOCKQUOTE>

<P>The return value (2) gets multiplied by <TT>n</TT>, which is 3, and the 
result, 6, is returned to <TT>main</TT>, or whoever called 
<TT>factorial (3)</TT>.</P>

<P>Here is what the stack diagram looks like for this sequence of function 
calls:</P>

<P CLASS=1><IMG SRC="images/stack3.png" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/stack3.png" ALT="Stack3 Image"></P>

<P>The return values are shown being passed back up the stack.</P>

<P>Notice that in the last instance of <TT>factorial</TT>, the local variables 
<TT>recurse</TT> and <TT>result</TT> do not exist because when <TT>n=0</TT> the
branch that creates them does not execute.</P>


<BR><BR>
<H3>Leap of faith</H3>

<P>Following the flow of execution is one way to read programs, but as you saw 
in the previous section, it can quickly become labarynthine. An alternative is 
what I call the ``leap of faith.''  When you come to a function call, instead 
of following the flow of execution, you <I>assume</I> that the function works 
correctly and returns the appropriate value.</P>

<P>In fact, you are already practicing this leap of faith when you use built-in
functions.  When you call <TT>cos</TT> or <TT>exp</TT>, you don't examine the 
implementations of those functions.  You just assume that they work, because 
the people who wrote the built-in libraries were good programmers.</P>

<P>Well, the same is true when you call one of your own functions. For example,
in Section 5.8 we wrote a function called <TT>isSingleDigit</TT> that 
determines whether a number is between 0 and 9.  Once we have convinced 
ourselves that this function is correct---by testing and examination of the 
code---we can use the function without ever looking at the code again.</P>

<P>The same is true of recursive programs.  When you get to the recursive call,
instead of following the flow of execution, you should <I>assume</I> that the 
recursive call works (yields the correct result), and then ask yourself, 
``Assuming that I can find the factorial of <TT>n-1</TT>, can I compute the 
factorial of <TT>n</TT>?''  In this case, it is clear that you can, by 
multiplying by <TT>n</TT>.</P>

<P>Of course, it is a bit strange to assume that the function works correctly 
when you have not even finished writing it, but that's why it's called a leap 
of faith!</P>


<BR><BR>
<H3>5.12 One more example</H3>

<P>In the previous example I used temporary variables to spell out the steps, 
and to make the code easier to debug, but I could have saved a few lines:</P>

<PRE>
int factorial (int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial (n-1);
  }
}
</PRE>

<P>From now on I will tend to use the more concise version, but I recommend 
that you use the more explicit version while you are developing code. When you 
have it working, you can tighten it up, if you are feeling inspired.</P>

<P>After <TT>factorial</TT>, the classic example of a recursively-defined
mathematical function is <TT>fibonacci</TT>, which has the following 
definition:</P>

<PRE>
      fibonacci(0) = 1
      fibonacci(1) = 1
      fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);
</PRE>

<P>Translated into C++, this is</P>

<PRE>
int fibonacci (int n) {
  if (n == 0 || n == 1) {
    return 1;
  } else {
    return fibonacci (n-1) + fibonacci (n-2);
  }
}
</PRE>

<P>If you try to follow the flow of execution here, even for fairly small 
values of <TT>n</TT>, your head explodes.  But according to the leap of faith, 
if we assume that the two recursive calls (yes, you can make two recursive 
calls) work correctly, then it is clear that we get the right result by adding 
them together.</P>


<BR><BR>
<H3>5.13 Glossary</H3>

<DL>
  <DT>return type:</DT><DD> The type of value a function returns.</DD>

  <DT>return value:</DT><DD> The value provided as the result of a function
  call.</DD>

  <DT>dead code:</DT><DD> Part of a program that can never be executed, often 
  because it appears after a <TT>return</TT> statement.</DD>

  <DT>scaffolding:</DT><DD> Code that is used during program development but is 
  not part of the final version.</DD>

  <DT>void:</DT><DD> A special return type that indicates a void function; that
  is, one that does not return a value.</DD>

  <DT>overloading:</DT><DD> Having more than one function with the same name
  but different parameters. When you call an overloaded function, C++ knows 
  which version to use by looking at the arguments you provide.</DD>

  <DT>boolean:</DT><DD> A value or variable that can take on one of two states, 
  often called <TT>true</TT> and <TT>false</TT>.  In C++, boolean values can be
  stored in a variable type called <TT>bool</TT>.</DD>

  <DT>flag:</DT><DD> A variable (usually type <TT>bool</TT>) that records a 
  condition or status information.</DD>

  <DT>comparison operator:</DT><DD> An operator that compares two values and 
  produces a boolean that indicates the relationship between the operands.</DD>

  <DT>logical operator:</DT><DD> An operator that combines boolean values in 
  order to test compound conditions.</DD>
</DL>

<BR>
<DIV CLASS=navigation><HR>
  <TABLE ALIGN=center WIDTH="100%" CELLPADDING=0 CELLSPACING=2>
  <TR>
    <TD><A HREF="chapter06.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter06.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="next" 
      SRC="images/next.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/next.gif"></A>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="up" 
      SRC="images/up.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/up.gif"></A>
    </TD>

    <TD><A HREF="chapter04.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter04.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="previous"
      SRC="images/previous.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/previous.gif"></A>
    </TD>

    <TD ALIGN=center BGCOLOR="#99CCFF" WIDTH="100%">
      <B CLASS=title>How to Think Like a Computer Scientist: Chapter 5</B>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="contents"
      SRC="images/contents.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/contents.gif"></A>
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>
  </TR>
  </TABLE>

  <B CLASS=navlabel>Next:</B>
  <SPAN CLASS=sectref><A HREF="chapter06.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter06.html">Chapter 6</A></SPAN>

  <B CLASS=navlabel>Up:</B>
  <SPAN CLASS=sectref><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">Index</A></SPAN>

  <B CLASS=navlabel>Previous:</B>
  <SPAN CLASS=sectref><A HREF="chapter04.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter04.html">Chapter 4</A></SPAN>

  <HR>
</DIV>
</BODY>
</HTML>